AT_abc267_f [ABC267F] Exactly K Steps

[problemUrl]: https://atcoder.jp/contests/abc267/tasks/abc267_f $ 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` を出力せよ。そのような頂点が複数存在する場合、どれを出力しても正解となる。

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