define君は N 頂点 M 辺の単純とも連結とも限らない有向グラフを持っており， 頂点には 1, 2, \cdots N の番号が，辺には 1, 2, \cdots M の番号がついている．
有向辺 i は 頂点 A_i から 頂点 B_i へと張られている．

彼は以下の操作を任意の回数行える．

1. 頂点 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. 選んだ 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 以下

小課題

1. (25 点) N=2
2. (25 点) M \leq 2
3. (25 点) M = N, A_i = i ， 各 i (1 \leq i \leq N) について B_j = i を満たす j は 1 つ
4. (25 点) M = N-1, A_i = i+1,B_i < A_i
5. (100 点) M = N, A_i = i
6. (200 点) 追加の制約はない．

入力例 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. 1 → 3, 3 → 6 を消し，1 → 6 を追加する．この時，1 → 6 は 2 本ある．
2. 1 → 6, 6 → 2 を消し，1 → 2 を追加する．なお，1 → 6 はまだ 1 本ある．
3. 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 の制約のみを満たす．