CF1674G.Remove Directed Edges

You are given a directed acyclic graph, consisting of $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$. There are no multiple edges and self-loops.

Let $\mathit{in}_v$ be the number of incoming edges (indegree) and $\mathit{out}_v$ be the number of outgoing edges (outdegree) of vertex $v$.

You are asked to remove some edges from the graph. Let the new degrees be $\mathit{in'}_v$ and $\mathit{out'}_v$.

You are only allowed to remove the edges if the following conditions hold for every vertex $v$:

• $\mathit{in'}_v \lt \mathit{in}_v$ or $\mathit{in'}_v = \mathit{in}_v = 0$;
• $\mathit{out'}_v \lt \mathit{out}_v$ or $\mathit{out'}_v = \mathit{out}_v = 0$.

Let's call a set of vertices $S$ cute if for each pair of vertices $v$ and $u$ ($v \neq u$) such that $v \in S$ and $u \in S$, there exists a path either from $v$ to $u$ or from $u$ to $v$ over the non-removed edges.

What is the maximum possible size of a cute set $S$ after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to $0$?

给你一个有向无环图（DAG），包含 $n$ 个顶点和 $m$ 条边。顶点编号为 $1$ 到 $n$。图中不存在重边和自环。

令 $\mathit{in}_v$ 表示顶点 $v$ 的入度（即指向 $v$ 的边数），$\mathit{out}_v$ 表示顶点 $v$ 的出度（即从 $v$ 出发的边数）。

你需要从图中删除若干条边。设删除后各顶点的新入度和新出度分别为 $\mathit{in'}_v$ 和 $\mathit{out'}_v$。

你仅可在满足以下条件的前提下删除边：对每个顶点 $v$，均需满足：

• $\mathit{in'}_v \lt \mathit{in}_v$ 或 $\mathit{in'}_v = \mathit{in}_v = 0$；
• $\mathit{out'}_v \lt \mathit{out}_v$ 或 $\mathit{out'}_v = \mathit{out}_v = 0$。

我们称顶点集合 $S$ 是“可爱的”（cute），当且仅当对任意两个不同顶点 $v, u$（即 $v \neq u$），若 $v \in S$ 且 $u \in S$，则在未被删除的边构成的子图中，存在一条从 $v$ 到 $u$ 的路径，或存在一条从 $u$ 到 $v$ 的路径。

在满足上述删边约束（即所有顶点的入度和出度要么严格减小，要么保持为 $0$）的前提下，你能得到的“可爱”集合 $S$ 的最大可能大小是多少？

The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$; $0 \le m \le 2 \cdot 10^5$) — the number of vertices and the number of edges of the graph.

Each of the next $m$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$; $v \neq u$) — the description of an edge.

The given edges form a valid directed acyclic graph. There are no multiple edges.

第一行包含两个整数 $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$）—— 描述一条有向边。

给定的边构成一个合法的有向无环图（DAG），且不存在重边。

Print a single integer — the maximum possible size of a cute set $S$ after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to $0$.

输出一个整数——在删除图中的一些边之后，所得到的“可爱”集合 $S$ 的最大可能大小，且所有顶点的入度和出度均不增加（即只能减少或保持为 $0$）。

In the first example, you can remove edges $(1, 2)$ and $(2, 3)$. $\mathit{in} = [0, 1, 2]$, $\mathit{out} = [2, 1, 0]$. $\mathit{in'} = [0, 0, 1]$, $\mathit{out'} = [1, 0, 0]$. You can see that for all $v$ the conditions hold. The maximum cute set $S$ is formed by vertices $1$ and $3$. They are still connected directly by an edge, so there is a path between them.

In the second example, there are no edges. Since all $\mathit{in}_v$ and $\mathit{out}_v$ are equal to $0$, leaving a graph with zero edges is allowed. There are $5$ cute sets, each contains a single vertex. Thus, the maximum size is $1$.

In the third example, you can remove edges $(7, 1)$, $(2, 4)$, $(1, 3)$ and $(6, 2)$. The maximum cute set will be $S = {7, 3, 2}$. You can remove edge $(7, 3)$ as well, and the answer won't change.

Here is the picture of the graph from the third example:

在第一个例子中，你可以删除边 $(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)$，答案不会改变。

以下是第三个例子中图的示意图：