시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB108423538.889%

문제

IOI 国は,N 個の都市からなる国である.これらの都市には 1, 2, . . . , N の番号がついている.JOI 教授 は,IOI 国の道路網が整備された過程について興味を持った.

JOI 教授が,IOI 国の歴史に関する資料を調べたところ,以下のことが分かった.

  • IOI 国の都市は建国直後から現在まで同じである.IOI 国の建国直後には都市を結ぶ道路は一つもな かった.
  • IOI 国の建国 i 年後 (1 ≦ i ≦ Q) には,都市 Ai と都市 Bi の間の交通状況の改善計画が立てられた.
  • 計画された改善計画のうちのいくつかは計画通り実行されたが,実行されずに放棄された計画もある.
  • どの改善計画が実行されたかは,資料から明らかになっている.
  • 実行された改善計画は,すべて 1 年以内に実行が完了した.

また,別の文献から,都市 Ai と都市 Bi の間の交通状況の改善計画は次のようなものであることが分 かった.

  • 改善計画が立てられた時点で建設済みの道路を用いて都市 Ai から都市 Bi に移動できない場合は,都 市 Ai と都市 Bi を双方向に結ぶ道路を新たに建設する.新たに建設された道路は未舗装である.
  • 改善計画が立てられた時点で建設済みの道路を用いて都市 Ai から都市 Bi に移動できる場合は,その ような経路のうち用いる道路の本数が最小となるものについて,その経路に含まれる未舗装の道路 をすべて舗装する.用いる道路の本数が最小となる経路が複数ある場合は,それらの経路すべてに対 して同じように未舗装の道路を舗装する.一度舗装した道路を,もう一度舗装することはない.

JOI 教授は,さらなる調査のため,実行されずに放棄された改善計画それぞれに対して,もしその改善 計画のみが追加で実行されていたら,その改善計画において何本の道路を舗装することになっていたかを 計算することにした.

IOI 国の交通状況の改善計画とその実行状況が与えられたとき,実行されずに放棄された改善計画それ ぞれに対して,もしその改善計画が実行されていたら,その改善計画において何本の道路を舗装すること になっていたかを計算するプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N, Q が空白を区切りとして書かれている.これは,IOI 国に都市が N 個あり,JOI 教授が建国から Q 年間の交通状況の改善計画に注目していることを表す.
  • 続く Q 行のうちの i 行目 (1 ≦ i ≦ Q) には,3 つの整数 Ti , Ai, Bi が空白を区切りとして書かれている. 整数 Ti は,建国 i 年後に立てられた改善計画の実行状況を表し,Ti = 1 の時はその改善計画が実行 されたことを,Ti = 2 の時はその改善計画が実行されずに放棄されたことを表す.また,整数 Ai, Bi は,建国 i 年後に都市 Ai と都市 Bi の間の交通状況の改善計画が立てられたことを表す.

출력

標準出力に,実行されずに放棄された改善計画それぞれに対し,もしその改善計画が実行されていたら, その改善計画において舗装することになる道路の本数を 1 行で出力せよ.ただし,その改善計画を実行す ると新しい道路が建設される場合は,-1 を出力せよ.

제한

  • 2 ≦ N ≦ 100 000.
  • 1 ≦ Q ≦ 300 000.
  • 1 ≦ Ti ≦ 2 (1 ≦ i ≦ Q).
  • 1 ≦ Ai ≦ N (1 ≦ i ≦ Q).
  • 1 ≦ Bi ≦ N (1 ≦ i ≦ Q).
  • Ai ≠ Bi (1 ≦ i ≦ Q).

서브태스크 1 (10점)

  • N ≦ 1 000.
  • Q ≦ 3 000.

서브태스크 2 (25점)

  • Ti = 1 (1 ≦ i ≦ P) および Ti = 2 (P + 1 ≦ i ≦ Q) を満たす整数 P (1 ≦ P ≦ Q − 1) が存在する.

서브태스크 3 (25점)

  • Ti = 1 を満たすすべての i (1 ≦ i ≦ Q) に対して,次のいずれかが成り立つ.
  • 建国 i 年後の改善計画を実行する直前の時点で,建設済みの道路を用いて都市 Ai から都市 Bi に 移動できない.
  • 建国 i 年後の改善計画を実行する直前の時点で,建設済みの道路のうち 200 本以下の道路を用 いて都市 Ai から都市 Bi へ移動できる.

서브태스크 4 (25점)

  • Ti = 2 を満たす i (1 ≦ i ≦ Q) は 200 個以下である.

서브태스크 5 (15점)

追加の制限はない.

예제 입력 1

3 7
1 1 2
2 2 1
2 2 3
1 2 1
2 1 2
1 2 3
2 1 3

예제 출력 1

1
-1
0
1

この入力例の場合, IOI 国の交通状況の改善計画は以下のように実行されたことになる.

  • IOI 国には 3 個の都市があり,建国直後にはそれらを結ぶ道路はなかった.
  • 建国 1 年後に都市 1 と都市 2 の間の交通状況の改善計画が実行された.この時点で建設済みの道路 を用いて都市 1 から都市 2 に移動することができないので,この計画により,これらの都市の間に 道路が建設された.
  • 建国 2 年後に都市 2 と都市 1 の間の交通状況の改善計画が立てられたが,実行されずに放棄された. この時点で建設済みの道路を 1 本用いて都市 2 から都市 1 に移動することができ,その道路は舗装 されていないので,この改善計画に対応した出力として 1 を出力する.
  • 建国 3 年後に都市 2 と都市 3 の間の交通状況の改善計画が立てられたが,実行されずに放棄された. この時点で建設済みの道路を用いて都市 2 から都市 3 に移動することができないので,この改善計 画に対応した出力として -1 を出力する.
  • 建国 4 年後に都市 2 と都市 1 の間の交通状況の改善計画が実行された.この時点で建設済みの道路 を用いて都市 2 から都市 1 に移動することができるので,この計画により,これらの都市を結ぶ道 路が舗装された.
  • 建国 5 年後に都市 1 と都市 2 の間の交通状況の改善計画が立てられたが,実行されずに放棄された. この時点で建設済みの道路を 1 本用いて都市 1 から都市 2 に移動することができ,その道路は舗装 されているので,この改善計画に対応した出力として 0 を出力する.
  • 建国 6 年後に都市 2 と都市 3 の間の交通状況の改善計画が実行された.この時点で建設済みの道路 を用いて都市 2 から都市 3 に移動することができないので,この計画により,これらの都市の間に 道路が建設された.
  • 建国 7 年後に都市 1 と都市 3 の間の交通状況の改善計画が立てられたが,実行されずに放棄された. この時点で建設済みの道路を 2 本用いて都市 1 から都市 3 に行くことができ,そのうち 1 本だけが 舗装されていないので,この改善計画に対応した出力として 1 を出力する.

예제 입력 2

6 8
1 1 3
1 6 1
1 2 5
2 3 6
1 3 6
1 4 1
2 4 3
2 2 5

예제 출력 2

2
1
1

예제 입력 3

7 11
1 5 1
1 6 2
1 1 3
1 3 5
1 5 7
1 4 5
1 4 1
2 1 3
2 3 7
2 4 3
2 5 6

예제 출력 3

0
1
0
-1

채점 및 기타 정보

  • 예제는 채점하지 않는다.