시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 1 1 1 100.000%

문제

宇宙の遥か彼方,とある銀河には,文明が発達した 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.

예제 입력 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