分数: 500 点
问题陈述
你得到了一棵树 N 顶点。 顶点已编号 1, \dots, N,以及 i-th (1 \leq i \leq N - 1) 边连接顶点 A_i 和 B_i.
我们定义 距离 顶点之间 u 和 v 在这棵树上通过从顶点开始的最短路径中的边数 u 到顶点 v.
你被给予 Q 查询。 在 i-th (1 \leq i \leq Q) 查询,给定整数 U_i 和 K_i,打印距 Vertex 距离的任何顶点的索引 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-th (1 \leq i \leq Q)行应包含距顶点距离的任何顶点的索引 U_i 正是 K_i 如果存在这样的顶点;如果没有,它应该包含 -1。 如果有多个这样的顶点,您可以打印其中任何一个。
示例输入 1
5 1 2 2 3 3 4 3 5 3 2 2 5 3 3 3
示例输出 1
4 1 -1
- 两个顶点,顶点 4 和 5,有一个精确的距离 2 来自顶点 2.
- 仅顶点 1 的距离正好 3 来自顶点 5.
- 没有顶点具有精确的距离 3 来自顶点 3.
示例输入 2
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
2 4 10 -1 -1