AT_abc295_g [ABC295G] Minimum Reachable City

[problemUrl]: https://atcoder.jp/contests/abc295/tasks/abc295_g $ N $ 頂点の有向グラフ $ G_S $ があり、頂点には $ 1 $ から $ N $ までの番号が付けられています。 $ G_S $ には $ N-1 $ 本の辺があり、$ i $ 本目 $ (1\leq\ i\ \leq\ N-1) $ の辺は頂点 $ p_i\ (1\leq\ p_i\ \leq\ i) $ から頂点 $ i+1 $ に伸びています。 $ N $ 頂点の有向グラフ $ G $ があり、頂点には $ 1 $ から $ N $ までの番号が付けられています。 最初、$ G $ は $ G_S $ と一致しています。 $ G $ に関するクエリが $ Q $ 個与えられるので、与えられた順番に処理してください。クエリは次の $ 2 $ 種類のいずれかです。 - `1 u v` : $ G $ に頂点 $ u $ から頂点 $ v $ に伸びる辺を追加する。 このとき、以下の条件が満たされることが保証される。 - $ u\ \neq\ v $ - $ G_S $ 上で頂点 $ v $ からいくつかの辺を辿ることで頂点 $ u $ に到達可能である - `2 x` : $ G $ 上で頂点 $ x $ からいくつかの辺を辿ることで到達可能な頂点 (頂点 $ x $ を含む) のうち、最も番号が小さい頂点の番号を出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ p_1 $ $ p_2 $ $ \dots $ $ p_{N-1} $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ ただし、$ \mathrm{query}_i $ は $ i $ 個目のクエリを表しており、次のいずれかの形式で与えられる。 > $ 1 $ $ u $ $ v $ > $ 2 $ $ x $

$ 2 $ 番目の形式のクエリの回数を $ q $ 回として、$ q $ 行出力せよ。 $ j\ (1\leq\ j\ \leq\ q) $ 行目には、$ 2 $ 番目の形式のクエリのうち $ j $ 個目のものに対する答えを出力せよ。

### 制約 - $ 2\leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\leq\ Q\ \leq\ 2\times\ 10^5 $ - $ 1\leq\ p_i\leq\ i $ - $ 1 $ 番目の形式のクエリについて、 - $ 1\leq\ u,v\ \leq\ N $ - $ u\ \neq\ v $ - $ G_S $ 上で頂点 $ v $ からいくつかの辺を辿ることで頂点 $ u $ に到達可能である - $ 2 $ 番目の形式のクエリについて、$ 1\leq\ x\ \leq\ N $ - 入力は全て整数 ### Sample Explanation 1 \- $ 1 $ 個目のクエリの時点で、$ G $ 上で頂点 $ 4 $ からいくつかの辺を辿ることで到達可能な頂点は $ 4 $ のみです。 - $ 3 $ 個目のクエリの時点で、$ G $ 上で頂点 $ 4 $ からいくつかの辺を辿ることで到達可能な頂点は $ 2,3,4,\ 5 $ です。 - $ 5 $ 個目のクエリの時点で、$ G $ 上で頂点 $ 4 $ からいくつかの辺を辿ることで到達可能な頂点は $ 1,2,3,4,5 $ です。