题目描述

给定一棵有 $N$ 个点的树，每个点的编号分别为 $1,2,\cdots,N$；给定的第 $i(1\leq i\leq N-1)$ 条边连接编号为 $A_i,B_i$ 的点。

定义两点 $u,v$ 间的距离为这两个点之间的最短路径所包含的边数。

现有 $Q$ 组询问，对于第 $i$ 组询问，给定 $U_i,K_i$，找到任意一个离结点 $U_i$ 的距离恰好为 $K_i$ 的点，或报告无解。

输入格式

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$，表示 $A_i,B_i$ 间有一条边。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $U_i,K_i$，意义如上所述。

输出格式

对于每一组询问，输出一行一个整数，表示与 $U_i$ 距离恰为 $K_i$ 的结点编号。若不止一个这样的结点，输出任意一个即可；特别地，若没有这样的结点，输出 -1。

样例 1

输入

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

输出

4
1
-1

样例 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
4
10
-1
-1

说明/提示

数据范围

• $2\le N \le 2\times 10^5$
• $1\le A_i<B_i\le N(1\le i\le N-1)$
• 保证给定的图为一棵树。
• $1\le Q \le 2\times 10^5$
• $1\le U_i,K_i\le N(1\le i \le Q)$
• 所有输入值均为整数。

样例解释#1

• 有两个点 $4$ 和 $5$ 满足与点 $2$ 的距离为 $2$。
• 只有点 $1$ 满足与点 $5$ 的距离为 $3$。
• 没有点与点 $3$ 的距离为 $3$。