A14980. 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 < \mathit{in}_v$ or $\mathit{in'}_v = \mathit{in}_v = 0$ ;
- $\mathit{out'}_v < \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$ ?

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.

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$ .

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: