/
実行時間制限: 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