当前没有测试数据。

F - 步数刚好为K

得分：500分

问题描述

给定一棵有$N$个顶点的树。顶点编号为$1, \dots, N$，第$i$条（$1 \leq i \leq N - 1$）边连接顶点$A_i$和$B_i$。

我们定义树上顶点$u$和$v$之间的距离为从顶点$u$到顶点$v$的最短路径上的边数。

给出$Q$个查询。在第$i$个（$1 \leq i \leq Q$）查询中，给定整数$U_i$和$K_i$，输出离顶点$U_i$距离正好为$K_i$的任意一个顶点的索引。如果没有这样的顶点，则输出-1。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)$
• 给定的图是一棵树。
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)$
• 输入中的所有值都为整数。

输入

从标准输入中按以下格式给出输入：

$N$

$A_1$ $B_1$

$\vdots$

$A_{N-1}$ $B_{N-1}$

$Q$

$U_1$ $K_1$

$\vdots$

$U_Q$ $K_Q$

输出

输出$Q$行。第$i$行（$1 \leq i \leq Q$）应当输出离顶点$U_i$距离正好为$K_i$的任意一个顶点的索引，如果不存在这样的顶点，则输出-1。如果存在多个这样的顶点，则输出任意一个都可以。

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

4
1
-1

• 有两个顶点，顶点$4$和顶点$5$，到达顶点$2$的距离正好为$2$。
• 只有顶点$1$到达顶点$5$的距离正好为$3$。
• 没有顶点到达顶点$3$的距离正好为$3$。

10
1 2
2 3
3 5
2 8
3 4
4 6
4 9
5 7
9 10
5
1 1
2 2
3 3
4 4
5 5

2
4
10
-1
-1