王国$$$X$$$中有$$$n$$$个城市,编号从$$$1$$$到$$$n$$$。人们通过一些单向道路在城市之间旅行。作为一名乘客,JATC 发现很奇怪,从任何一个城市 $$$u$$$ 出发,他都无法在其中开始旅行,然后使用王国的道路返回。也就是说,王国可以被视为一个无环图。
由于旅行系统的困扰,JATC 决定去见国王并请他做点什么。作为回应,国王表示他将升级一些城市,以方便出行。由于预算的原因,国王只会升级那些重要或半重要的城市。如果对于每个城市 $$$v \neq u$$$,存在从 $$$u$$$ 到 $$$v$$$ 的路径或从 $$$v$$$ 到 $$$u$$$ 的路径,则称城市 $$$u$$$ 是重要的。如果一座城市 $$$u$$$ 不重要,则该城市被称为半重要城市,并且我们可以恰好摧毁一座城市 $$$v \neq u$$$,从而使 $$$u$$$ 变得重要。
国王一查明所有这些城市就会开始行动。请帮助他加快进程。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 300\,000$$$, $$$1 \le m \le 300\,000$$$) — 城市数量和单向道路数量。
接下来的 $$$m$$$ 行描述了王国的道路系统。其中每个包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$),表示从 $$$u_i$$$ 到 $$$v_i$$$ 的单向道路。
可以保证,王国的道路构成一个非循环图,其中不包含多条边和自环。
输出
打印一个整数——国王必须升级的城市数量。
示例
输入 #1
7 7 1 2 2 3 3 4 4 7 2 5 5 4 6 4
输出 #1
4
输入 #2
6 7 1 2 2 3 3 4 1 5 5 3 2 6 6 4
输出 #2
4
注意
在第一个示例中:
- 从城市 $$$1$$$ 开始,我们可以到达除城市 $$$6$$$ 之外的所有其他城市。另外,从城市 $$$6$$$ 我们无法到达城市 $$$1$$$。因此,如果我们摧毁了城市$$$6$$$,那么城市$$$1$$$就会变得重要。所以$$$1$$$ 是一个半重要城市。
- 对于城市 $$$2$$$,无法到达 $$$2$$$ 且 $$$2$$$ 无法到达的城市集合为 $$$\{6\}$$$。因此,摧毁城市 $$$6$$$ 将使城市 $$$2$$$ 变得重要。所以城市 $$$2$$$ 也是半重要的。
- 对于城市$$$3$$$,集合为$$$\{5, 6\}$$$。正如您所看到的,摧毁城市 $$$5$$$ 或 $$$6$$$ 不会使城市 $$$3$$$ 变得重要。因此,它既不重要也不半重要。
- 对于城市 $$$4$$$,集合为空。所以$$$4$$$是一个重要的城市。
- 城市 $$$5$$$ 的集合为 $$$\{3, 6\}$$$,城市 $$$6$$$ 的集合为 $$$\{3, 5\}$$$。与城市$$$3$$$类似,两者都不重要也不半重要。
- 城市 $$$7$$$ 很重要,因为我们可以从所有其他城市到达它。
在第二个示例中,重要城市是 $$$1$$$ 和 $$$4$$$。半重要城市为$$$2$$$ 和$$$3$$$。