Educational DP Contest - Longest Path

There is a directed graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N, and for each i (1 \leq i \leq M), the i-th directed edge goes from Vertex x_i to y_i. G does not contain directed cycles.

Find the length of the longest directed path in G. Here, the length of a directed path is the number of edges in it.

Constraints

* All values in input are integers.
* 2 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq x_i, y_i \leq N
* All pairs (x_i, y_i) are distinct.
* G does not contain directed cycles.

Input

Input is given from Standard Input in the following format:


N M
x_1 y_1
x_2 y_2
:
x_M y_M


Output

Print the length of the longest directed path in G.

Examples

Input

4 5
1 2
1 3
3 2
2 4
3 4


Output

3


Input

6 3
2 3
4 5
5 6


Output

2


Input

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3


Output

3

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
sys.setrecursionlimit(1000000)
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	g[x].append(y)
dp = [-1] * n

def rec(v):
	if dp[v] != -1:
		return dp[v]
	else:
		res = 0
		for u in g[v]:
			res = max(res, rec(u) + 1)
		dp[v] = res
		return dp[v]
for i in range(n):
	rec(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict
(n, m) = map(int, input().split())
d = defaultdict(list)
for i in range(m):
	(tx, ty) = map(int, input().split())
	d[tx - 1].append(ty - 1)
dp = [0] * n

def dist(i):
	if dp[i] > 0:
		return dp[i]
	dp[i] = 0
	for ni in d[i]:
		dp[i] = max([dp[i], dist(ni) + 1])
	return dp[i]
ans = 0
for i in range(n):
	ans = max(ans, dist(i))
print(ans)


(n, m) = map(int, input().split())
dp = [0] * (n + 1)
e = [set() for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	e[a].add(b)
	dp[b] += 1
q = [0] * (n + 1)
j = 0
for z in range(len(dp)):
	if dp[z] == 0:
		q[j] = z
		j = j + 1
color = 0
i = 1
while i < j:
	end = j
	for qel in range(i, end):
		for w in e[q[qel]]:
			dp[w] -= 1
			if dp[w] == 0:
				q[j] = w
				j = j + 1
	i = end
	color = color + 1
print(color - 1)


import sys
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
e = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	e[a - 1].append(b - 1)

def dfs(x):
	num = 0
	for nex in e[x]:
		if dis[nex] < 0:
			dfs(nex)
		num = max(num, dis[nex] + 1)
	dis[x] = num
	return
dis = [-1] * n
for i in range(n):
	if dis[i] < 0:
		dfs(i)
print(max(dis))


import sys
sys.setrecursionlimit(10 ** 5 + 1)
(N, M) = map(int, input().split())
nodes = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	nodes[x - 1].append(y - 1)
dp = [-1] * N

def judge(index):
	if dp[index] != -1:
		return dp[index]
	else:
		edges = 0
		for i in nodes[index]:
			edges = max(edges, 1 + judge(i))
		dp[index] = edges
		return edges
answer = 0
for i in range(N):
	answer = max(answer, judge(i))
print(answer)


import sys
sys.setrecursionlimit(300 * 300 * 300 + 10)

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for nv in Graph[v]:
		res = max(res, rec(nv) + 1)
	dp[v] = res
	return dp[v]
(N, M) = map(int, input().split())
G = [[int(_) for _ in input().split()] for _ in range(M)]
dp = [-1] * N
Graph = [[] for _ in range(N)]
ans = 0
for i in G:
	Graph[i[0] - 1].append(i[1] - 1)
for v in range(N):
	ans = max(ans, rec(v))
print(ans)


(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
kara = []
to = [0] * n
for i in range(m):
	(x, y) = map(int, input().split())
	edge[x - 1].append(y - 1)
	to[y - 1] += 1
for j in range(n):
	if to[j] == 0:
		kara.append(j)
dp = [0] * n
while len(kara):
	go = kara.pop()
	for e in edge[go]:
		to[e] -= 1
		if to[e] == 0:
			kara.append(e)
		dp[e] = max(dp[e], dp[go] + 1)
print(max(dp))


(N, M) = map(int, input().split())
g = [[] for _ in range(N)]
in_deg = [0] * N
for _ in range(M):
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
	in_deg[y - 1] += 1
dist = [0] * N
q = [x for x in range(N) if in_deg[x] == 0]
while q:
	v = q.pop()
	for u in g[v]:
		dist[u] = max(dist[u], dist[v] + 1)
		in_deg[u] -= 1
		if in_deg[u] == 0:
			q.append(u)
print(max(dist))


from collections import deque
(N, M) = map(int, input().split())
dp = [0] * N
E = [[] for _ in range(N)]
deg = [0] * N
for _ in range(M):
	(x, y) = map(int, input().split())
	E[x - 1].append(y - 1)
	deg[y - 1] += 1
que = deque((v for v in range(N) if deg[v] == 0))
while que:
	v = que.pop()
	for u in E[v]:
		deg[u] -= 1
		if deg[u] == 0:
			que.appendleft(u)
			dp[u] = max(dp[u], dp[v] + 1)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
(a, b) = (0, 0)
for i in range(M):
	(a, b) = map(int, input().split())
	G[b - 1].append(a - 1)
DP = [-1] * N

def f(x):
	if DP[x] != -1:
		return DP[x]
	DP[x] = 0
	for i in range(len(G[x])):
		DP[x] = max(DP[x], f(G[x][i]) + 1)
	return DP[x]
for i in range(N):
	f(i)
print(max(DP))


(n, m) = map(int, input().split())
oya = [set() for i in range(n)]
ko = [set() for i in range(n)]
rank = [0] * n
for i in range(m):
	(a, b) = map(int, input().split())
	ko[a - 1].add(b - 1)
	oya[b - 1].add(a - 1)
q = []
for i in range(n):
	if not oya[i]:
		q.append([i, ko[i]])
while q:
	(now, path) = q.pop()
	for i in path:
		oya[i].remove(now)
		if not oya[i]:
			q.append([i, ko[i]])
		rank[i] = max(rank[i], rank[now] + 1)
print(max(rank))


from collections import deque
(n, m) = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for j in range(m)]
E = [[] for i in range(n + 1)]
IN = [0] * (n + 1)
for (a, b) in X:
	E[a].append(b)
	IN[b] += 1
q = deque(((i, 0) for i in range(1, n + 1) if IN[i] == 0))
D = [0] * (n + 1)
while q:
	(i, d) = q.popleft()
	IN[i] -= 1
	if IN[i] > 0:
		continue
	D[i] = d
	for e in E[i]:
		q.append((e, d + 1))
print(max(D))


import sys
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
g = [[] for i in range(1 + n)]
dist = [-1] * (1 + n)
for i in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)

def dfs(cur):
	if dist[cur] != -1:
		return dist[cur]
	if not g[cur]:
		dist[cur] = 0
	else:
		dist[cur] = 1 + max([dfs(nb) for nb in g[cur]])
	return dist[cur]
ans = 0
for i in range(1, n + 1):
	ans = max(ans, dfs(i))
print(ans)


from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def f(v):
	if not arc[v]:
		return 0
	return max((f(nv) for nv in arc[v])) + 1
(n, m) = map(int, input().split())
arc = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	arc[x - 1].append(y - 1)
print(max((f(v) for v in range(n))))


import sys
input = sys.stdin.readline
from collections import *
(N, M) = map(int, input().split())
ins = [0] * N
outs = defaultdict(list)
for _ in range(M):
	(x, y) = map(int, input().split())
	ins[y - 1] += 1
	outs[x - 1].append(y - 1)
q = deque([v for v in range(N) if ins[v] == 0])
dp = [0] * N
while q:
	v = q.popleft()
	for nv in outs[v]:
		dp[nv] = max(dp[nv], dp[v] + 1)
		ins[nv] -= 1
		if ins[nv] == 0:
			q.append(nv)
print(max(dp))


import sys
sys.setrecursionlimit(100000)
(N, M) = map(int, input().split())
childs = [[] for _ in range(N)]
for i in range(M):
	(p, c) = map(int, input().split())
	childs[p - 1].append(c - 1)
depth = [-1] * N

def dfs(n):
	if depth[n] != -1:
		return depth[n]
	if childs[n]:
		depth[n] = max((dfs(nc) for nc in childs[n])) + 1
	else:
		depth[n] = 0
	return depth[n]
print(max((dfs(n) for n in range(N))))


import sys
sys.setrecursionlimit(10 ** 7)

def f(v):
	if dp[v] != 0:
		return dp[v]
	res = 0
	for i in graph[v]:
		res = max(res, f(i) + 1)
	dp[v] = res
	return res
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	graph[x - 1].append(y - 1)
dp = [0] * N
for i in range(N):
	f(i)
print(max(dp))


import sys
sys.setrecursionlimit(200000)
(N, M) = map(int, input().split())
G = [[] for _ in range(N + 1)]
MEMO = [-1 for _ in range(N + 1)]
for _ in range(M):
	(x, y) = map(int, input().split())
	G[x].append(y)

def dp_LP(v):
	if MEMO[v] != -1:
		return MEMO[v]
	else:
		ans = 0
		for i in G[v]:
			ans = max(ans, dp_LP(i) + 1)
		MEMO[v] = ans
		return ans
answer = 0
for n in range(1, N + 1):
	answer = max(answer, dp_LP(n))
print(answer)


from collections import deque
(N, M) = list(map(int, input().split()))
inflows = [0] * (N + 1)
edges = [[] for i in range(N + 1)]
for i in range(M):
	(x, y) = list(map(int, input().split()))
	edges[x].append(y)
	inflows[y] += 1
queue = deque([i for i in range(1, N + 1) if inflows[i] == 0])
DP = [0] * (N + 1)
while queue:
	x = queue.popleft()
	for y in edges[x]:
		inflows[y] -= 1
		DP[y] = max(DP[y], DP[x] + 1)
		if inflows[y] == 0:
			queue.append(y)
print(max(DP))


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 8)
(N, M) = map(int, input().split())
h = defaultdict(list)
for i in range(M):
	(x, y) = map(int, input().split())
	h[x - 1].append(y - 1)
