The Reason You Clicked

You are given a tree with n nodes numbered from \(1\) to \(n\). Each edge in the tree has a weight of \(1\). You are also given a constant \(X\) (with \(X \ge 1\)).

For any two nodes \(a\) and \(b\), let \(dist(a,b)\) denote the sum of the edge weights on the unique simple path from \(a\) to \(b\) (with \(dist(a,a)=0\)).

For each query, you are given an interval \([l,r]\) (i.e. all nodes with labels \(l, l+1, \dots, r\)). In the context of the query, we define an \(X\)-connectivity between two nodes \(a\) and \(b\) in \([l,r]\) as follows: They are \(X\)-connected if and only if there exists a sequence of nodes \(\{v_i\}_{i=1}^{t}\) (where \(t\) can be any positive integer) satisfying:

1. \(v_1 = a\).
2. \(v_t = b\).
3. For every \(1 \le i \le t-1\), \(dist(v_i,v_{i+1}) \le X\).
4. For every \(1 \le i \le t\), \(l \le v_i \le r\).

A set \(S\) (of nodes) with \(S \subseteq \{l, l+1, \dots, r\}\) is called an \(X\)-block if it satisfies:

1. For any node \(a \in S\) and any node \(b \in [l,r] \setminus S\), \(a\) and \(b\) are not \(X\)-connected.
2. For any two nodes \(a,b \in S\), \(a\) and \(b\) are \(X\)-connected.
3. Every node \(a \in S\) satisfies \(l \le a \le r\).

Your task is: for each query, count the number of \(X\)-blocks in the interval \([l,r]\).

Note: The \(X\)-connectivity is defined using the distance in the original tree even if the intermediate nodes on the unique path between two nodes are not in the sequence; only the endpoints of each jump are required to lie in \([l,r]\). For example, consider the tree with 3 nodes in a line (\(1-2-3\)). Even if the tree edge between \(1\) and \(3\) does not exist, since \(dist(1,3)=2\), if \(X \ge 2\) then nodes \(1\) and \(3\) are \(X\)-connected with the jump \([1,3]\).

inputFormat

The first line contains two integers \(n\) and \(X\) (\(1 \le n \le \text{small}\), \(X \ge 1\)).

The next \(n-1\) lines each contain two integers \(u\) and \(v\), meaning there is an edge between nodes \(u\) and \(v\).

The next line contains an integer \(q\), the number of queries.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) (\(1 \le l \le r \le n\)).

outputFormat

For each query, output a single integer on a new line: the number of \(X\)-blocks in the interval \([l,r]\).

sample

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

1
2
2

</p>