Codeforces Round 786 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

dp

graphs

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Remove Directed Edges

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$?

Input

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.

Output

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

Examples

Input

3 3 1 2 2 3 1 3

Output

2

Input

5 0

Output

1

Input

7 8 7 1 1 3 6 2 2 3 7 2 2 4 7 3 6 3

Output

3

Note

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:

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/19/2024 17:30:00 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|