Spaceships

宇宙の遥か彼方，とある銀河には，文明が発達した 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 ≤ i ≤ Q) には 2 個 または 3 個の整数が空白を区切りとして書かれている．1 個目の整数を Ti とすると，以下のいずれか である．

  1. Ti = 1 のとき．

     • この行には整数 Ti, Ai, Bi が書かれており，次の状態の変更を表す：星 Ai が管理する宇宙船を， 星 Bi へ行くために使われている状態にする．
     • 1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N, Ai ≠ Bi であること，この時点で星 Ai が管理する宇宙船は使われていな い状態にあること，この時点で一般旅客が宇宙船に何回か乗って星 Bi から星 Ai へ行くことは できないことが保証される．

  2. Ti = 2 のとき．

     • この行には整数 Ti, Ai が書かれており，次の状態の変更を表す：星 Ai が管理する宇宙船を，使 われていない状態にする．
     • 1 ≤ Ai ≤ N であること，この時点で星 Ai が管理する宇宙船は使われている状態にあることが保 証される．

  3. Ti = 3 のとき．

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

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

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

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

• 2 ≤ N ≤ 1 000 000．
• 1 ≤ Q ≤ 1 000 000．