无尽漫步

题目描述

给定具有 $N$ 个顶点、$M$ 条边的简单有向图 $G$。顶点编号为顶点 $1$,顶点 $2$,$\ldots$,顶点 $N$。

第 $i$ 条边($1\le i\le M$)从顶点 $U_i$ 指向顶点 $V_i$。

Takahashi 从某个顶点出发,反复沿着有向边在 $G$ 上从一个顶点移动到另一个顶点。

求满足以下条件的顶点个数:从该顶点出发,Takahashi 可以通过精心选择路径无限地继续移动。

输入格式

输入按以下格式从标准输入给出:

N M
U_1 V_1
U_2 V_2
⋮
U_M V_M

输出格式

输出答案。

样例

5 5
1 2
2 3
3 4
4 2
4 5

4

从顶点 $2$ 出发时,Takahashi 可以无限地继续移动:$2\to 3\to 4\to 2\to 3\to\cdots$。从顶点 $3$ 或顶点 $4$ 出发也同样可以。

从顶点 $1$ 出发,可以先移动到顶点 $2$,之后同样可以无限地继续移动。

另一方面,从顶点 $5$ 出发,完全无法移动。

因此,顶点 $1$、$2$、$3$、$4$ 这 4 个顶点满足条件,应输出 $4$。

3 2
1 2
2 1

2

注意,在简单有向图中,同一对顶点之间可能存在两条方向相反的边。另外,$G$ 可能不连通。

数据范围

• $1 \le N \le 2\times 10^5$
• $0 \le M \le \min(N(N-1), 2\times 10^5)$
• $1 \le U_i,V_i \le N$
• $U_i \neq V_i$
• 如果 $i\neq j$,则 $(U_i,V_i)\neq (U_j,V_j)$。
• 输入中的所有值均为整数。