AT_pakencamp_2020_day2_c A + B

定义：有一个有向图，包含 $N$ 个顶点和 $M$ 条边，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。 操作：可以任意次数执行以下操作： - 选择一个顶点 $A(1 \le A \le N)$ 和另一个顶点 $B(1 \le B \le N,A \le B)$，移除从 $A$ 到 $B$ 的一条边，同时移除从 $B$ 到另一个顶点 $C(1 \le C \le N,B \ne C)$ 的一条边。 - 如果 $A \ne C$，则添加一条从 $A$ 到 $C$ 的边。 问题：经过一系列操作后，剩余的边的数量最少是多少？

第一行包含一个整数 $T$，表示测试用例的数量。 接下来 $T$ 行，每行描述一个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $M$，表示顶点和边的数量。 接下来 $M$ 行，描述 $M$ 条边，每行包含两个整数 $A$ 和 $B$，表示从顶点 $A$ 到顶点 $B$ 存在一条边。

对于每个测试样例，输出一个整数，表示剩余边的最少数量。

### 制約 - 入力は全て整数である． - $ 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 の制約のみを満たす．