dp = [0] * N

def dist(v):
	if dp[v] > 0:
		return dp[v]
	dp[v] = 0
	for nv in h[v]:
		dp[v] = max([dp[v], dist(nv) + 1])
	return dp[v]
ans = 0
for v in range(N):
	ans = max([ans, dist(v)])
print(ans)


import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
(N, M) = map(int, input().split())
lst_edge = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	lst_edge[x - 1].append(y - 1)
dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	ans = 0
	lst_nv = lst_edge[v]
	for nv in lst_nv:
		ans = max(ans, rec(nv) + 1)
	dp[v] = ans
	return dp[v]
ans = 0
for v in range(N):
	ans = max(ans, rec(v))
print(ans)


(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
deg = [0] * N
for i in range(M):
	(xx, yy) = map(int, input().split())
	graph[xx - 1].append(yy - 1)
	deg[yy - 1] += 1
que = []
dp = [0] * N
for i in range(N):
	if deg[i] == 0:
		que.append(i)
while len(que) > 0:
	k = que.pop(0)
	for x in graph[k]:
		deg[x] -= 1
		if deg[x] == 0:
			que.append(x)
			dp[x] = max(dp[x], dp[k] + 1)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)

def rec(v):
	if memo[v] != -1:
		return memo[v]
	res = 0
	for nv in tree[v]:
		res = max(res, rec(nv) + 1)
	memo[v] = res
	return res
