Background

Xiao L has many favorite game characters, and he connects these characters according to certain relationships. These characters and their relationships form a tree, which Xiao L calls the "relationship tree".

Problem Description

A relationship tree is a tree consisting of $n$ vertices and $n - 1$ undirected edges.

For a given graph $G$, define the vertex-induced subgraph of $G$ on a vertex set $E$ as the graph consisting of the vertex set $E$ and all edges in the original graph $G$ whose both endpoints belong to $E$.

A graph is defined to be clean if and only if for any two vertices $u, v$ in the graph, either $u$ and $v$ are not connected, or the distance is at most $k$.

Xiao L wants to know, for a query pair $l, r$ ($l \leq r$), how many pairs $(a, b)$ satisfy $l \leq a \leq b \leq r$, such that the vertex-induced subgraph formed by all vertices with indices from $a$ to $b$ (including $a, b$) is clean. Moreover, he also wants you to output the sum of all interval lengths (i.e., $b - a + 1$).

Since Xiao L likes asking questions, you need to answer a total of $q$ queries.

Input Format

The first line contains three integers $n$, $q$, $k$, with the meanings as described above.

The next $n - 1$ lines each contain two integers $u$, $v$, describing an edge.

The next $q$ lines each contain two integers $l$, $r$, representing a query.

Output Format

Output $q$ lines. Each line contains two integers: the number of valid pairs $(a, b)$, and the sum of all interval lengths.

5 3 2
1 2
1 5
4 5
3 5
1 3
2 5
1 5

6 10
10 20
14 30

Hint

Sample 1 Explanation

The relationship tree formed is shown in the figure.

The valid $(a, b)$ are $(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)$.

The answers to the three queries are $6,10$, $10,20$, and $14,30$, respectively.

Constraints

This problem uses bundled testdata.

• Subtask 1 ( $10\%$ ): $n \leq 2000$.
• Subtask 2 ( $30\%$ ): $n \leq 2 \times 10^4$, and the relationship tree is a chain.
• Subtask 3 ( $60\%$ ): $n \leq 2 \times 10^4$.
• Subtask 4 ( Enhanced version testdata, time limit $4.5s$ ): No special restrictions.

For all test cases ($100\%$), it is guaranteed that $1 \leq n \leq 8 \times 10^4$, $1 \leq q \leq 10^5$, $0 \leq k < n$, $1 \leq u, v, l, r \leq n$.

Translated by ChatGPT 5