G. Remove Directed Edges
dfs and similar; dp; graphs
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: