Problem Description

You have traveled to the world of Yu-Gi-Oh!, and now you are dueling against your opponent—a directed graph with $n$ vertices and $m$ edges.

Then I forgot what happened.

A true duelist believes everything is inevitable. To deal with the duel in front of you, you need to know how many vertices $x$ satisfy the following condition.

• For any vertex $y$, it holds that either $x$ can reach $y$ or $y$ can reach $x$ (we consider that a vertex can reach itself).

Input Format

The first line contains two positive integers $n, m$, representing the number of vertices and the number of edges in the given directed graph.

The next $m$ lines each contain two positive integers $x, y$, denoting a directed edge $x \to y$.

Output Format

Output one integer in one line: the answer, i.e., how many vertices satisfy that every vertex can reach it or be reached from it.

4 4
1 2
1 3
2 4
3 4

2

Hint

Explanation for Sample 1

It can be proven that only vertices $1$ and $4$ satisfy the requirement.

Since vertex $3$ cannot reach vertex $2$ and also cannot be reached from vertex $2$, vertices $2$ and $3$ do not satisfy the requirement.

Sample 2

See the attached files gameh2.in and gameh2.ans.

The constraints of this sample are the same as test point $2$.

Sample 3

See the attached files gameh3.in and gameh3.ans.

The constraints of this sample are the same as test point $3$.

Constraints

This problem has $10$ test points. The test points are not evenly distributed, and the score for each test point is as follows.

For all testdata, it is guaranteed that $10 \le n \le 10^6$ and $20 \le m \le 3\times 10^6$.

For odd-numbered test points, it is guaranteed that the given graph has no cycles with more than $1$ distinct vertex.

Hint

The input and output size of this problem is large, so please use fast I/O.

Translated by ChatGPT 5