题目描述

在神秘的埃洛利亚森林中，存在着一张由远古灵树构成的网络。这些灵树彼此通过隐形的能量通道相互连接，形成了一种没有任何环的能量树状结构。

共有 $N$ 棵灵树，编号为 $1$ 到 $N$。这些树之间有 $N-1$ 条能量通道，其中第 $i$ 条通道连接了编号为 $A_i$ 和 $B_i$ 的两棵树。

森林守护者 dash 收到了一些年轻学徒的请求。每位学徒想知道：如果他们从某一棵特定的灵树 $U_i$ 出发，是否能够找到一棵恰好距离为 $K_i$ 的其他灵树（即经过 $K_i$ 条通道）？

你的任务是协助 dash 回答这些请求。对于每个请求，如果存在一棵距离为恰好 $K_i$ 的树，则输出其编号；如果不存在这样的灵树，则输出 -1。

输入格式

第一行一个整数 $N$，表示灵树的总数。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$，表示有一条能量通道连接灵树 $A_i$ 和 $B_i$。

接下来一行一个整数 $Q$，表示请求的数量。

接下来 $Q$ 行，每行两个整数 $U_i,K_i$，表示第 $i$ 个请求中，学徒从灵树 $U_i$ 出发，想找到一棵距离为 $K_i$ 的其他灵树。

输出格式

对于每个请求，输出一行一个整数，表示与 $U_i$ 的距离恰好为 $K_i$ 的灵树编号；若有多个符合条件的灵树，输出任意一个即可；若不存在，输出 -1。

样例

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

4
1
-1

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)$