Helping the Transit

Interview

Time limit1sMemory limit1024 MB

Summary

Given N reference points and M one-way streets, find the fewest one-way bridges to add so that every point can reach every other point.

Level: Medium5 of 10
Topics: Graph, DFS, Topological sort
Solved: No attempts yet

Problem

The president of Nlogonia decided, by decree, that all the streets of Nlogonia should be one-way. Because no one planned the change properly, people could not get to work or could not return home from work. The result was chaos and riots in many cities.

The president was impeached, and the new administration hired a team of scientists to solve the problem. The team then hired you, an expert in algorithm complexity, to help compute the solutions efficiently.

Each city has reference points, and one-way streets, each connecting two reference points. Find the minimum number of one-way bridges that must be built to make the city fully connected. Each bridge also connects two reference points.

Input

The first line contains two integers $N$ and $M$ ( $1 ≤ N ≤ 10^4$ , $1 ≤ M ≤ 10^6$ ), where $N$ is the number of reference points and $M$ is the number of streets. Each of the next $M$ lines contains two integers $R$ and $S$ ( $1 ≤ R, S ≤ N$ , $R \ne S$ ), meaning a street runs from $R$ to $S$ . Every vehicle on that street must move away from $R$ toward $S$ .

Output

Print a single line containing the minimum number of bridges needed to make the inhabitants happy.

Examples5

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