Popular Cows

Interview

Time limit1sMemory limit1024 MB

Summary

Given M directed pairs (A, B) meaning cow A thinks cow B is popular, count the cows that every other cow can reach through transitive popularity.

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

Problem

Every cow's dream is to become the most popular cow in the herd. In a herd of $N$ ( $1 \le N \le 10{,}000$ ) cows, you are given up to $M$ ( $1 \le M \le 50{,}000$ ) ordered pairs of the form $(A, B)$ . Each pair says that cow $A$ thinks cow $B$ is popular. Popularity is transitive: if $A$ thinks $B$ is popular and $B$ thinks $C$ is popular, then $A$ also thinks $C$ is popular, even if no pair in the input says so. Compute the number of cows that every other cow considers popular.

Input

The first line contains two space-separated integers $N$ and $M$ . Each of the next $M$ lines contains two space-separated integers $A$ and $B$ , meaning that cow $A$ thinks cow $B$ is popular.

Output

Print a single integer: the number of cows that are considered popular by every other cow.

Hint

Cow 3 is the only cow with high popularity.

Examples1

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