恰好 K 步

题目描述

给定一棵具有 $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。

输入格式

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

$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

与顶点 $2$ 距离恰好为 $2$ 的顶点有两个，分别是顶点 $4$ 和 $5$。

与顶点 $5$ 距离恰好为 $3$ 的顶点只有顶点 $1$。

与顶点 $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

数据范围

• $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)$
• 输入中的所有值均为整数

提示

答案不唯一,输出任意合法解即可。