题目描述

对于一棵有 $n$ 个节点，根为 $k$ 的树，最开始有且仅有一个“可扩展的”节点 $z$，我们有两种扩展形式：

• $\text{I}$ 类扩展：从一个“可扩展的”节点 $u$ 开始扩展，把 $u$ 的子树中所有节点和所有满足与 $u$ 距离 $\leq p$ 且是 $u$ 祖先的节点标记为“可扩展的”。
• $\text{II}$ 类扩展：从一个“可扩展的”节点 $u$ 开始扩展，把所有与 $u$ 深度相等的节点标记为“可扩展的”。

你需要将所有结点都标记为“可扩展的”，求最小进行扩展的次数。

输入格式

第一行两个整数 $n,k$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示存在一条无向边连接 $u,v$。

接下来一行一个整数 $t$，表示询问次数。

接下来 $t$ 行，每行两个整数 $z,p$，意义如上。

输出格式

$t$ 行，对于每次询问：

• 若无法将所有节点都标记为“可扩展的”，输出 -1。

• 否则一行一个整数，表示答案。

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

提示

样例 $1$ 解释：两次询问都可以先对 $2$ 节点进行 $\text{II}$ 类扩展，然后对 $3$ 进行 $\text{I}$ 类扩展。可以保证对于两次询问，这样操作都是最优的。

对于所有数据，$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}$。