题目描述

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

题目大意

给定一张点数为 $N$ 的有向图，初始 $p_i(1\leq p_i \leq i,1 \leq i < N)$ 连向 $i+1$。

$Q$ 次操作，有两种：

• 1 u v：$u$ 向 $v$ 连一条有向边，保证最开始时 $v$ 能到达 $u$，$u \ne v$。
• 2 x：询问 $x$ 能到达的点中编号最小的点。

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

4
2
1

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

提示

制約

• $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$ です。