3 - 宇宙船 (Spaceships) 解説 /

実行時間制限: 10 sec / メモリ制限: 256 MiB

配点 : 100 点

問題文

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

(i) T_{i} = 1 のとき.

この行には整数 T_{i}, A_{i}, B_{i} が書かれており,次の状態の変更を表す:星 A_{i} が管理する宇宙船を,星 B_{i} へ行くために使われている状態にする.

1 \leqq A_{i} \leqq N,1 \leqq B_{i} \leqq N,A_{i} \ne B_{i} であること,この時点で星 A_{i} が管理する宇宙船は使われていない状態にあること,この時点で一般旅客が宇宙船に何回か乗って星 B_{i} から星 A_{i} へ行くことはできないことが保証される.

(ii) T_{i} = 2 のとき.

この行には整数 T_{i}, A_{i} が書かれており,次の状態の変更を表す:星 A_{i} が管理する宇宙船を,使われていない状態にする.

1 \leqq A_{i} \leqq N であること,この時点で星 A_{i} が管理する宇宙船は使われている状態にあることが保証される.

(iii) T_{i} = 3 のとき.

この行には整数 T_{i}, A_{i}, B_{i} が書かれており,次の質問を表す:この時点で,1 人が星 A_{i} に,もう 1 人が星 B_{i} にいるとしたとき,2 人が一般旅客として宇宙船を使って合流することができるか,さらに,合流することができるならば,どの星で合流するのが宇宙船の使用回数が最も少なくなるか.

1 \leqq A_{i} \leqq N,1 \leqq B_{i} \leqq N,A_{i} \ne B_{i} であることが保証される.

出力

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

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

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

制約

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

  • 2 \leqq N \leqq 1\,000\,000.
  • 1 \leqq Q \leqq 1\,000\,000.

小課題

小課題 1 [10 点]

以下の条件を満たす.

  • N \leqq 5\,000.
  • Q \leqq 5\,000.

小課題 2 [30 点]

  • T_{i} \ne 2 (1 \leqq i \leqq 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

出典

JOI 2012/2013 春季トレーニング合宿 Contest Day4