当前没有测试数据。

F - 无尽之旅

得分：$500$ 分

问题描述

我们有一个有 $N$ 个顶点和 $M$ 条边的简单有向图 $G$，顶点标号为顶点 $1$，顶点 $2$，$\ldots$，顶点 $N$。 第 $i$ 条边 $(1\leq i\leq M)$ 是从顶点 $U_i$ 到顶点 $V_i$。

高滨が顶点开始，并沿着有向边从一个顶点移动到另一个顶点，然后反复移动。 问有多少个顶点满足以下条件：高滨可以从该顶点开始，通过仔细选择路径而无限地继续移动?

约束

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

输入

从标准输入给出的输入如下所示：

$N$ $M$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

输出

输出答案。

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

4

从顶点 $2$ 开始，高滨可以无限地继续移动：$2$ $\to$ $3$ $\to$ $4$ $\to$ $2$ $\to$ $3$ $\to$ $\cdots$ 顶点 $3$ 或顶点 $4$ 的情况也是如此。 从顶点 $1$，他可以先去顶点 $2$，然后再次无限地前进。
另一方面，从顶点 $5$，他无法移动。

因此，满足条件的顶点有四个——顶点 $1$，$2$，$3$ 和 $4$——因此应该输出 $4$。

3 2
1 2
2 1

2

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