题目描述

给定一棵具有 $N$ 个顶点的树。顶点被编号为 $1, \\dots, N$，第 $i$ 条边连接顶点 $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$

输出

输出结果到标准输出。

输出格式如下：

对于每个查询，输出一行。第 $i$ 行（$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$ 到顶点 $5$ 的距离恰好为 $3$。
• 没有顶点到顶点 $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