17754번 - 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 個目の整数を T_i とすると，以下のいずれか である．
  1. T_i = 1 のとき．
     • この行には整数 T_i, A_i, B_i が書かれており，次の状態の変更を表す：星 A_i が管理する宇宙船を， 星 B_i へ行くために使われている状態にする．
     • 1 ≤ A_i ≤ N, 1 ≤ B_i ≤ N, A_i ≠ B_i であること，この時点で星 A_i が管理する宇宙船は使われていな い状態にあること，この時点で一般旅客が宇宙船に何回か乗って星 B_i から星 A_i へ行くことは できないことが保証される．
  2. T_i = 2 のとき．
     • この行には整数 T_i, A_i が書かれており，次の状態の変更を表す：星 Ai が管理する宇宙船を，使 われていない状態にする．
     • 1 ≤ A_i ≤ N であること，この時点で星 Ai が管理する宇宙船は使われている状態にあることが保 証される．
  3. T_i = 3 のとき．
     • この行には整数 T_i, A_i, B_i が書かれており，次の質問を表す：この時点で，1 人が星 A_i に，もう 1 人が星 B_i にいるとしたとき，2 人が一般旅客として宇宙船を使って合流することができるか， さらに，合流することができるならば，どの星で合流するのが宇宙船の使用回数が最も少なく なるか．
     • 1 ≤ A_i ≤ N, 1 ≤ B_i ≤ N, A_i ≠ B_i であることが保証される．

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

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

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

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

• N ≤ 5 000．
• Q ≤ 5 000．

• T_i ≠ 2 (1 ≤ i ≤ Q) を満たす．

追加の制限はない．