Problem Description

Define-kun has a directed graph that may not be simple or connected, with $ N $ vertices and $ M $ edges. The vertices are numbered $1, 2, \cdots, N$, and the edges are numbered $1, 2, \cdots, M$. The directed edge $ i $ goes from vertex $ A_i $ to vertex $ B_i $.

He can perform the following operation any number of times:

1. Select one edge from vertex $ A $ ($1 \leq A \leq N$) to vertex $ B $ ($1 \leq B \leq N, A \neq B$) and one edge from vertex $ B $ to vertex $ C $ ($1 \leq C \leq N, B \neq C$).
2. Delete these two selected edges, and if $A \neq C$, add a new directed edge from vertex $ A $ to vertex $ C $.

By performing the operations appropriately, what is the minimum number of edges that can remain? For each of the $ T $ test cases, find the answer.

Input Format

The input is given from the standard input in the following format:

For each input data, the input is given in the following format:

$ T $ (information for the 1st test case) (information for the 2nd test case) $\vdots$ (information for the $ T $th test case)

For each test case, the input is given in the following format:

$N\ M$ $A_1\ B_1$ $A_2\ B_2$ $\vdots$ $A_M\ B_M$

Output Format

Output $ T $ lines to the standard output.
The $ i $th line should contain the answer for the $ i $th test case.

Sample Input and Output

Sample Input #1

1
2 2
1 2
2 1

Sample Output #1

0

Sample Input #2

1
4 3
2 1
3 2
4 1

Sample Output #2

2

Sample Input #3

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

Sample Output #3

3

Sample Input #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

Sample Output #4

1
4

Notes/Hints

Constraints

• All input values are integers.
• $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$
• The sum of $ N $ and $ M $ across all $ T $ test cases is at most $ 10^6 $.

Note that the given directed graph may contain multiple edges.

Subtasks

1. ($ 25 $ points) $ N = 2 $
2. ($ 25 $ points) $M \leq 2$
3. ($ 25 $ points) $ M = N, A_i = i $, for each $ i $ ($1 \leq i \leq N$), there is exactly one $ j $ such that $ B_j = i $
4. ($ 25 $ points) $ M = N - 1, A_i = i + 1, B_i $
5. ($ 100 $ points) $ M = N, A_i = i $
6. ($ 200 $ points) No additional constraints.

Sample Explanation 1

Choosing 1 → 2 and 2 → 1 and deleting them is optimal. This input satisfies the constraints of subtasks 1, 2, 3, 5, and 6.

Sample Explanation 2

Deleting 3 → 2 and 2 → 1 and adding 3 → 1 is optimal. This input satisfies the constraints of subtasks 4 and 6.

Sample Explanation 3

For example, the following operations are optimal:
1. Delete 1 → 3 and 3 → 6, add 1 → 6. At this point, there are two 1 → 6 edges.
2. Delete 1 → 6 and 6 → 2, add 1 → 2. Note that there is still one 1 → 6 edge left.
3. Delete 1 → 2 and 2 → 5, add 1 → 5. This input satisfies only the constraints of subtask 6.

Sample Explanation 4

This input satisfies only the constraints of subtask 6.

见题面 Input 部分

见题面 Output 部分