AT_pakencamp_2020_day2_c A + B

[problemUrl]: https://atcoder.jp/contests/pakencamp-2020-day2/tasks/pakencamp_2020_day2_c 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 $ 本張る． 適切に操作をした時，最終的に残る辺の本数は最少で何本になるか？ $ T $ 件のテストケースそれぞれについて求めよ．

入力は以下の形式で標準入力から与えられる。 **各入力データ**について，以下の形式で入力が与えられる． > $ T $ ($ 1\ $件目のテストケースの情報) ($ 2\ $件目のテストケースの情報) $ \vdots $ ($ T\ $件目のテストケースの情報) **各テストケース**について，以下の形式で入力が与えられる． > $ N\ M $ $ A_1\ B_1 $ $ A_2\ B_2 $ $ \vdots $ $ A_M\ B_M $

$ T $ 行に渡って標準出力に出力せよ． $ i $ 行目には，$ i $ 個目のテストケースにおける答えを出力せよ．

### 制約 - 入力は全て整数である． - $ 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 $ 5. ($ 100 $ 点) $ M\ =\ N,\ A_i\ =\ i $ 6. ($ 200 $ 点) 追加の制約はない． ### Sample Explanation 1 1 → 2, 2 → 1 を選び，消すのが最適である．この入力は小課題 1, 2, 3, 5, 6 の制約を満たす． ### Sample Explanation 2 3 → 2, 2 → 1 を消し，3 → 1 を追加するのが最適である．この入力は小課題 4, 6 の制約を満たす． ### Sample Explanation 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 を追加する． この入力は小課題 6 の制約のみを満たす． ### Sample Explanation 4 この入力は小課題 6 の制約のみを満たす．