AT_pakencamp_2022_day1_g Ancestor Query

$ N $ 頂点の根付き木が与えられます。頂点には $ 1 $ から $ N $ までの番号が振られており、根は頂点 $ 1 $ で、頂点 $ i\,(2\leq i\leq N) $ の親は頂点 $ P_i $ です。 $ Q $ 個の質問が与えられるので答えてください。 $ i $ 番目の質問では整数 $ X_i, Y_i $ が与えられます。頂点 $ X_i $ は頂点 $ Y_i $ の祖先であり、二頂点間の距離を $ d $ とすると $ d\geq2 $ です。頂点 $ X_i $ と $ Y_i $ を結ぶパス上の頂点の番号を順に $ v_0,v_1,\ldots,v_d $ （ただし、 $ v_0=X_i, v_d=Y_i $ ）とするとき、 $ v_1 $ を出力してください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ P_2 $ $ P_3 $ $ \ldots $ $ P_N $ $ Q $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行出力してください。 $ i\, (1\leq i\leq Q) $ 行目には、 $ i $ 番目の質問に対する答えを出力してください。

### Sample Explanation 1 $ 1 $ 番目のクエリにおいて、 $ (v_0,v_1,v_2,v_3)=(1,3,5,7) $ であり、 $ v_1=3 $ です。 $ 2 $ 番目のクエリにおいて、 $ (v_0,v_1,v_2)=(3,5,6) $ であり、 $ v_1=5 $ です。 $ 3 $ 番目のクエリにおいて、 $ (v_0,v_1,v_2)=(3,5,7) $ であり、 $ v_1=5 $ です。 ### Constraints - $ 3\leq N\leq 2\cdot 10^5 $ - $ 1\leq P_i\leq i-1\, (2\leq i\leq N) $ - $ 1\leq Q\leq 2\cdot 10^5 $ - $ 1\leq X_i,Y_i\leq N\, (1\leq i\leq Q) $ - 頂点 $ X_i $ は頂点 $ Y_i $ の祖先 $ (1\leq i\leq Q) $ - 頂点 $ X_i $ と頂点 $ Y_i $ の距離は $ 2 $ 以上