AT_abc267_f [ABC267F] Exactly K Steps

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

### 制約 - $ 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 $ である頂点は存在しません。