Proving Equivalences

Time limit2sMemory limit128 MB

Summary

Given a directed graph of proven implications, find the minimum number of edges to add so every node becomes mutually reachable (classic SCC condensation + max(sources, sinks) technique).

Level: Medium6 of 10
Topics: Graph, Union-find, Greedy
Solved: No attempts yet

Problem

The great mathematician Kim Seon-yeong, while writing a linear algebra textbook, came up with the following problem.

For an $N \times N$ matrix $A$ , prove that the following statements are equivalent.

$A$ is invertible.
For every $N \times 1$ matrix $b$ , $Ax = b$ has a unique solution.
For every $N \times 1$ matrix $b$ , $Ax = b$ has a solution.
$Ax = 0$ has only the solution $x = 0$ .

A common way to solve such a problem is to use a chain of implications. For example, one may argue as follows.

(1) implies (2), (2) implies (3), (3) implies (4), and finally (4) implies (1). These four implications show that all four statements are equivalent.

Another way is to prove that (1) implies (2) and (2) implies (1), so that (1) and (2) are equivalent, and likewise prove that (2) and (3) are equivalent, and that (3) and (4) are equivalent. However, this needs as many as six implications.

Since Kim Seon-yeong must prove countless statements equivalent while writing the textbook, such inefficiency is fatal. Let us help prove equivalences using as few implications as possible.

In general, you are given $n$ statements and $m$ already-proven implications. Each implication means "if statement $s_1$ is true, then statement $s_2$ is also true." Find the minimum number of additional implications that must be proven so that all given statements become equivalent (that is, if any one of them is true, all the others are true as well).

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ).

Each test case is given as follows.

The first line contains the number of statements $n$ ( $1 \le n \le 20000$ ) and the number of already-proven implications $m$ ( $0 \le m \le 50000$ ), separated by a space.
Each of the next $m$ lines contains two integers $s_1$ and $s_2$ ( $1 \le s_1, s_2 \le n$ , $s_1 \ne s_2$ ), denoting an already-proven implication "if statement $s_1$ is true, then statement $s_2$ is also true."

Output

For each test case, print a single integer on its own line.

Print the minimum number of additional implications that must be proven so that all given statements become equivalent.

Examples6

Example 1
Input
```
2
4 0
3 2
1 2
1 3
```
Expected output
```
4
2
```
Example 2
Input
```
1
1 0
```
Expected output
```
0
```
Example 3
Input
```
1
3 3
1 2
2 3
3 1
```
Expected output
```
0
```
Example 4
Input
```
1
4 3
1 2
2 3
3 4
```
Expected output
```
1
```
Example 5
Input
```
1
2 0
```
Expected output
```
2
```
Example 6
Input
```
1
5 4
1 3
1 4
2 4
2 5
```
Expected output
```
3
```