1つの頂点からなる根付き木が $N$ 個ある。頂点には $1$ から $N$ までの番号が付けられている。

以下のクエリを実行するプログラムを作成せよ。

• 1 u v: u と v の間に辺を1本追加する。このとき、v が u の親となる。クエリが実行される前に、u は u が属する木の根であり、u と v は異なる木に属していることが保証される。
• 2 v: v と v の親を結ぶ辺を切断する。v は根ではない。
• 3 u v: u と v の LCA を出力する。u と v は同じ木の中にある。

入力

最初の行に $N$ ($2 \le N \le 100{,}000$) とクエリの個数 $M$ ($1 \le M \le 200{,}000$) が与えられる。

続く $M$ 行には、クエリが1行に1つずつ与えられる。

出力

各 3 番クエリの結果を順番に1行に1つずつ出力する。

入出力例

入力例 1

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

出力例 1

1
2
3
2