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


-----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:

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Graph algorithms

Graph traversal


Solutions:
from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(m)]
inv = [0] * n
outv = [0] * n
for i in range(m):
	graph[i][0] -= 1
	graph[i][1] -= 1
	inv[graph[i][0]] += 1
	outv[graph[i][1]] += 1
S = set()
for (u, v) in graph:
	if inv[u] > 1 and outv[v] > 1:
		g[u].append(v)
	else:
		S.add((u, v))
for (a, b) in S:
	inv[a] -= 1
	outv[b] -= 1
q = deque()
for i in range(n):
	if outv[i] <= 0:
		q.append(i)
dp = [0] * n
while q:
	node = q.pop()
	for nextNode in g[node]:
		dp[nextNode] = max(dp[nextNode], dp[node] + 1)
		outv[nextNode] -= 1
		if outv[nextNode] == 0:
			q.appendleft(nextNode)
print(max(dp) + 1)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
ab = [list(map(int, input().split())) for _ in range(m)]
inv = [0] * n
outv = [0] * n
for i in range(m):
	ab[i][0] -= 1
	ab[i][1] -= 1
	inv[ab[i][0]] += 1
	outv[ab[i][1]] += 1
S = set()
for (a, b) in ab:
	if inv[a] > 1 and outv[b] > 1:
		g[a].append(b)
	else:
		S.add((a, b))
for (a, b) in S:
	inv[a] -= 1
	outv[b] -= 1
go = deque()
for i in range(n):
	if outv[i] <= 0:
		go.append(i)
dp = [0] * n
while go:
	node = go.pop()
	for nex in g[node]:
		dp[nex] = max(dp[nex], dp[node] + 1)
		outv[nex] -= 1
		if outv[nex] == 0:
			go.appendleft(nex)
print(max(dp) + 1)