← Home
write a go solution for Description:
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 mathitin_v be the number of incoming edges (indegree) and mathitout_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 mathitin'_v and mathitout'_v.

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

- mathitin'_v<mathitin_v or mathitin'_v=mathitin_v=0;
- mathitout'_v<mathitout_v or mathitout'_v=mathitout_v=0.

Let's call a set of vertices S cute if for each pair of vertices v and u (vnequ) such that vinS and uinS, 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?

Input Format:
The first line contains two integers n and m (1<=n<=2*10^5; 0<=m<=2*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<=v,u<=n; vnequ) — the description of an edge.

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

Output Format:
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.

Note:
In the first example, you can remove edges (1,2) and (2,3). mathitin=[0,1,2], mathitout=[2,1,0]. mathitin'=[0,0,1], mathitout'=[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 mathitin_v and mathitout_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:. Output only the code with no comments, explanation, or additional text.