(n, m) = map(int, input().split())
tree = [[] for i in range(n)]
memo = [-1 for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	tree[x].append(y)
ans = 0
for v in range(n):
	ans = max(ans, rec(v))
print(ans)


import sys
from functools import lru_cache
sys.setrecursionlimit(524287)
(n, m, *l) = map(int, open(0).read().split())
pas = [[] for _ in range(n)]
for (x, y) in zip(l[::2], l[1::2]):
	pas[x - 1].append(y - 1)
INF = float('inf')
done = [-INF] * n

@lru_cache(maxsize=None)
def dfs(t):
	if done[t] >= 0:
		pass
	elif pas[t]:
		done[t] = max((dfs(s) for s in pas[t])) + 1
	else:
		done[t] = 0
	return done[t]
print(max((dfs(i) for i in range(n))))


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(cur):
	if dp[cur] != -1:
		return dp[cur]
	res = 0
	for nx in G[cur]:
		res = max(res, dfs(nx) + 1)
	dp[cur] = res
	return res
(n, m) = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
dp = [-1] * n
for i in range(n):
	dp[i] = max(dp[i], dfs(i))
print(max(dp))


import sys
sys.setrecursionlimit(10000)
(n, m) = map(int, input().split())
G = [[] for i in range(n)]
for j in range(m):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
DP = [None for i in range(n)]

def dp(i):
	if DP[i] != None:
		return DP[i]
	ret = 0
	for j in G[i]:
		ret = max(ret, dp(j) + 1)
	DP[i] = ret
	return ret
print(max([dp(i) for i in range(n)]))


import sys
sys.setrecursionlimit(10 ** 6)

def rec(i):
	if memo[i] != -1:
		return memo[i]
	elif not graph[i]:
		return 0
	else:
		memo[i] = max([rec(edge) for edge in graph[i]]) + 1
		return memo[i]
(N, M) = map(int, input().split())
memo = [-1 for i in range(N + 1)]
graph = [[] for i in range(N + 1)]
for i in range(M):
	(x, y) = map(int, input().split())
	graph[y].append(x)
for i in range(N + 1):
	rec(i)
print(max(memo))


import sys
sys.setrecursionlimit(1000000)
(n, m) = map(int, input().split())
path = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	path[y - 1].append(x - 1)
memo = [-1] * n

def dfs(v):
	if memo[v] < 0:
		if len(path[v]) == 0:
			memo[v] = 0
		else:
			memo[v] = max([dfs(p) + 1 for p in path[v]])
	return memo[v]
res = 0
for i in range(n):
	tmp = dfs(i)
	if res < tmp:
		res = tmp
print(res)


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
G = [set() for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	G[x - 1].add(y - 1)
dp = [-1 for i in range(N)]

def search(k):
	if dp[k] != -1:
		return dp[k]
	res = 0
	for r in G[k]:
		if search(r) + 1 > res:
			res = search(r) + 1
	dp[k] = res
	return res
for i in range(N):
	if dp[i] == -1:
		search(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
dp = [-1] * n
for _ in range(m):
	(v1, v2) = map(int, input().split())
	v1 -= 1
	v2 -= 1
	g[v1].append(v2)

def dfs(i):
	if dp[i] != -1:
		return dp[i]
	temp = 0
	for neighbour in g[i]:
		temp = max(temp, dfs(neighbour) + 1)
	dp[i] = temp
	return temp
res = 0
for i in range(n):
	res = max(res, dfs(i))
print(res)


import sys
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	edge[x - 1].append(y - 1)
dp = [-1] * N

def calc(x):
	if dp[x] != -1:
		return dp[x]
	if not len(edge[x]):
		dp[x] = 0
		return 0
	dp[x] = max([calc(i) for i in edge[x]]) + 1
	return dp[x]
ans = 0
for i in range(N):
	ans = max(ans, calc(i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 8)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
dp = [-1] * N

def dfs(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for g in G[v]:
		res = max(res, dfs(g) + 1)
	dp[v] = res
	return res
ans = 0
for i in range(N):
	ans = max(ans, dfs(i))
print(ans)


import sys
input = sys.stdin.readline
(n, m) = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = [int(x) for x in input().split()]
	g[x - 1].append(y - 1)
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

@lru_cache(maxsize=None)
def dp(v):
	res = 0
	for u in g[v]:
		res = max(res, dp(u) + 1)
	return res
ans = -1
for i in range(n):
	ans = max(ans, dp(i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	edge[x - 1].append(y - 1)
d = [0] * n

def dfs(v, edge):
	depth = 0
	for next_v in edge[v]:
		if d[next_v] == 0:
			depth = max(depth, dfs(next_v, edge))
		depth = max(depth, d[next_v])
	depth += 1
	d[v] = depth
	return depth
for i in range(n):
	dfs(i, edge)
print(max(d) - 1)


import sys
sys.setrecursionlimit(100000)
(N, M) = map(int, input().split())
Edge = [[] for _ in range(N)]
Far = [-1] * N
for _ in range(M):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	Edge[x].append(y)

def long(x):
	if len(Edge[x]) == 0:
		Far[x] = 0
		return 0
	if Far[x] >= 0:
		return Far[x]
	r = 0
	for i in Edge[x]:
		l = long(i) + 1
		r = max(r, l)
	Far[x] = r
	return r
for i in range(N):
	long(i)
print(max(Far))


import sys
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	edge[x].append(y)
flag = [0] * n
dp = [0] * n

def dfs(s):
	if flag[s]:
		return dp[s]
	flag[s] = 1
	dist = 0
	for i in edge[s]:
		dist = max(dist, dfs(i) + 1)
	dp[s] = dist
	return dp[s]
for i in range(n):
	dfs(i)
print(max(dp))


import sys
sys.setrecursionlimit(10000)
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	graph[x - 1].append(y - 1)
dp = [-1 for _ in range(N)]

def rec(c):
	if dp[c] != -1:
		return dp[c]
	res = 0
	for i in graph[c]:
		res = max(res, rec(i) + 1)
	dp[c] = res
	return res
for i in range(N):
	rec(i)
print(max(dp))


import sys
sys.setrecursionlimit(int(100000.0))
(N, M) = map(int, input().rstrip().split(' '))
g = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().rstrip().split(' '))
	g[y - 1].append(x - 1)
dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	count = 0
	for x in g[v]:
		count = max(count, rec(x) + 1)
	dp[v] = count
	return count
for i in range(N):
	rec(i)
print(max(dp))


import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)
(N, M) = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, readline().split())
	G[x - 1].append(y - 1)
dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for child in G[v]:
		res = max(res, rec(child) + 1)
	dp[v] = res
	return res
res = 0
for v in range(N):
	res = max(res, rec(v))
print(res)


(N, M) = map(int, input().split())
xy = [[int(i) - 1 for i in input().split()] for _ in range(M)]
cnt = [0] * N
v = [[] for _ in range(N)]
for (x, y) in xy:
	v[x].append(y)
	cnt[y] += 1
s = []
for i in range(N):
	if cnt[i] == 0:
		s.append(i)
dp = [0] * N
while s:
	cur = s.pop()
	for nex in v[cur]:
		dp[nex] = max(dp[nex], dp[cur] + 1)
		cnt[nex] -= 1
		if cnt[nex] == 0:
			s.append(nex)
print(max(dp))


(n, m) = map(int, input().split())
dp = [0] * n
indeg = [0] * n
to = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	to[x].append(y)
	indeg[y] += 1
avail = list(filter(lambda i: indeg[i] == 0, range(n)))
while avail:
	u = avail.pop()
	for v in to[u]:
		dp[v] = max(dp[v], dp[u] + 1)
		indeg[v] -= 1
		if indeg[v] == 0:
			avail.append(v)
print(max(dp))


import sys
(N, M) = map(int, input().split())
sys.setrecursionlimit(10 ** 9)
vertices = [[] for i in range(N + 1)]
dp = [-1] * (N + 1)
for _ in range(M):
	(fro, to) = map(int, input().split())
	vertices[fro].append(to)

def dfs(i):
	if dp[i] != -1:
		return dp[i]
	temp = 0
	for vertex in vertices[i]:
		temp = max(temp, dfs(vertex) + 1)
	dp[i] = temp
	return temp
for i in range(1, N + 1):
	dfs(i)
print(max(dp))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
(N, M) = map(int, input().split())
to = [[] * (N + 1) for _ in range(N + 1)]
for i in range(M):
	(x, y) = map(int, input().split())
	to[x].append(y)
dp = [-1] * (N + 1)

def saiki(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for u in to[v]:
		res = max(res, saiki(u) + 1)
	dp[v] = res
	return res
ans = 0
for i in range(1, N + 1):
	ans = max(ans, saiki(i))
print(max(dp))


from collections import defaultdict, deque
(N, M) = map(int, input().split())
G = defaultdict(list)
V = defaultdict(int)
for i in range(M):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	G[x].append(y)
	V[y] += 1
q = deque((v for v in range(N) if V[v] == 0))
dp = [0] * N
while q:
	From = q.popleft()
	for to in G[From]:
		dp[to] = max(dp[From] + 1, dp[to])
		V[to] -= 1
		if V[to] == 0:
			q.append(to)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
E = [[] for _ in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	E[x].append(y)
dp = [-1 for _ in range(N)]

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for u in E[v]:
		res = max(res, rec(u) + 1)
	dp[v] = res
	return dp[v]
for i in range(N):
	rec(i)
print(max(dp))


import sys
sys.setrecursionlimit(10000)

def solve(g):
	dp = [-1] * len(g)

	def _solve(f):
		if dp[f] == -1:
			dp[f] = 0
			for c in g[f]:
				dp[f] = max(dp[f], 1 + _solve(c))
		return dp[f]
	for f in range(len(g)):
		_solve(f)
	return max(dp)
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(f, t) = map(int, input().split())
	g[f - 1].append(t - 1)
print(solve(g))


(n, m) = map(int, input().split())
G = [[] for i in range(n)]
I = [0 for i in range(n)]
for j in range(m):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
	I[y - 1] += 1
Q = [i for i in range(n) if I[i] == 0]
L = [0 for i in range(n)]
while Q:
	i = Q.pop()
	while G[i]:
		j = G[i].pop()
		I[j] -= 1
		L[j] = max(L[j], L[i] + 1)
		if I[j] == 0:
			Q.append(j)
print(max(L))


from sys import setrecursionlimit

def f(i, links, dp):
	if dp[i] != -1:
		return dp[i]
	if len(links[i]) == 0:
		dp[i] = 0
	else:
		dp[i] = max((f(j, links, dp) for j in links[i])) + 1
	return dp[i]
setrecursionlimit(1000000)
(N, M) = map(int, input().split())
links = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	links[x - 1].append(y - 1)
dp = [-1] * N
print(max((f(i, links, dp) for i in range(N))))


import sys
sys.setrecursionlimit(100000)
(N, M) = map(int, input().split())
memo = [-1] * N
dic = [[] for i in range(N)]

def dfs(dic, memo, v):
	if memo[v] != -1:
		return memo[v]
	plen = 0
	for i in dic[v]:
		plen = max(plen, dfs(dic, memo, i) + 1)
	memo[v] = plen
	return plen
for m in range(M):
	(x, y) = map(int, input().split())
	dic[x - 1].append(y - 1)
ans = 0
for i in range(N):
	ans = max(ans, dfs(dic, memo, i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 8)
(N, M) = map(int, input().split())
graph = [dict() for _ in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	graph[y - 1][x - 1] = 1
dp = [0 for _ in range(N)]

def dfs(u):
	if dp[u] != 0:
		return dp[u]
	max_dis = 0
	for f in graph[u].keys():
		if max_dis < dfs(f) + 1:
			max_dis = dfs(f) + 1
	dp[u] = max_dis
	return dp[u]
for i in range(N):
	dfs(i)
print(max(dp))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edges = [[] for _ in range(n)]
S = []
T = [0] * n
for _ in range(m):
	(x, y) = map(int, input().split())
	edges[x - 1].append(y - 1)
	T[y - 1] += 1
for i in range(n):
	if T[i] == 0:
		S.append(i)
DP = [0] * n
while S:
	fr = S.pop()
	for to in edges[fr]:
		T[to] -= 1
		if T[to] == 0:
			S.append(to)
		DP[to] = max(DP[to], DP[fr] + 1)
print(max(DP))


(N, M) = (int(i) for i in input().split())
outs = [[] for i in range(N)]
ins = [0] * N
for _ in range(M):
	(x, y) = (int(i) for i in input().split())
	x -= 1
	y -= 1
	outs[x].append(y)
	ins[y] += 1
q = []
for i in range(N):
	if ins[i] == 0:
		q.append(i)
last = [0] * N
while q != []:
	qn = q.pop()
	for v in outs[qn]:
		ins[v] -= 1
		last[v] = max(last[v], last[qn] + 1)
		if ins[v] == 0:
			q.append(v)
print(max(last))


import sys
sys.setrecursionlimit(10 ** 5 + 1)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
dp = [-1] * N

def search(v):
	if dp[v] != -1:
		return dp[v]
	max_depth = 0
	for child in G[v]:
		max_depth = max(max_depth, search(child) + 1)
	dp[v] = max(dp[v], max_depth)
	return dp[v]
for i in range(N):
	search(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(M):
	(x, y) = map(int, input().split())
	G[x].append(y)
lst = [-1] * (N + 1)

def calc(x):
	if lst[x] != -1:
		return lst[x]
	tmp = 0
	for next_ in G[x]:
		tmp = max(tmp, calc(next_))
	lst[x] = tmp + 1
	return tmp + 1
ans = 0
for i in range(1, N + 1):
	if lst[i] == -1:
		ans = max(ans, calc(i))
print(ans - 1)


import sys
sys.setrecursionlimit(10 ** 5)
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
dp = [0] * n
for i in range(m):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)

def dfs(s):
	if edge[s]:
		for i in edge[s]:
			if dp[i]:
				dp[s] = max(dp[s], dp[i] + 1)
			else:
				dp[s] = max(dp[s], dfs(i) + 1)
		return dp[s]
	else:
		return 0
for i in range(n):
	dfs(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 7)

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for nv in es[v]:
		res = max(res, rec(nv) + 1)
	dp[v] = res
	return res
(N, M) = map(int, input().split())
es = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	es[x].append(y)
dp = [-1] * N
res = 0
for v in range(N):
	res = max(res, rec(v))
print(res)


import collections
import sys
sys.setrecursionlimit(10 ** 9)

def dfs(v):
	if cache.get(v):
		return cache[v]
	path = 0
	for adj in g[v]:
		path = max(path, 1 + dfs(adj))
	cache[v] = path
	return path
(n, m) = map(int, input().split())
g = collections.defaultdict(list)
cache = {}
path = 0
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
for v in range(1, n + 1):
	path = max(path, dfs(v))
print(path)


import sys
sys.setrecursionlimit(10 ** 5)

def dfs(now):
	if v[now]:
		return v[now]
	res = 1
	for to in e[now]:
		res = max(res, dfs(to) + 1)
	v[now] = res
	return res
(n, m) = map(int, input().split())
e = [[] for _ in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	e[x] += [y]
v = [0] * (n + 1)
v[0] = 1
ans = 0
for i in range(n + 1):
	ans = max(ans, dfs(i))
print(ans - 1)


import sys
sys.setrecursionlimit(10 ** 9)
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	g[x].append(y)
dp = [-1] * n

def dfs(i):
	if dp[i] != -1:
		return dp[i]
	tmp = 0
	for j in g[i]:
		tmp = max(tmp, dfs(j) + 1)
	dp[i] = tmp
	return tmp
for i in range(n):
	dfs(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 8)
(n, m) = map(int, input().split())
d = {}
dp = {}
n = []
for _ in range(m):
	(x, y) = map(int, input().split())
	n.append(x)
	try:
		d[x].append(y)
	except:
		d[x] = [y]

def lp(a):
	if a in dp:
		return dp[a]
	if a not in d:
		dp[a] = 1
		return 1
	ans = 0
	for i in d[a]:
		ans = max(ans, 1 + lp(i))
	dp[a] = ans
	return ans
p = 0
for i in n:
	p = max(p, lp(i))
print(p - 1)


import sys
sys.setrecursionlimit(10 ** 9)

def rec(n):
	if dp[n] != -1:
		return dp[n]
	else:
		max_n = 0
		for i in graph[n]:
			max_n = max(max_n, rec(i) + 1)
		dp[n] = max_n
		return dp[n]
(N, M) = list(map(int, input().split()))
dp = [-1] * N
graph = [[] for _ in range(N)]
for _ in range(M):
	(xi, yi) = list(map(int, input().split()))
	graph[xi - 1].append(yi - 1)
ans = 0
for n in range(N):
	ans = max(rec(n), ans)
print(ans)


import sys
sys.setrecursionlimit(10 ** 5 + 10)

def memo(v):
	if dp[v] != -1:
		return dp[v]
	ans = 0
	for next_v in g[v]:
		ans = max(ans, memo(next_v) + 1)
	dp[v] = ans
	return ans
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	g[x].append(y)
dp = [-1] * (n + 1)
ans = 0
for v in range(1, n + 1):
	ans = max(ans, memo(v))
print(ans)


(N, M) = map(int, input().split())
E = [[] for _ in range(N)]
rE = [0] * N
for _ in range(M):
	(x, y) = map(int, input().split())
	E[x - 1].append(y - 1)
	rE[y - 1] += 1
dp = [0] * N
Q = [x for x in range(N) if not rE[x]]
while Q:
	v = Q.pop()
	memo = dp[v] + 1
	for u in E[v]:
		dp[u] = max(dp[u], memo)
		rE[u] -= 1
		if not rE[u]:
			Q.append(u)
print(max(dp))


from queue import Queue
(n, m) = map(int, input().split())
E = [[] for i in range(n + 1)]
ind = [0] * (n + 1)
dp = [0] * (n + 1)
Q = Queue()
for i in range(m):
	(x, y) = map(int, input().split())
	E[x].append(y)
	ind[y] += 1
for i in range(1, n + 1):
	if not ind[i]:
		Q.put(i)
while not Q.empty():
	u = Q.get()
	for i in E[u]:
		ind[i] -= 1
		dp[i] = max(dp[i], dp[u] + 1)
		if not ind[i]:
			Q.put(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 5 + 10)
(N, M) = map(int, input().split())
to = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	to[x - 1] += [y - 1]
dp = [-1 for i in range(N)]

def memo(i):
	if dp[i] != -1:
		return dp[i]
	a = 0
	for j in to[i]:
		a = max(a, memo(j) + 1)
	dp[i] = a
	return a
lp = 0
for i in range(N):
	lp = max(lp, memo(i))
print(lp)


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = list(map(lambda x: int(x) - 1, input().split()))
	G[x].append(y)
dp = [-1] * N

def f(v):
	if dp[v] != -1:
		return dp[v]
	ans = 0
	for nv in G[v]:
		ans = max(ans, f(nv) + 1)
	dp[v] = ans
	return ans
ans = 0
for i in range(N):
	ans = max(ans, f(i))
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)

def rec(vv):
	if p[vv] >= 0:
		return p[vv]
	res = 0
	for nv in g[vv]:
		res = max(res, rec(nv) + 1)
	p[vv] = res
	return res
(N, M) = map(int, input().split())
g = [[] for _ in range(N)]
p = [-1 for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	g[x].append(y)
ans = 0
for v in range(N):
	ans = max(ans, rec(v))
print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
(N, M) = map(int, input().split())
V = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	V[x].append(y)
dp = [None for _ in range(N)]

def dfs(x):
	if dp[x] is not None:
		return dp[x]
	if not V[x]:
		dp[x] = 0
		return 0
	l = max((dfs(v) for v in V[x])) + 1
	dp[x] = l
	return l
print(max((dfs(v) for v in range(N))))


(n, m) = map(int, input().split())
p = [[] for _ in range(n)]
c = [0] * n
import sys
sys.setrecursionlimit(10 ** 6)
for i in range(m):
	(x, y) = map(int, input().split())
	p[x - 1].append(y - 1)
from functools import lru_cache

@lru_cache(maxsize=n)
def l(k):
	return max([l(i) for i in p[k]] + [0]) + 1
print(max([l(i) for i in range(n)]) - 1)


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	path[x].append(y)
dp = [-1] * N

def dfs(v):
	if dp[v] > -1:
		return dp[v] + 1
	ret = 0
	for i in path[v]:
		ret = max(ret, dfs(i))
	dp[v] = ret
	return ret + 1
for i in range(N):
	if dp[i] < 0:
		dfs(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	path[a].append(b)
dp = [-1] * N

def chdp(x):
	if dp[x] != -1:
		return dp[x]
	dp[x] = 0
	for t in path[x]:
		dp[x] = max(dp[x], chdp(t) + 1)
	return dp[x]
for i in range(N):
	chdp(i)
print(max(dp))


import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
(n, m) = map(int, input().split())
es = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	es[x - 1].append(y - 1)
dp = [-1] * n

def memo(v):
	if dp[v] + 1:
		return dp[v]
	a = 0
	for i in es[v]:
		a = max(a, memo(i) + 1)
	dp[v] = a
	return a
ans = 0
for i in range(n):
	ans = max(ans, memo(i))
print(ans)


(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
in_G = [0] * N
for i in range(M):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
	in_G[y - 1] += 1
dist = [0] * N
q = [x for x in range(N) if in_G[x] == 0]
while q:
	v = q.pop()
	for g in G[v]:
		dist[g] = max(dist[g], dist[v] + 1)
		in_G[g] -= 1
		if in_G[g] == 0:
			q.append(g)
print(max(dist))


import sys
sys.setrecursionlimit(1000000)

def dfs(v):
	if cache[v] > -1:
		return cache[v]
	lv = links[v]
	cache[v] = ret = max(map(dfs, lv)) + 1 if lv else 0
	return ret
(n, m) = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
cache = [-1] * n
for line in sys.stdin.readlines():
	(x, y) = map(int, line.split())
	x -= 1
	y -= 1
	sss.discard(y)
	links[x].add(y)
print(max(map(dfs, sss)))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	graph[x - 1].append(y - 1)
dp = [-1] * n

def count(a):
	if dp[a] != -1:
		return dp[a]
	else:
		dp[a] = 0
		for i in graph[a]:
			dp[a] = max(count(i) + 1, dp[a])
		return dp[a]
print(max([count(i) for i in range(n)]))


import sys
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline().strip()

def dfs(v):
	if dp[v] >= 0:
		return dp[v]
	res = 0
	for nv in g[v]:
		res = max(res, dfs(nv) + 1)
	dp[v] = res
	return res
(n, m) = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
	(x, y) = map(int, input().split())
	g[x].add(y)
dp = [-1] * (n + 1)
for v in g:
	dp[v] = max(dp[v], dfs(v))
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 5 * 2)
(N, M) = map(int, input().split())
Ps = [[] for _ in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	Ps[x - 1].append(y - 1)
mem = [-1] * N

def rec(n):
	if mem[n] > -1:
		return mem[n]
	elif len(Ps[n]) == 0:
		mem[n] = 0
		return mem[n]
	else:
		mem[n] = max([rec(Ps[n][i]) for i in range(len(Ps[n]))]) + 1
		return mem[n]
for i in range(N):
	rec(i)
print(max(mem))


import sys
sys.setrecursionlimit(500000)
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	G[x].append(y)
dp = [-1] * n

def rec(s):
	if dp[s] != -1:
		return dp[s]
	ret = 0
	for ns in G[s]:
		ret = max(ret, rec(ns) + 1)
	dp[s] = ret
	return ret
ml = 0
for i in range(n):
	ml = max(ml, rec(i))
print(ml)


import sys
sys.setrecursionlimit(10 ** 7)

def dfs(x):
	if x in memo:
		return memo[x]
	ret = 0
	for y in g[x]:
		ret = max(ret, dfs(y) + 1)
	memo[x] = ret
	return ret
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
memo = {}
for i in range(1, n + 1):
	dfs(i)
print(max(memo.values()))


import sys
(N, M) = map(int, input().split())
sys.setrecursionlimit(10 ** 5)
E = [[] for _ in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	E[x - 1].append(y - 1)
dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	if len(E[v]) == 0:
		dp[v] = 0
		return dp[v]
	for to in E[v]:
		dp[v] = max(dp[v], rec(to) + 1)
	return dp[v]
for i in range(N):
	dp[i] = rec(i)
print(max(dp))


import sys
from heapq import *
sys.setrecursionlimit(200000)

def rec(i):
	if dp[i] != 0:
		return dp[i]
	res = 0
	for j in E[i]:
		res = max(rec(j) + 1, res)
	dp[i] = res
	return dp[i]
(N, M) = (int(x) for x in input().split())
E = [[] for _ in [0] * N]
dp = [0] * N
for i in range(M):
	(a, b) = (int(x) for x in input().split())
	E[a - 1].append(b - 1)
ans = 0
for i in range(N):
	ans = max(ans, rec(i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
(N, M) = map(int, input().split())
lst = [{} for f in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	lst[x - 1][y - 1] = 1
memo = {}

def cost(a):
	ans = 0
	if a in memo:
		return memo[a]
	else:
		for i in lst[a]:
			if i in memo:
				ans = max(memo[i] + 1, ans)
			else:
				ans = max(cost(i) + 1, ans)
		memo[a] = ans
		return ans
T = 0
for i in range(N):
	T = max(T, cost(i))
print(T)


(n, m) = map(int, input().split())
g_o = [[] for x in range(n)]
g_i = [0] * n
for _ in range(m):
	(p, c) = map(int, input().split())
	g_o[p - 1].append(c - 1)
	g_i[c - 1] += 1
sor = [e for e in range(n) if g_i[e] == 0]
for node in sor:
	for i in g_o[node]:
		g_i[i] -= 1
		if g_i[i] == 0:
			sor.append(i)
dp = [0] * n
for node in sor:
	for c in g_o[node]:
		if dp[c] < dp[node] + 1:
			dp[c] = dp[node] + 1
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 8)
(N, M) = map(int, input().split())
G = dict([[i, []] for i in range(N)])
for _ in range(M):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
dp = [-1] * N

def rec(v):
	if dp[v] >= 0:
		return dp[v]
	if len(G[v]) == 0:
		return 0
	ret = -1
	for nv in G[v]:
		ret = max(ret, rec(nv) + 1)
	dp[v] = ret
	return ret
print(max([rec(v) for v in range(N)]))


from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
(N, M) = map(int, input().split())
XY = [map(int, input().split()) for _ in range(M)]
dp = [-1 for _ in range(N + 1)]
x_to_y = defaultdict(list)
for (x, y) in XY:
	x_to_y[x].append(y)

@lru_cache(N)
def depth(n):
	ret = -1
	for y in x_to_y[n]:
		ret = max(ret, depth(y))
	return ret + 1
depths = [depth(n) for n in range(1, N + 1)]
print(max(depths))


import sys
sys.setrecursionlimit(10 ** 8)
(n, m) = map(int, input().split())
adjacent_list = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	adjacent_list[x].append(y)
dp = [-1] * (n + 1)

def dfs(i):
	if dp[i] != -1:
		return dp[i]
	res = 0
	for j in adjacent_list[i]:
		res = max(res, dfs(j) + 1)
	dp[i] = res
	return dp[i]
ans = 0
for i in range(1, n + 1):
	ans = max(ans, dfs(i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
	(f, t) = map(int, input().split())
	graph[t].append(f)
dp = [-1] * (n + 1)

def dfs(now):
	if dp[now] != -1:
		return dp[now]
	if not graph[now]:
		return 0
	r = max((dfs(parent) for parent in graph[now])) + 1
	dp[now] = r
	return r
print(max((dfs(i) for i in range(1, n + 1))))


import sys
sys.setrecursionlimit(10 ** 5 + 100)
(N, M) = list(map(int, input().split()))
G = {i: [] for i in range(N)}
for _ in range(M):
	(x, y) = list(map(int, input().split()))
	G[x - 1].append(y - 1)
dp = [-1] * N

def rec(i):
	if dp[i] != -1:
		return dp[i]
	res = 0
	for v in G[i]:
		res = max(res, rec(v) + 1)
	dp[i] = res
	return res
ans = 0
for i in range(N):
	ans = max(ans, rec(i))
print(ans)


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
(n, m) = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for j in range(m)]
E = [[] for i in range(n + 1)]
for (a, b) in X:
	E[a].append(b)
memo = [-1] * (n + 1)

def dfs(i):
	if memo[i] != -1:
		return memo[i] + 1
	if not E[i]:
		return 0
	memo[i] = max((dfs(e) for e in E[i]))
	return memo[i] + 1
print(max((dfs(i) for i in range(1, n + 1))))


import sys
sys.setrecursionlimit(10 ** 5 + 100)
(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
	(xi, yi) = map(int, input().split())
	G[xi - 1].append(yi - 1)
dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for nv in G[v]:
		res = max(res, rec(nv) + 1)
	dp[v] = res
	return res
ans = 0
for v in range(N):
	ans = max(ans, rec(v))
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
graph = {}
(n, m) = map(int, input().split())
for i in range(1, n + 1):
	graph[i] = []
for _ in range(m):
	(u, v) = map(int, input().split())
	graph[u].append(v)

def dfs(i, dp):
	temp = 0
	if dp[i] != -1:
		return dp[i]
	for nvr in graph[i]:
		temp = max(temp, dfs(nvr, dp) + 1)
	dp[i] = temp
	return temp
dp = [-1] * (n + 1)
res = 0
for i in range(1, n + 1):
	res = max(res, dfs(i, dp))
print(res)


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(v):
	if dp[v] == -1:
		dp[v] = 0
		for nv in G[v]:
			dp[v] = max(dp[v], dfs(nv) + 1)
	return dp[v]
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	G[x].append(y)
dp = [-1] * N
res = -1
for v in range(N):
	res = max(res, dfs(v))
print(res)


import sys
sys.setrecursionlimit(10 ** 9)

def f(x):
	if dp[x] != -1:
		return dp[x]
	ans = 0
	for e in d[x]:
		ans = max(ans, 1 + f(e))
	dp[x] = ans
	return ans
(n, m) = list(map(int, input().split()))
d = {}
dp = [-1]
for i in range(1, n + 1):
	d[i] = []
	dp.append(-1)
for _ in range(m):
	(a, b) = map(int, input().split())
	d[a].append(b)
ans = 0
for i in range(1, n + 1):
	ans = max(ans, f(i))
print(ans)


(N, M) = map(int, input().split())
A = [[] for i in range(N + 1)]
B = [0 for i in range(N + 1)]
dp = [0 for j in range(N + 1)]
for i in range(M):
	(x, y) = map(int, input().split())
	A[x].append(y)
	B[y] += 1
st = []
for i in range(1, N + 1):
	if B[i] == 0:
		st.append(i)
		dp[i]
while len(st):
	x = st.pop()
	for y in A[x]:
		dp[y] = max(dp[y], dp[x] + 1)
		B[y] -= 1
		if B[y] == 0:
			st.append(y)
print(max(dp))


import sys
sys.setrecursionlimit(10000000)
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
dp = [-1] * n
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	g[x].append(y)

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for i in g[v]:
		res = max(res, rec(i) + 1)
	dp[v] = res
	return dp[v]
for i in range(n):
	rec(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
mem = [-1] * n

def dfs(v):
	if mem[v] != -1:
		return mem[v]
	mem[v] = r = max((dfs(w) for w in g[v])) + 1 if g[v] else 0
	return r
print(max((dfs(t) for t in range(n))))


from collections import deque
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	deg[v] += 1
q = deque()
for i in range(1, n + 1):
	if deg[i] == 0:
		q.append(i)
dp = [0] * (n + 1)
while q:
	n = q.popleft()
	for s in graph[n]:
		deg[s] -= 1
		if deg[s] == 0:
			q.append(s)
			dp[s] = dp[n] + 1
print(max(dp))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
F = [-1 for _ in range(N)]

def dfs(s):
	if F[s] != -1:
		return F[s]
	ret = 0
	for g in G[s]:
		ret = max(ret, dfs(g) + 1)
	F[s] = ret
	return ret
res = 0
for i in range(N):
	res = max(dfs(i), res)
print(res)


import sys
sys.setrecursionlimit(10 ** 6 + 100)
(n, m) = map(int, input().split())
memo = [-1] * (10 ** 6 + 100)
g = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	g[y].append(x)

def dfs(i):
	if memo[i] != -1:
		return memo[i]
	if not g[i]:
		return 0
	else:
		memo[i] = max((dfs(v) for v in g[i])) + 1
		return memo[i]
for i in range(1, n + 1):
	dfs(i)
print(max(memo))


import sys
sys.setrecursionlimit(100000)
(N, M) = map(int, input().split())
links = [[] for _ in range(N + 1)]
for _ in range(M):
	(s, t) = map(int, input().split())
	links[s].append(t)
dp = [-1 for _ in range(N + 1)]

def search(i):
	if dp[i] != -1:
		return dp[i]
	paths = 0
	for t in links[i]:
		paths = max(paths, search(t) + 1)
	dp[i] = paths
	return paths
for i in range(1, N + 1):
	search(i)
print(max(dp))


import sys
sys.setrecursionlimit(100000)
(N, M) = map(int, input().split(' '))
G = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split(' '))
	G[x - 1].append(y - 1)
dp = [-1] * N

def pathlen(G, dp, v):
	if dp[v] != -1:
		return dp[v]
	plen = 0
	for i in G[v]:
		plen = max(plen, pathlen(G, dp, i) + 1)
	dp[v] = plen
	return plen
ans = 0
for i in range(N):
	ans = max(ans, pathlen(G, dp, i))
print(ans)


(n, m) = map(int, input().split())
l = [[] for i in range(n)]
for i in range(m):
	p = [int(j) for j in input().split()]
	l[p[1] - 1].append(p[0] - 1)
dp = [-1] * n
import sys
sys.setrecursionlimit(10 ** 6)

def f(v):
	if dp[v] != -1:
		return dp[v]
	p = 0
	for i in l[v]:
		p = max(p, f(i) + 1)
	dp[v] = p
	return dp[v]
for i in range(n):
	f(i)
print(max(dp))


from sys import setrecursionlimit
setrecursionlimit(10 ** 5 + 10)
(N, M, *XY) = map(int, open(0).read().split())
E = [[] for _ in range(N + 1)]
for (x, y) in zip(*[iter(XY)] * 2):
	E[x].append(y)
memo = {}

def dp(p):
	if p not in memo:
		memo[p] = max((1 + dp(c) for c in E[p]), default=0)
	return memo[p]
print(max((dp(p) for p in range(1, N + 1))))


from collections import deque
(n, m) = map(int, input().split())
rev = [list() for _ in range(n + 1)]
tr = [0] * (n + 1)
ans = [0] * (n + 1)
for _ in range(m):
	(x, y) = map(int, input().split())
	rev[y].append(x)
	tr[x] += 1
q = deque()
for i in range(1, n + 1):
	if tr[i] == 0:
		q.append(i)
while q:
	cur = q.popleft()
	for x in rev[cur]:
		tr[x] -= 1
		ans[x] = max(ans[x], ans[cur] + 1)
		if tr[x] == 0:
			q.append(x)
print(max(ans))


import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
(N, M) = map(int, input().split())
XY = [[] for m in range(N)]
for l in range(M):
	(x, y) = map(int, input().split())
	XY[x - 1].append(y - 1)
dp = [-1 for k in range(N)]

def search(i):
	if dp[i] != -1:
		return dp[i]
	c = 0
	start = XY[i]
	for s in start:
		c = max(c, search(s) + 1)
	dp[i] = c
	return dp[i]
a = 0
for i in range(N):
	a = max(a, search(i))
print(a)


(n, m) = map(int, input().split())
inc = [0] * n
out = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	out[a].append(b)
	inc[b] += 1
S = {i for (i, c) in enumerate(inc) if c == 0}
L = []
while S:
	k = S.pop()
	L.append(k)
	for m in out[k]:
		inc[m] -= 1
		if inc[m] == 0:
			S.add(m)
dp = [0] * n
for i in L:
	for j in out[i]:
		dp[j] = max(dp[j], dp[i] + 1)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(M)]
dp = [-1] * N
ip = [[] for _ in range(N)]
for i in range(M):
	ip[p[i][1] - 1].append(p[i][0] - 1)

def maxpath(i):
	if dp[i] != -1:
		return dp[i]
	a = 0
	for el in ip[i]:
		a = max(a, maxpath(el) + 1)
	dp[i] = a
	return a
for i in range(N):
	maxpath(i)
print(max(dp))


from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
	(x, y) = map(int, input().split())
	g[x].append(y)
	deg[y] += 1
q = deque()
for i in range(1, n + 1):
	if deg[i] == 0:
		q.append(i)
dp = [0] * (n + 1)
while q:
	n = q.popleft()
	for zzz in g[n]:
		deg[zzz] -= 1
		if deg[zzz] == 0:
			q.append(zzz)
			dp[zzz] = dp[n] + 1
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
memo = [-1] * N

def dfs(v):
	if memo[v] != -1:
		return memo[v]
	memo[v] = r = max((dfs(w) for w in G[v])) + 1 if G[v] else 0
	return r
print(max((dfs(v) for v in range(N))))


import sys
sys.setrecursionlimit(10000)
(n, m) = map(int, input().split())
root = [[] for _ in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	root[x - 1].append(y - 1)
memo = ['empty' for _ in range(n)]

def dp(x):
	if memo[x] == 'empty':
		res = 0
		for i in root[x]:
			res = max(res, dp(i) + 1)
		memo[x] = res
	return memo[x]
for j in range(n):
	dp(j)
print(max(memo))


(n, m) = map(int, input().split())
G = [[] for i in range(n)]
enter = [0] * n
for i in range(m):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
	enter[y - 1] += 1
dp = [0] * n
s = []
for i in range(n):
	if not enter[i]:
		s.append(i)
while s != []:
	v = s.pop(0)
	for i in G[v]:
		enter[i] -= 1
		if not enter[i]:
			s.append(i)
			dp[i] = dp[v] + 1
print(max(dp))


(N, M) = map(int, input().split())
path = [[] for _ in range(N)]
pin = [0] * N
for _ in range(M):
	(ip, op) = map(int, input().split())
	pin[op - 1] += 1
	path[ip - 1].append(op - 1)
cur = []
for i in range(N):
	if pin[i] == 0:
		cur.append(i)
ans = 0
while cur:
	ans += 1
	nxt = []
	for ip in cur:
		for op in path[ip]:
			pin[op] -= 1
			if pin[op] == 0 and (not op in nxt):
				nxt.append(op)
	cur = [x for x in nxt]
print(ans - 1)


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
memo = [-1] * N

def rec(x):
	if memo[x] >= 0:
		return memo[x]
	res = 0
	if not G[x]:
		memo[x] = 0
		return 0
	for y in G[x]:
		res = max(rec(y), res)
	memo[x] = res + 1
	return memo[x]
for i in range(N):
	rec(i)
print(max(memo))


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	G[x].append(y)
d = [-1] * N

def dfs(u):
	if d[u] != -1:
		return d[u]
	ma = 0
	for w in G[u]:
		ma = max(ma, dfs(w))
	d[u] = ma + 1
	return ma + 1
ans = 0
for i in range(N):
	ans = max(ans, dfs(i))
print(ans - 1)


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(v):
	if dp[v] != 0:
		return dp[v]
	cnt = 0
	for i in g[v]:
		cnt = max(cnt, dfs(i) + 1)
	dp[v] = cnt
	return dp[v]
(N, M) = map(int, input().split())
dp = [0] * (N + 1)
g = [[] for _ in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
for i in range(N):
	dfs(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
G = [[] for _ in range(N + 1)]
for i in range(M):
	(x, y) = map(int, input().split())
	G[x] += [y]
dp = [-1] * (N + 1)

def func(n):
	if dp[n] != -1:
		return dp[n]
	cnt = 0
	for m in G[n]:
		cnt = max(cnt, func(m) + 1)
	dp[n] = cnt
	return cnt
for i in range(1, N + 1):
	func(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 6)

def f(x):
	global hashi
	if x in hashi:
		return hashi[x]
	if adj[x] == []:
		return 0
	mino = 0
	for i in adj[x]:
		mino = max(mino, f(i))
	hashi[x] = mino + 1
	return mino + 1
l = input().split()
n = int(l[0])
m = int(l[1])
adj = [[] for i in range(n + 1)]
for i in range(m):
	l = input().split()
	u = int(l[0])
	v = int(l[1])
	adj[u].append(v)
maxa = 0
hashi = dict()
for i in range(1, n + 1):
	maxa = max(maxa, f(i))
print(maxa)


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 5 + 100)

def rec(v, dp, E):
	if dp[v] != -1:
		return dp[v]
	x = 0
	for w in E[v]:
		x = max(x, rec(w, dp, E) + 1)
	dp[v] = x
	return x
(n, m) = map(int, input().split())
E = defaultdict(list)
for i in range(m):
	(x, y) = map(int, input().split())
	E[x - 1].append(y - 1)
dp = [-1 for _ in range(n)]
ans = 0
for i in range(n):
	ans = max(ans, rec(i, dp, E))
print(ans)


import sys
sys.setrecursionlimit(110000)
(N, M) = map(int, input().split())
graph = [[] for _ in range(110000)]
for _ in range(M):
	(x, y) = map(int, input().split())
	graph[x].append(y)
dp_memo = [-1] * 110000

def dp(v):
	if dp_memo[v] != -1:
		return dp_memo[v]
	ret = 0
	for item in graph[v]:
		ret = max(ret, dp(item) + 1)
	dp_memo[v] = ret
	return ret
ans = 0
for i in range(1, N + 1):
	ans = max(ans, dp(i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
(n, m) = map(int, input().split())
dp = [-1] * n
E = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	E[x].append(y)

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for nv in E[v]:
		res = max(res, rec(nv) + 1)
	dp[v] = res
	return res
res = 0
for v in range(n):
	res = max(res, rec(v))
print(res)


import sys
sys.setrecursionlimit(10 ** 6)

def f(x):
	if flg[x]:
		flg[x] = 0
		p = 0
		for y in glaph[x]:
			p = max(p, f(y) + 1)
		dp[x] = p
	return dp[x]
(n, m) = map(int, input().split())
flg = [1] * (n + 1)
dp = [0] * (n + 1)
glaph = [[] for i in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	glaph[x].append(y)
ans = 0
for i in range(1, n + 1):
	ans = max(ans, f(i))
print(ans)


import collections
import sys
sys.setrecursionlimit(10 ** 9)
(cache, edge) = ({}, collections.defaultdict(list))

def dp(node):
	if node in cache:
		return cache[node]
	lcl_max = 0
	for child in edge[node]:
		lcl_max = max(lcl_max, 1 + dp(child))
	cache[node] = lcl_max
	return lcl_max
max_dis = 0
(n, m) = map(int, input().split())
for _ in range(m):
	(a, b) = map(int, input().split())
	edge[a].append(b)
for node in range(1, n + 1):
	max_dis = max(max_dis, dp(node))
print(max_dis)


import sys
sys.setrecursionlimit(100001)
(N, M) = map(int, input().split())
dp = [0] * N
g = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	g[x].append(y)

def dfs(node):
	if dp[node] > 0:
		return dp[node]
	mx = 0
	for i in g[node]:
		a = dfs(i) + 1
		if mx < a:
			mx = a
	dp[node] = mx
	return mx
ans = 0
for i in range(N):
	if dp[i] == 0:
		ans = max(ans, dfs(i))
print(ans)


import sys
sys.setrecursionlimit(2 << 28)
(n, m) = [int(i) for i in input().split()]
al = [set() for _ in range(n)]
for _ in range(m):
	(x, y) = [int(i) for i in input().split()]
	al[x - 1].add(y - 1)
dp = [-1] * n

def rec(v):
	if dp[v] != -1:
		return dp[v]
	ret = 0
	for nv in al[v]:
		ret = max(ret, rec(nv) + 1)
	dp[v] = ret
	return ret
ans = 0
for v in range(n):
	ans = max(ans, rec(v))
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
from collections import defaultdict
(n, m) = map(int, input().split())
d = defaultdict(list)
for _ in range(m):
	(x, y) = map(int, input().split())
	d[x - 1].append(y - 1)
dp = [-1] * n

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for nv in d[v]:
		res = max(res, rec(nv) + 1)
	dp[v] = res
	return res
res = 0
for v in range(n):
	res = max(res, rec(v))
print(res)


import sys
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
s = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	s[a - 1].append(b - 1)
k = [-1] * n

def dfs(v):
	if k[v] != -1:
		return k[v]
	k[v] = r = max((dfs(q) for q in s[v])) + 1 if s[v] else 0
	return r
print(max((dfs(t) for t in range(n))))


import sys

def dp(i, xy, l):
	if l[i] >= 0:
		return l[i]
	l[i] = t = max((dp(j, xy, l) for j in xy[i])) + 1
	return t

def main():
	sys.setrecursionlimit(10 ** 6)
	(N, M) = map(int, input().split())
	xy = [set() for _ in range(N)]
	for _ in range(M):
		(xi, yi) = map(int, input().split())
		xy[xi - 1].add(yi - 1)
	l = [0 if not i else -1 for i in xy]
	m = 0
	for i in range(N):
		m = max(m, dp(i, xy, l))
	print(m)
main()


import sys
sys.setrecursionlimit(10000000)
(V, M) = map(int, input().split())
L = [[] for _ in range(V + 1)]
DP = [-1 for _ in range(V + 2)]
for _ in range(M):
	(x, y) = map(int, input().split())
	L[x - 1].append(y - 1)

def rec(v):
	if DP[v] != -1:
		return DP[v]
	ret = 0
	for x in L[v]:
		ret = max(ret, rec(x) + 1)
	DP[v] = ret
	return DP[v]
ans = 0
for i in range(V):
	ans = max(ans, rec(i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
(N, M) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
G = [[] for i in range(N)]
for (a, b) in A:
	G[a - 1].append(b - 1)
dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	ans = 0
	for i in G[v]:
		ans = max(ans, rec(i) + 1)
	dp[v] = ans
	return dp[v]
ans = 0
for i in range(N):
	ans = max(ans, rec(i))
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)
from functools import lru_cache
(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	G[x].append(y)

@lru_cache(maxsize=10 ** 5 + 1)
def dp(v):
	res = 0
	for w in G[v]:
		res = max(res, dp(w) + 1)
	return res
ans = 0
for i in range(N):
	ans = max(ans, dp(i))
print(ans)


from collections import defaultdict
(n, m) = map(int, input().split(' '))
paths = defaultdict(list)
ins = [0] * (n + 1)
for _ in range(m):
	(x, y) = map(int, input().split(' '))
	paths[x].append(y)
	ins[y] += 1
no_in = [y for y in range(1, n + 1) if ins[y] == 0]
depth = [0] * (n + 1)
while no_in:
	x = no_in.pop()
	for y in paths[x]:
		ins[y] -= 1
		depth[y] = max(depth[y], depth[x] + 1)
		if ins[y] == 0:
			no_in.append(y)
print(max(depth))


import sys
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
dp = [-1] * (n + 1)
path = [[] for i in range(n)]
X = []
Y = []
for i in range(m):
	(x, y) = map(int, input().split())
	X.append(x - 1)
	Y.append(y - 1)
	path[x - 1].append(y - 1)

def dfs(i):
	if dp[i] > 0:
		return dp[i]
	res = 0
	for k in path[i]:
		res = max(res, dfs(k) + 1)
	dp[i] = res
	return res
ans = 0
for i in range(n):
	ans = max(ans, dfs(i))
print(ans)


from collections import defaultdict
(n, m) = map(int, input().split())
adj = defaultdict(list)
deg = [0] * (n + 1)
for i in range(m):
	(x, y) = map(int, input().split())
	adj[x].append(y)
	deg[y] += 1
dist = [0] * (n + 1)
que = []
for i in range(1, n + 1):
	if deg[i] == 0:
		que.append(i)
while que:
	v = que.pop()
	for i in adj[v]:
		deg[i] -= 1
		if deg[i] == 0:
			que.append(i)
		dist[i] = max(dist[i], dist[v] + 1)
print(max(dist))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
ad = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	ad[y].append(x)
dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for nv in ad[v]:
		res = max(res, rec(nv) + 1)
	dp[v] = res
	return dp[v]
for v in range(N):
	rec(v)
ans = max(dp)
print(ans)


import sys
sys.setrecursionlimit(10 ** 8)
(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for next_v in G[v]:
		res = max(res, rec(next_v) + 1)
	dp[v] = res
	return dp[v]
for i in range(N):
	dp[i] = rec(i)
print(max(dp))


(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
arrive = [0] * n
ready = []
for i in range(m):
	(x, y) = map(int, input().split())
	edge[x - 1].append(y - 1)
	arrive[y - 1] += 1
for i in range(n):
	if arrive[i] == 0:
		ready.append(i)
path_num = [0] * n
while ready:
	depart = ready.pop()
	for to in edge[depart]:
		path_num[to] = max(path_num[to], path_num[depart] + 1)
		arrive[to] -= 1
		if arrive[to] == 0:
			ready.append(to)
print(max(path_num))


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(v):
	seen[v] = 1
	for nv in G[v]:
		if seen[nv]:
			continue
		dfs(nv)
	topo.append(v)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	G[x].append(y)
seen = [0] * N
topo = []
for i in range(N):
	if not seen[i]:
		dfs(i)
dp = [0] * N
for v in reversed(topo):
	for nv in G[v]:
		dp[nv] = max(dp[nv], dp[v] + 1)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)
(n, m) = map(int, input().split())
v = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	v[a - 1].append(b - 1)
memo = [-1] * n

def dp(x):
	if memo[x] != -1:
		return memo[x]
	r = 0
	for i in v[x]:
		r = max(r, dp(i) + 1)
	memo[x] = r
	return r
res = max([dp(i) for i in range(n)])
print(res)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
	indeg[y - 1] += 1
dp = [-1 for _ in range(n)]

def LP(v):
	if dp[v] != -1:
		return dp[v]
	ans = 0
	for w in g[v]:
		ans = max(ans, LP(w) + 1)
	dp[v] = ans
	return dp[v]
for i in range(n):
	LP(i)
print(max(dp))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
dp = [-1] * N

def dfs(n):
	global dp
	if dp[n] >= 0:
		return dp[n]
	ma = 0
	for b in G[n]:
		ma = max(ma, dfs(b) + 1)
	dp[n] = ma
	return ma

def main():
	for i in range(N):
		dfs(i)
	print(max(dp))
main()


import sys
sys.setrecursionlimit(10000)
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
dp = [-1 for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().split())
	graph[x - 1].append(y - 1)

def rec(v):
	if dp[v] >= 0:
		return dp[v]
	temp = 0
	for next in graph[v]:
		temp = max(rec(next) + 1, temp)
	dp[v] = temp
	return temp
for i in range(N):
	rec(i)
print(max(dp))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(n, m) = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = [int(x) for x in input().split()]
	g[x - 1].append(y - 1)
memo = [-1] * n

def dp(v):
	if memo[v] >= 0:
		return memo[v]
	else:
		res = 0
		for u in g[v]:
			res = max(res, dp(u) + 1)
		memo[v] = res
		return res
for i in range(n):
	dp(i)
print(max(memo))


import sys
sys.setrecursionlimit(100000)

def rec(v):
	global dp, path
	if dp[v] != -1:
		return dp[v]
	res = 0
	for i in path[v]:
		res = max(res, rec(i) + 1)
	dp[v] = res
	return res
(N, M) = map(int, input().strip().split(' '))
dp = [-1] * N
path = [[] for _ in range(N)]
for _ in range(M):
	(x, y) = map(int, input().strip().split(' '))
	path[x - 1].append(y - 1)
result = 0
for i in range(N):
	result = max(result, rec(i))
print(result)


import sys
sys.setrecursionlimit(11000)

def util(adj, curr, dp):
	res = 0
	if dp[curr] != -1:
		return dp[curr]
	for next in adj[curr]:
		res = max(res, 1 + util(adj, next, dp))
	dp[curr] = res
	return res
(n, m) = map(int, input().strip().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().strip().split())
	adj[x - 1].append(y - 1)
dp = [-1] * n
lp = 0
for i in range(n):
	lp = max(lp, util(adj, i, dp))
print(lp)


import sys
sys.setrecursionlimit(1000000)
(n, m) = map(int, input().split())
p = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	p[x - 1].append(y - 1)
f = [-1 for _ in range(n)]

def calc(x):
	if f[x] != -1:
		return f[x]
	if len(p[x]) == 0:
		f[x] = 0
		return 0
	f[x] = max([calc(i) for i in p[x]]) + 1
	return f[x]
m = 0
for i in range(n):
	if f[i] != -1:
		continue
	m = max(m, calc(i))
print(m)


import sys
sys.setrecursionlimit(10 ** 5)
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	graph[x - 1].append(y - 1)
dp = [-1] * N
length = [0] * N

def cnt(j):
	if dp[j] != -1:
		return dp[j]
	else:
		dp[j] = 0
		for k in graph[j]:
			dp[j] = max(cnt(k) + 1, dp[j])
		return dp[j]
for i in range(N):
	length[i] = cnt(i)
print(max(length))


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]
dp = [None] * (N + 1)

def get_dp(i):
	if dp[i] != None:
		return dp[i]
	yListSub = yList[i]
	if yListSub == []:
		dp[i] = 0
		return 0
	else:
		dp[i] = 1 + max(map(get_dp, yListSub))
		return dp[i]
yList = [[] for _ in range(N + 1)]
for (x, y) in xy:
	yList[x].append(y)
[get_dp(i) for i in range(0, N + 1)]
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 5)
(N, M) = map(int, input().split())
edge = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	edge[x - 1].append(y - 1)
dp = [-1] * N

def dist(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for to in edge[v]:
		res = max(res, dist(to) + 1)
	dp[v] = res
	return res
ans = 0
for i in range(N):
	ans = max(ans, dist(i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
from functools import lru_cache
IN = lambda : map(int, input().split())
(n, m) = IN()
parents = set(range(n + 1))
links = [set() for _ in range(n + 1)]

@lru_cache(maxsize=None)
def dfs(v):
	lv = links[v]
	return max(map(dfs, lv)) + 1 if lv else 0
for _ in range(m):
	(x, y) = IN()
	parents.discard(y)
	links[x].add(y)
print(max(map(dfs, parents)))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
	(x, y) = map(int, input().split())
	graph[x].append(y)
dp = [None] * (N + 1)

def dfs(x):
	if dp[x] is not None:
		return dp[x]
	if graph[x]:
		dp[x] = 1 + max((dfs(y) for y in graph[x]))
	else:
		dp[x] = 0
	return dp[x]
answer = max((dfs(x) for x in range(1, N + 1)))
print(answer)


from collections import deque
(N, M) = map(int, input().split())
adjL = [[] for v in range(N)]
indegs = [0] * N
for _ in range(M):
	(x, y) = map(int, input().split())
	adjL[x - 1].append(y - 1)
	indegs[y - 1] += 1
dp = [0] * N
Q = deque([v for v in range(N) if indegs[v] == 0])
while Q:
	vNow = Q.popleft()
	for v2 in adjL[vNow]:
		dp[v2] = max(dp[v2], dp[vNow] + 1)
		indegs[v2] -= 1
		if indegs[v2] == 0:
			Q.append(v2)
print(max(dp))


import sys
sys.setrecursionlimit(1000000)
(N, M) = map(int, input().split())
G = {k: [] for k in range(N)}
for _ in range(M):
	(x, y) = map(int, input().split())
	G[x - 1].append(y - 1)
dp = [-1 for _ in range(100100)]

def rec(v):
	if dp[v] != -1:
		return dp[v]
	dp[v] = 0
	for nv in G[v]:
		dp[v] = max(dp[v], rec(nv) + 1)
	return dp[v]
ans = 0
for v in range(N):
	ans = max(ans, rec(v))
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
table = [[] for i in range(N)]
Lin = [0] * N
for i in range(M):
	(w, v) = map(int, input().split())
	table[w - 1].append(v - 1)
	Lin[v - 1] += 1
H = []
for i in range(N):
	if Lin[i] == 0:
		H.append(i)
dp = [-1] * N

def f(x):
	if dp[x] != -1:
		return dp[x]
	if len(table[x]) == 0:
		return 0
	t = 0
	for i in table[x]:
		t = max(t, f(i) + 1)
	dp[x] = t
	return t
for i in H:
	f(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 5)
(n, m) = map(int, input().split())
edges = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	edges[x].append(y)
dp = [-1 for _ in range(n + 1)]

def longest_path(u):
	if dp[u] != -1:
		return dp[u]
	d = 0
	for v in edges[u]:
		d = max(d, 1 + longest_path(v))
	dp[u] = d
	return d
for u in range(1, n + 1):
	longest_path(u)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
x = [0] * M
y = [0] * M
edge = [[] for j in range(N + 1)]
for i in range(M):
	(x[i], y[i]) = map(int, input().split())
	edge[x[i]] += [y[i]]
dp = [0] * (N + 1)

def f(x):
	if dp[x] != 0:
		return dp[x]
	num = 0
	for i in edge[x]:
		if i == []:
			num = max(num, 0)
		else:
			num = max(num, f(i) + 1)
	dp[x] = num
	return dp[x]
for i in range(1, N + 1):
	f(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
l = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	l[x].append(y)
memo = [0] * (n + 1)

def chain(v):
	if memo[v] != 0:
		return memo[v]
	else:
		for a in l[v]:
			memo[v] = max(chain(a) + 1, memo[v])
		return memo[v]
res = 0
for i in range(1, n + 1):
	res = max(res, chain(i))
print(res)


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(i):
	if distance[i] != -1:
		return distance[i]
	ans = 0
	for node in graph[i]:
		ans = max(ans, dfs(node) + 1)
	distance[i] = ans
	return ans
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
distance = [-1 for i in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
ans = 0
for i in range(n):
	ans = max(ans, dfs(i))
print(ans)


import sys
sys.setrecursionlimit(4100000)
(N, M) = [int(x) for x in input().split()]
E = {i: [] for i in range(1, N + 1)}
for _ in range(M):
	(u, v) = [int(x) for x in input().split()]
	E[u].append(v)
dp = [-1] * (N + 1)

def memo(v):
	if dp[v] != -1:
		return dp[v]
	res = 0
	for nv in E[v]:
		res = max(res, memo(nv) + 1)
	dp[v] = res
	return dp[v]
res = 0
for v in range(1, N + 1):
	res = max(res, memo(v))
print(res)


import sys
sys.setrecursionlimit(10 ** 5)
(N, M) = map(int, input().split())
edges = [[] for i in range(N)]
while M:
	(a, b) = map(int, input().split())
	edges[a - 1].append(b - 1)
	M -= 1
dp = [-1] * N

def dist(vertex):
	if dp[vertex] != -1:
		return dp[vertex]
	res = 0
	for to in edges[vertex]:
		res = max(res, dist(to) + 1)
	dp[vertex] = res
	return res
ans = 0
for i in range(N):
	ans = max(ans, dist(i))
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
(n, m) = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	adj[x].append(y)
dp = [-1 for _ in range(n + 1)]

def f(k):
	if dp[k] != -1:
		return dp[k]
	dp[k] = 0
	if adj[k]:
		for v in adj[k]:
			dp[k] = max(dp[k], f(v) + 1)
	return dp[k]
ans = -INF
for i in range(1, n + 1):
	ans = max(ans, f(i))
print(ans)


import sys
sys.setrecursionlimit(2000)
(N, M) = map(int, input().split())
x = [0] * M
y = [0] * M
G = [[] for _ in range(N + 1)]
for i in range(M):
	(X, Y) = map(int, input().split())
	x[i] = X
	y[i] = Y
	G[X] += [Y]
dp = [-1] * (N + 1)

def f(n):
	if dp[n] != -1:
		return dp[n]
	res = 0
	for m in G[n]:
		res = max(res, f(m) + 1)
	dp[n] = res
	return res
for i in range(1, N + 1):
	f(i)
print(max(dp))


import sys
sys.setrecursionlimit(10 ** 8)
(N, M) = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)

def dfs(v):
	if len(edge[v]) == 0:
		return 0
	ans = 0
	for u in edge[v]:
		if longest[u] == -1:
			longest[u] = dfs(u)
		ans = max(ans, longest[u] + 1)
	return ans
longest = [-1] * N
for i in range(N):
	if longest[i] == -1:
		longest[i] = dfs(i)
ans = max(longest)
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	G[x].append(y)
memo = [-1] * n

def dp(v):
	if memo[v] != -1:
		return memo[v]
	res = 0
	for nv in G[v]:
		res = max(res, dp(nv) + 1)
	memo[v] = res
	return res
ans = 0
for v in range(n):
	ans = max(ans, dp(v))
print(ans)


from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
dp = [-1 for _ in range(n)]
V = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	V[x - 1].append(y - 1)

def f(x):
	if dp[x] != -1:
		return dp[x]
	t = 0
	for v in V[x]:
		t = max(t, f(v) + 1)
	dp[x] = t
	return dp[x]
t = 0
for i in range(n):
	t = max(t, f(i))
print(t)


import sys
sys.setrecursionlimit(10 ** 7)

def dfs(v):
	if d[v] != -1:
		return d[v]
	res = -1
	for u in e[v]:
		res = max(res, dfs(u))
	res += 1
	d[v] = res
	return res
(n, m) = map(int, input().split())
e = tuple((set() for _ in range(n)))
for _ in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	e[x].add(y)
d = [-1] * n
res = -1
for v in range(n):
	res = max(res, dfs(v))
print(res)


import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def dfs(v):
	lv = links[v]
	return max(map(dfs, lv)) + 1 if lv else 0
(n, m) = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
	(x, y) = map(int, line.split())
	x -= 1
	y -= 1
	sss.discard(y)
	links[x].add(y)
print(max(map(dfs, sss)))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def dfs(i):
	if dp[i] != -1:
		return dp[i]
	c = 0
	for j in v[i]:
		c = max(c, dfs(j) + 1)
	dp[i] = c
	return c
(n, m) = map(int, input().split())
v = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	v[x].append(y)
dp = [-1] * (n + 1)
m = 0
for i in range(1, n + 1):
	m = max(m, dfs(i))
print(m)


import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
(n, m) = map(int, input().split())
e = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	e[a - 1].append(b - 1)
dis = [0] * n

def dfs(x):
	num = 0
	for nex in e[x]:
		if dis[nex] < 0:
			dfs(nex)
		num = max(num, dis[nex] + 1)
	dis[x] = num
	return
dis = [-1] * n
for i in range(n):
	if e[i] and dis[i] < 0:
		dfs(i)
print(max(dis))


import sys
sys.setrecursionlimit(2000000000)
(n, m) = map(int, input().split())
v = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	v[a - 1].append(b - 1)
memo = [-1] * n

def dp(x):
	if memo[x] != -1:
		return memo[x]
	r = 0
	for i in v[x]:
		r = max(r, dp(i) + 1)
	memo[x] = r
	return r
print(max((dp(i) for i in range(n))))


import sys
sys.setrecursionlimit(10000000)

def calc(dp, adj, i):
	if len(adj[i]) == 0:
		dp[i] = 0
	elif dp[i] > 0:
		return dp[i]
	else:
		for j in adj[i]:
			dp[i] = max(dp[i], calc(dp, adj, j))
		dp[i] += 1
	return dp[i]
(n, m) = map(int, input().split())
adj = []
for i in range(n + 1):
	adj.append([])
for i in range(m):
	(x, y) = map(int, input().split())
	adj[x].append(y)
dp = [-1] * (n + 1)
for i in range(1, n + 1):
	calc(dp, adj, i)
print(max(dp))


import collections
(n, m) = map(int, input().split())
d = {}
indegree = [0] * n
for _ in range(m):
	(x, y) = map(int, input().split())
	d[x - 1] = d.get(x - 1, []) + [y - 1]
	indegree[y - 1] += 1
dp = [0] * n
q = collections.deque([i for i in range(n) if indegree[i] == 0])
while q:
	node = q.popleft()
	for nei in d.get(node, []):
		indegree[nei] -= 1
		dp[nei] = max(dp[nei], dp[node] + 1)
		if indegree[nei] == 0:
			q.append(nei)
print(max(dp))