Remove Directed Edges

题意翻译

给出一个 n 点 m 边的有向无环图，你需要从中移除一些边，使得对于每一个点，其入度减少（如果原来有入边），出度也减少（如果原来有出边）。 **当删完边以后**，如果有一个点集，满足对于任两点（i, j）可以从 i 走到 j **或**可以从 j 走到 i，那就称其为可爱的。 现在要构造一种删边方案，使得删边后其中一个可爱的点集最大，输出这个点集大小。 输入数据第一行由两个正整数 n, m 组成，代表 n 个点和 m 条边。第 2 至 m + 1 行包含两个数 u, v，分别表示一条有向边的两个顶点。

题目描述

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

输入输出样例

输入样例 #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

说明

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: