配点 : $600$ 点

問題文

$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$ に到達可能である
• $u \neq v$
• $G_S$ 上で頂点 $v$ からいくつかの辺を辿ることで頂点 $u$ に到達可能である
• 2 x : $G$ 上で頂点 $x$ からいくつかの辺を辿ることで到達可能な頂点 (頂点 $x$ を含む) のうち、最も番号が小さい頂点の番号を出力する。

制約

• $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$ に到達可能である
• $1\leq u,v \leq N$
• $u \neq v$
• $G_S$ 上で頂点 $v$ からいくつかの辺を辿ることで頂点 $u$ に到達可能である
• $2$ 番目の形式のクエリについて、$1\leq x \leq N$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$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$ 個目のものに対する答えを出力せよ。

5
1 2 3 3
5
2 4
1 4 2
2 4
1 5 1
2 4

4
2
1

• $1$ 個目のクエリの時点で、$G$ 上で頂点 $4$ からいくつかの辺を辿ることで到達可能な頂点は $4$ のみです。
• $3$ 個目のクエリの時点で、$G$ 上で頂点 $4$ からいくつかの辺を辿ることで到達可能な頂点は $2,3,4, 5$ です。
• $5$ 個目のクエリの時点で、$G$ 上で頂点 $4$ からいくつかの辺を辿ることで到達可能な頂点は $1,2,3,4,5$ です。

7
1 1 2 2 3 3
10
2 5
1 5 2
2 5
1 2 1
1 7 1
1 6 3
2 5
2 6
2 1
1 7 1

5
2
1
1
1