実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
define君は N 頂点 M 辺の単純とも連結とも限らない有向グラフを持っており,
頂点には 1, 2, \cdots N の番号が,辺には 1, 2, \cdots M の番号がついている.
有向辺 i は 頂点 A_i から 頂点 B_i へと張られている.
彼は以下の操作を任意の回数行える.
- 頂点 A (1 \leq A \leq N) から頂点 B (1 \leq B \leq N, A \neq B) を結ぶ辺と, 頂点 B から頂点 C (1 \leq C \leq N, B \neq C) を結ぶ辺をそれぞれ 1 本選ぶ.
- 選んだ 2 本の辺を消し,A \neq C の場合は新たに頂点 A から 頂点 C に有向辺を 1 本張る.
制約
- 入力は全て整数である.
- 1 \leq T \leq 100
- 2 \leq N \leq 10^6
- 1 \leq M \leq 10^6
- 1 \leq A_i,B_i \leq N
- A_i \neq B_i
- T 件のテストケースに含まれる N,M の総和はそれぞれ 10^6 以下
小課題
- (25 点) N=2
- (25 点) M \leq 2
- (25 点) M = N, A_i = i , 各 i (1 \leq i \leq N) について B_j = i を満たす j は 1 つ
- (25 点) M = N-1, A_i = i+1,B_i < A_i
- (100 点) M = N, A_i = i
- (200 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられる。
各入力データについて,以下の形式で入力が与えられる.
T (1\ 件目のテストケースの情報) (2\ 件目のテストケースの情報) \vdots (T\ 件目のテストケースの情報)
各テストケースについて,以下の形式で入力が与えられる.
N \ \ M A_1 \ \ B_1 A_2 \ \ B_2 \vdots A_M \ \ B_M
出力
T 行に渡って標準出力に出力せよ.
i 行目には,i 個目のテストケースにおける答えを出力せよ.
入力例 1
1 2 2 1 2 2 1
出力例 1
0
1 → 2, 2 → 1 を選び,消すのが最適である.この入力は小課題 1, 2, 3, 5, 6 の制約を満たす.
入力例 2
1 4 3 2 1 3 2 4 1
出力例 2
2
3 → 2, 2 → 1 を消し,3 → 1 を追加するのが最適である.この入力は小課題 4, 6 の制約を満たす.
入力例 3
1 6 6 1 3 3 6 1 6 6 2 2 4 2 5
出力例 3
3
例えば,以下のように操作すると最適である.
- 1 → 3, 3 → 6 を消し,1 → 6 を追加する.この時,1 → 6 は 2 本ある.
- 1 → 6, 6 → 2 を消し,1 → 2 を追加する.なお,1 → 6 はまだ 1 本ある.
- 1 → 2, 2 → 5 を消し,1 → 5 を追加する.
入力例 4
2 6 13 2 5 2 4 2 6 4 6 3 2 3 5 4 2 1 4 1 3 5 1 6 4 6 1 5 2 5 10 3 5 5 3 5 4 4 1 2 1 5 4 5 1 3 5 1 5 5 1
出力例 4
1 4
この入力は小課題 6 の制約のみを満たす.
Writer : define