Background

This problem has a large amount of input and output, so please use faster I/O methods when appropriate. The time limit has been increased from $1s\to 1.5s$.

Problem Description

Given a tree with $n$ nodes and root $k$. Initially, there is one and only one “extendable” node $z$. We have two types of extensions:

• Type $\text{I}$ extension: start from an “extendable” node $u$, and mark as “extendable” all nodes in the subtree of $u$, as well as all nodes that are ancestors of $u$ and satisfy that their distance to $u$ is $\leq p$.
• Type $\text{II}$ extension: start from an “extendable” node $u$, and mark as “extendable” all nodes whose depth is the same as $u$.

You need to mark all nodes as “extendable”. Find the minimum number of extensions needed.

Input Format

The first line contains two integers $n,k$.

The next $n-1$ lines each contain two integers $u,v$, indicating that there is an undirected edge between $u$ and $v$.

The next line contains one integer $t$, the number of queries.

The next $t$ lines each contain two integers $z,p$, with the meaning as described above.

Output Format

Output $t$ lines. For each query:

• If it is impossible to mark all nodes as “extendable”, output -1.
• Otherwise, output one integer, the answer.

3 1
1 2
1 3
2
2 6
2 1

2
2

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

1
1
2

20 11
2 8
16 4
6 7
11 8
10 13
7 10
17 7
15 13
10 14
18 19
1 2
6 3
12 1
1 5
1 4
2 3
9 5
14 20
5 18
15
9 269
1 522
6 327
13 726
14 8
17 2
18 4
15 64
9 5
13 3
18 1
19 664
5 3
20 5
6 4

2
2
2
2
2
3
2
2
2
3
5
2
2
3
2

Hint

Explanation for Sample $1$: for both queries, you can first perform a Type $\text{II}$ extension on node $2$, and then perform a Type $\text{I}$ extension on node $3$. It can be guaranteed that for both queries, this operation is optimal.

Constraints: for all testdata, $1\leq z,k,u,v\leq n\leq 10^5,1\leq t\leq 2\times 10^6,0\leq p\leq 10^{18}$.

Translated by ChatGPT 5