Tidy Subgraph Intervals

We are given a tree \(G\) with \(n\) vertices and \(n-1\) edges. A vertex-induced subgraph for a set of vertices \(E\) is defined as the graph containing vertices \(E\) and all edges of \(G\) whose both endpoints lie in \(E\).

A graph is said to be tidy if for any two vertices \(u,v\), either they are disconnected or their distance is at most \(k\) (i.e. \(d(u,v) \le k\)). Equivalently, each connected component of the graph has a diameter not exceeding \(k\).

You are also given \(q\) queries. For each query, given two integers \(l\) and \(r\) (with \(l \le r\)), consider all intervals \([a,b]\) with \(l \le a \le b \le r\). For each such interval, take the vertex-induced subgraph on vertices numbered from \(a\) to \(b\) (inclusive). You need to count how many intervals yield a tidy subgraph and also calculate the sum of the lengths (i.e. \(b-a+1\)) of these intervals.

Note: The vertices of the tree are numbered from \(1\) to \(n\).

inputFormat

The first line contains three integers \(n\), \(q\) and \(k\): the number of vertices in the tree, the number of queries, and the maximum allowed distance.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating an undirected edge between vertices \(u\) and \(v\) in the tree.

The following \(q\) lines each contain two integers \(l\) and \(r\) (with \(l \le r\)) representing a query.

outputFormat

For each query, output two integers separated by a space: the number of valid intervals \([a,b]\) whose vertex-induced subgraph is tidy, and the sum of lengths (i.e. \(b-a+1\)) of these intervals.

sample

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

13 26
6 10
6 10