Description

Every cow dreams of becoming the star of the barn. A cow that is liked by all cows is a star cow. All cows are self-obsessed; each cow always likes itself. The “likes” relation is transitive—if $A$ likes $B$, and $B$ likes $C$, then $A$ also likes $C$. There are $N$ cows in the barn. Given some admiration relationships between cows, please compute how many cows can be stars.

Input Format

The first line contains two space-separated integers: $N$ and $M$. The next $M$ lines: each line contains two space-separated integers: $A$ and $B$, meaning $A$ likes $B$.

Output Format

Output a single integer on one line, the number of star cows.

3 3
1 2
2 1
2 3

1

Hint

Only cow number $3$ can be a star.

Constraints

• For $10\%$ of the testdata, $N \le 20$, $M \le 50$.
• For $30\%$ of the testdata, $N \le 10^3$, $M \le 2 \times 10^4$.
• For $70\%$ of the testdata, $N \le 5 \times 10^3$, $M \le 5 \times 10^4$.
• For $100\%$ of the testdata, $1 \le N \le 10^4$, $1 \le M \le 5 \times 10^4$.

Translated by ChatGPT 5