题目描述

$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 を出力せよ。そのような頂点が複数存在する場合、どれを出力しても正解となる。

题目大意

题目描述

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

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) $
• 入力は全て整数

Sample Explanation 1

- 頂点 $2$ からの距離がちょうど $2$ であるのは頂点 $4,\ 5$ の二つです。 - 頂点 $5$ からの距離がちょうど $3$ であるのは頂点 $1$ のみです。 - 頂点 $3$ からの距離がちょうど $3$ である頂点は存在しません。