Dominos

Interview

Time limit1sMemory limit256 MB

Summary

Given a directed graph of domino toppling relations, find the minimum number of blocks to push by hand so that all blocks fall.

Level: Medium4 of 10
Topics: Graph, DFS, Implementation
Solved: No attempts yet

Problem

Dominos are fun. If you stand domino blocks in a long line and topple one of them, that block topples the next, which topples the one after it, and so on, so that the whole line falls in a chain reaction. Sometimes, however, the blocks are arranged so that one block does not topple another; in that case the next block must be toppled by hand.

Given the arrangement of the domino blocks (which blocks topple which when they fall), find the minimum number of blocks you must topple by hand so that every block falls.

Input

The first line contains the number of test cases.

The first line of each test case contains two integers $N$ and $M$ , both at most $100000$ . $N$ is the number of domino blocks and $M$ is the number of relations. The blocks are numbered with integers from $1$ to $N$ . Each of the next $M$ lines contains two integers $x$ and $y$ , meaning that if block $x$ falls, block $y$ also falls.

Output

For each test case, output a single integer on its own line: the minimum number of domino blocks that must be toppled by hand.

Examples2

Example 1
Input
```
1
3 2
1 2
2 3
```
Expected output
```
1
```
Example 2
Input
```
1
3 3
1 2
2 3
3 1
```
Expected output
```
1
```