给定一个有向无环图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。顶点编号从 $$$1$$$ 到 $$$n$$$。不存在重边和自环。
令 $$$\mathit{in}_v$$$ 为传入边的数量(入度),$$$\mathit{out}_v$$$ 为顶点 $$$v$$$ 的传出边的数量(出度)。
系统会要求您从图中删除一些边。令新度数为 $$$\mathit{in'}_v$$$ 和 $$$\mathit{out'}_v$$$。
仅当每个顶点 $$$v$$$ 满足以下条件时,才允许删除边:
- $$$\mathit{in'}_v < \mathit{in}_v$$$ 或 $$$\mathit{in'}_v = \mathit{in}_v = 0$$$;
- $$$\mathit{out'}_v < \mathit{out}_v$$$ 或 $$$\mathit{out'}_v = \mathit{out}_v = 0$$$。
如果对于每对顶点 $$$v$$$ 和 $$$u$$$ ($$$v \neq u$$$) 使得 $$$v \in S$$$ 和 $$$u \in S$$$ 存在一条从 $$$v$$$ 到 $$$u$$$ 或从$$$u$$$ 到 $$$v$$$ 在未删除的边缘上。
从图中删除一些边并且所有顶点的入度和出度都减小或保持等于 $$$0$$$ 后,可爱集 $$$S$$$ 的最大可能大小是多少?
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le m \le 2 \cdot 10^5$$$) — 图的顶点数和边数。
接下来的 $$$m$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) - 边的描述。
给定的边形成有效的有向无环图。不存在多重边。
输出
打印单个整数 - 从图中删除一些边并且所有顶点的入度和出度都减小或保持等于 $$$0$$$ 后可爱集合 $$$S$$$ 的最大可能大小。
示例
输入 #1
3 3 1 2 2 3 1 3
输出 #1
2
输入 #2
5 0
输出 #2
1
输入 #3
7 8 7 1 1 3 6 2 2 3 7 2 2 4 7 3 6 3
输出 #3
3
注意
在第一个示例中,您可以删除边 $$$(1, 2)$$$ 和 $$$(2, 3)$$$。 $$$\mathit{in} = [0, 1, 2]$$$,$$$\mathit{out} = [2, 1, 0]$$$。 $$$\mathit{in'} = [0, 0, 1]$$$,$$$\mathit{out'} = [1, 0, 0]$$$。您可以看到,对于所有 $$$v$$$ 条件都成立。最大可爱集$$$S$$$由顶点$$$1$$$和$$$3$$$组成。它们仍然通过边直接连接,因此它们之间有一条路径。
在第二个示例中,没有边缘。由于所有 $$$\mathit{in}_v$$$ 和 $$$\mathit{out}_v$$$ 都等于 $$$0$$$,因此允许保留零边的图。有 $$$5$$$ 可爱的集合,每个集合都包含一个顶点。因此,最大大小为 $$$1$$$。
在第三个示例中,您可以删除边 $$$(7, 1)$$$、$$$(2, 4)$$$、$$$(1, 3)$$$ 和 $$$(6, 2)$$$。最大可爱集将为 $$$S = \{7, 3, 2\}$$$。您也可以删除边 $$$(7, 3)$$$,答案不会改变。
这是第三个示例中的图表图片: