宇宙の遥か彼方，とある銀河には，文明が発達した $N$ 個の星がある．星には $1$ から $N$ までの番号がついている．それぞれの星は 1 つの宇宙船を管理している．宇宙船は，ある他の星へ行くために使われている状態，または，使われていない状態のいずれかにある．星 $a$ が管理する宇宙船が星 $b$ へ行くために使われている状態にあるとするとき，宇宙船は星 $a$ と星 $b$ の間を何回も往復している．宇宙船が星 $a$ から星 $b$ へ行くとき，一般旅客は宇宙船に乗って星 $a$ から星 $b$ へ行くことができるが，宇宙船が星 $b$ から星 $a$ へ戻るときは，燃料の問題や荷物をのせるなどの都合により，一般旅客は乗船できない．また，星 $a$ が管理する宇宙船が使われていない状態にあるとき，その宇宙船は星 $a$ で待機している．

今，すべての宇宙船が使われていない状態にある．今後の宇宙船の状態の変更のスケジュールが決まっている．状態の変更は，次のいずれかの種類である．

• 使われていない状態にある星 $a$ が管理する宇宙船を，星 $b$ へ行くために使われている状態にする．ただし，これは一般旅客が宇宙船に何回か乗って星 $b$ から星 $a$ へ行くことができないときにのみ行われる．
• 使われている状態にある星 $a$ が管理する宇宙船を，使われていない状態にする．

この銀河を旅行する計画を立てているある 2 人は，待ち合わせの予定を考えるため，次の形式の質問を何個か用意した．

• スケジュールのある時点で，1 人が星 $a$ に，もう 1 人が星 $b$ にいるとしたとき，2 人が一般旅客として宇宙船を使って合流することができるか，さらに，合流することができるならば，どの星で合流するのが宇宙船の使用回数が最も少なくなるか．すなわち，星 $c$ であって，一般旅客が宇宙船に何回か乗って星 $a$ から星 $c$ へも星 $b$ から星 $c$ へも行くことができるようなものは存在するか，さらに，存在するならば，星 $a$ から星 $c$ へ行くための宇宙船の使用回数と星 $b$ から星 $c$ へ行くための宇宙船の使用回数の合計を最小にするような星 $c$ はどれか．

優秀なプログラマであるあなたは，2 人の質問すべてに対する答えを求めることを求められた．

課題

今後の宇宙船の状態の変更のスケジュールと質問が時系列順に与えられたとき，質問に答えるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には整数 $N,Q$ が空白を区切りとして書かれており，星の個数が $N$，状態の変更の回数と質問の個数の合計が $Q$ であることを表す．
• 続く $Q$ 行は状態の変更と質問を時系列順に表している．これらのうちの $i$ 行目（$1\le i\le Q$）には 2 個または 3 個の整数が空白を区切りとして書かれている．1 個目の整数を $T_i$ とすると，以下のいずれかである．

(i) $T_i=1$ のとき

この行には整数 $T_i,A_i,B_i$ が書かれており，次の状態の変更を表す：星 $A_i$ が管理する宇宙船を，星 $B_i$ へ行くために使われている状態にする．

$1\le A_i\le N$，$1\le B_i\le N$，$A_i\ne B_i$ であること，この時点で星 $A_i$ が管理する宇宙船は使われていない状態にあること，この時点で一般旅客が宇宙船に何回か乗って星 $B_i$ から星 $A_i$ へ行くことはできないことが保証される．

(ii) $T_i=2$ のとき

この行には整数 $T_i,A_i$ が書かれており，次の状態の変更を表す：星 $A_i$ が管理する宇宙船を，使われていない状態にする．

$1\le A_i\le N$ であること，この時点で星 $A_i$ が管理する宇宙船は使われている状態にあることが保証される．

(iii) $T_i=3$ のとき

この行には整数 $T_i,A_i,B_i$ が書かれており，次の質問を表す：この時点で，1 人が星 $A_i$ に，もう 1 人が星 $B_i$ にいるとしたとき，2 人が一般旅客として宇宙船を使って合流することができるか，さらに，合流することができるならば，どの星で合流するのが宇宙船の使用回数が最も少なくなるか．

$1\le A_i\le N$，$1\le B_i\le N$，$A_i\ne B_i$ であることが保証される．

出力

標準出力に，それぞれの質問ごとに，

• 合流することができるならば，宇宙船の使用回数を最も少なくするための合流する星の番号，
• 合流することができないならば，整数 $-1$

を順に 1 行ずつ出力せよ．

制約

すべての入力データは以下の条件を満たす．

• $2\le N\le1\,000\,000$．
• $1\le Q\le1\,000\,000$．

小課題

小課題 1 [10 点]

以下の条件を満たす．

• $N\le5\,000$．
• $Q\le5\,000$．

小課題 2 [30 点]

• $T_i\ne2$（$1\le i\le Q$）を満たす．

小課題 3 [60 点]

追加の制限はない．

入出力例

入力 1

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

出力 1

-1
4

注記

この例では，状態の変更と質問は順に以下のようになっている．

• 星 $2$ が管理する宇宙船が，星 $4$ へ行くために使われる状態になる．
• この時点で 2 人が星 $2$ と星 $6$ にいた場合，合流することはできないので，$-1$ を出力する．
• 星 $4$ が管理する宇宙船が，星 $3$ へ行くために使われる状態になる．
• 星 $6$ が管理する宇宙船が，星 $4$ へ行くために使われる状態になる．
• この時点で 2 人が星 $2$ と星 $6$ にいた場合，星 $3$ または星 $4$ で合流することができる．使用する宇宙船の回数を最小にするためには星 $4$ で合流するべきであるため，$4$ を出力する．

入力 2

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

出力 2

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6