Problem:
 Score : 100 points    Problem Statement 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 .        Sample Input 1 4 5
1 2
1 3
3 2
2 4
3 4      Sample Output 1 3  The red directed path in the following figure is the longest:        Sample Input 2 6 3
2 3
4 5
5 6      Sample Output 2 2  The red directed path in the following figure is the longest:        Sample Input 3 5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3      Sample Output 3 3  The red directed path in the following figure is one of the longest:

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



sys.setrecursionlimit(10**6)

def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num



N, M = mi()
x = li2(M)


adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



from collections import deque
sys.setrecursionlimit(10**6)

N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    if flag[x]:
        return None
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

for i in range(N):
    dfs(i)

dp = [0]*N
for a in ans:
    for b in adj[a]:
        dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



from collections import deque
sys.setrecursionlimit(10**6)

N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    if flag[x]:
        return None
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

for i in range(N):
    dfs(i)

dp = [0]*N
for a in ans:
    for b in adj[a]:
        dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



from collections import deque
sys.setrecursionlimit(10**6)

N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x, ans):
    if flag[x]:
        return None
    else:
        flag[x] = 1
        if adj[x]:
            for a in adj[x]:
                dfs(a, ans)
        
        ans.appendleft(x)

for i in range(N):
    dfs(i, ans)

dp = [0]*N
for a in ans:
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]


'''
N, M = mi()
x = li2(M)


dp = [[0, []] for i1 in range(N+1)]


for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    if dp[x[i][1]][1] != []:
        for a in dp[x[i][1]][1]:
            dp[a][0] = max(dp[x[i][1]][0] + 1, dp[a][0])

print(dp)
print(max([row[0] for row in dp])) 
'''

from collections import deque
N, M = mi()
x = li2(M)

h = [0]*N
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    h[x[i][1]] += 1
    adj[x[i][0]].append(x[i][1])

zeros = deque([])

for i in range(N):
    if h[i] == 0:
        zeros.append(i)
        

dp = [0]*N

while(zeros != deque()):
    a = zeros.popleft()
    if(adj[a]):
        for b in adj[a]:
            h[b] -= 1
            if h[b] == 0:
                zeros.append(b)
                dp[b] = max(dp[a] + 1, dp[b])
                
'''
dp = [0]*N
for a in ans:
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[a] + 1, dp[b])

print(dp[ans[-1]])
'''
print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]


'''
N, M = mi()
x = li2(M)


dp = [[0, []] for i1 in range(N+1)]


for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    if dp[x[i][1]][1] != []:
        for a in dp[x[i][1]][1]:
            dp[a][0] = max(dp[x[i][1]][0] + 1, dp[a][0])

print(dp)
print(max([row[0] for row in dp])) 
'''
from collections import deque
N, M = mi()
x = li2(M)

h = [0]*N
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    h[x[i][1]] += 1
    adj[x[i][0]].append(x[i][1])

zeros = deque([])
ans = []
for i in range(N):
    if h[i] == 0:
        zeros.append(i)
        ans.append(i)

while(zeros != deque()):
    a = zeros.popleft()
    if(adj[a]):
        for b in adj[a]:
            h[b] -= 1
            if h[b] == 0:
                zeros.append(b)
                ans.append(b)



dp = [0]*N


for a in ans:
    
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[a] + 1, dp[b])

print(dp[ans[-1]])

Solution (Python):

import sys


sys.setrecursionlimit(1000000)

N, M = map(int, input().split())


class Graph(object):
    def __init__(self, n: int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def add_edge(self, v1: int, v2: int, undirected=False):
        self.adjacency_dict[v1].append(v2)
        if undirected:
            self.adjacency_dict[v2].append(v1)


def find_longest(v):
    """ vからの有向最長パスをの長さをdp[v]とする """
    global dp
    if dp[v] > 0:
        return dp[v]

    res = 0
    for nv in g.adjacency_dict[v]:
        res = max(res, find_longest(nv) + 1)

    dp[v] = res
    return res


g = Graph(N)
for i in range(M):
    x, y = map(int, input().split())
    g.add_edge(x - 1, y - 1)


dp = [-1] * N

for v in range(N):
    if len(g.adjacency_dict[v]) == 0:
        dp[v] = 0


for v in range(N):
    find_longest(v)

print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

n,m = map(int,input().split())
g = [[] for i in range(n)]


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

print(max(dp))

Solution (Python):
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))

Solution (Python):
import sys

sys.setrecursionlimit(500000)


N,M = list(map(int,input().split()))

e_list = [[] for i in range(N)]

for i in range(M):
    x,y = list(map(int,input().split()))
    x,y = x-1,y-1
    e_list[x].append(y)

memo = [-1]*N

def DFS(v):
    if memo[v]!=-1:
        return memo[v]
    if len(e_list[v])==0:
        memo[v] = 0
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    memo[v] = res
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    if res>ans:
        ans = res
print(ans)

Solution (Python):
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9+7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)

Solution (Python):
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
import sys
sys.setrecursionlimit(10**7)

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)

Solution (Python):
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)

Solution (Python):
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)]))

Solution (Python):
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)]))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)

def main():
    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)
        
    dist = [-1 for _ in range(N)]
            
    def dfs(s):
        if dist[s] != -1:
            return dist[s]
        else:
            ret = 0
            for fol in edge[s]:
                ret = max(ret,dfs(fol)+1)
            dist[s] = ret
            return ret

    for i in range(N):
        dfs(i)
        
    print(max(dist))
    
if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
M = mod = 10**9 +7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]


def dfs(root):
    global ans,g
    if ans[root]:return 

    temp = 0
    for j in g[root]:dfs(j)
    if len(g[root]):temp = max(ans[j] for j in g[root])
    ans[root] = 1 + temp

n,m = li()
g = defaultdict(set)
for i in range(m):
    a,b = li()
    g[a].add(b)

ans = [0]*(n + 1)

for j in range(1,n + 1):
    if not ans[j]:dfs(j)

print(max(ans) - 1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, M = MAP()

gout = [[] for _ in range(N)]
deg = [0]*N
for _ in range(M):
	x, y = MAP()
	gout[x-1].append(y-1)
	deg[y-1] += 1
topo = [v for v in range(N) if deg[v]==0]
path_len = [0]*N
deq = deque(topo)
ans = 0
while deq:
    v = deq.popleft()
    for t in gout[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            path_len[t] = path_len[v] + 1
            ans = path_len[t]

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, M = MAP()

gout = [[] for _ in range(N)]
deg = [0]*N
for _ in range(M):
	x, y = MAP()
	gout[x-1].append(y-1)
	deg[y-1] += 1
topo = [v for v in range(N) if deg[v]==0]
path_len = [0]*N
deq = deque(topo)
ans = 0
while deq:
    v = deq.popleft()
    for t in gout[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            path_len[t] = path_len[v] + 1
            ans = path_len[t]

print(ans)

Solution (Python):
n, m = map(int, input().split())
parents = [[] for _ in range(n)]
outdegree = [0] * n
indegree = [0] * n
path_root = [0] * n
for _ in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  parents[y].append(x)
  outdegree[x] += 1
  indegree[y] += 1
stack = [i for i in range(n) if outdegree[i] == 0]
while stack:
  vertex = stack.pop()
  path_length = path_root[vertex] + 1
  for parent in parents[vertex]:
    outdegree[parent] -= 1
    indegree[vertex] -= 1
    path_root[parent] = max(path_root[parent], path_length)
    if outdegree[parent] == 0:
      stack.append(parent)
print(max(path_root))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
dest = [[] for _ in range(n)]
comein = [0 for _ in range(n)]
ro = [True for _ in range(n)]
dp = [0 for _ in range(n)]
for _ in range(m):
	x, y = map(int, input().split())
	dest[x-1].append(y-1)
	comein[y-1] += 1
	ro[y-1] = False

def search(leaf):
	global dp
	for i in dest[leaf]:
		comein[i] -= 1
		dp[i] = max(dp[i], dp[leaf] + 1)
		if comein[i] == 0:
			search(i)
	return

for j in range(n):
	if ro[j] == True:
		search(j)

print(max(dp))

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
in_path = defaultdict(lambda: [])
out_path = defaultdict(lambda: [])

for m in range(M):
    x, y = map(int, input().split())
    in_path[y].append(x)
    out_path[x].append(y)

check = [False]*(N+1)
memo = [0]*(N+1)


def dp(i):
    if check[i]:
        return memo[i]
    else:
        check[i] = True
        if not out_path[i]:
            return 0
        else:
            max_path = 0
            for node in out_path[i]:
                max_path = max(dp(node), max_path)
            max_path += 1
            memo[i] = max_path
            return max_path


ans = 0
for i in range(1, N+1):
    ans = max(ans, dp(i))

print(ans)

Solution (Python):
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))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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 e[i] and dis[i] < 0 :
        dfs(i)
print(max(dis))

Solution (Python):
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))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

N, M = map(int, input().split())

not_start_point = set()
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    not_start_point.add(y)
    to_point[x].append(y)

start_point = set(range(N)) - not_start_point

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0


def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

ans = 0
for s in start_point:
    ans = max(ans, dp(s))

print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

N, M = map(int, input().split())

to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0


def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

for i in range(N):
    dp(i)

print(max(dp_memo))

Solution (Python):
from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
to = [0]*n
dp = [0]*n
for _ in range(m):
    x,y = map(int,input().split())
    path[x-1].add(y-1)
    to[y-1] += 1

que = deque()
for i in range(n):
    if to[i] == 0:
        que.append(i)
ans = 0
while que:
    p = que.popleft()
    for i in path[p]:
        to[i] -= 1
        if to[i] == 0:
            que.append(i)
        dp[i] = max(dp[i], dp[p] + 1)
        ans = max(ans, dp[i])
print(ans)

Solution (Python):
import sys

def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = 0
    for b in xy[a]:
      if dp[b]:
        num = dp[b]
      else:
        num = cal(b)
        dp[b] = num
      if num+1 > ans:
        ans = num+1
    return ans
  return 0

if __name__ == "__main__":
  sys.setrecursionlimit(100000)
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)
def chmax(a,b):
  if a>=b:
    return a
  else:
    return b
dp=[-1]*N
def rec(v):
  if dp[v]!=-1:
    return dp[v]
  ans=0
  for i in G[v]:
    ans=chmax(ans,rec(i)+1)
  dp[v]=ans
  return dp[v]
    
ans=0
for i in range(N):
  ans=chmax(ans,rec(i))
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = sys.stdin.readline
def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    else:
        return b
def main():  
    
    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 = chmax(ans, rec(nv) + 1)
        dp[v] = ans
        return dp[v]
    
    
    ans = 0
    for v in range(N):
        ans = chmax(ans, rec(v))
    
    print(ans)
main()

Solution (Python):
import math
import sys
sys.setrecursionlimit(1000000)
dp = [-1]*(100*1000+1)
tab = [[] for x in range(100*1000+1)]

def get_max(root):
    if(dp[root] > -1): return dp[root]
    
    mi = 0
    for nei in tab[root]:
        mi = max(mi,get_max(nei)+1)
    dp[root] = mi
    return dp[root]
def main():
    n,m = map(int,input().split())
    
    for x in range(m):
        a,b = map(int,input().split())
        a-=1;b-=1
        tab[a].append(b)
    
    for x in range(n):
        get_max(x) 
    
    print(max(dp))
main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
sys.setrecursionlimit(10**6)

N, M = input_nums()

G = {}
for i in range(N):
    G[i] = []

for i in range(M):
    x, y = input_nums()
    x -= 1
    y -= 1
    G[x].append(y)

dp = [-1 for _ in range(N+1)]

def rec(v: int):
    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

res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    x, y = map(lambda z: int(z)-1, input().split())
    G[x].append(y)

ans = [-1]*n
def dfs(i):
    if ans[i] != -1:
        return ans[i]
    if len(G[i]) == 0:
        ans[i] = 0
        return ans[i]
    res = 0
    for j in G[i]:
        res = max(res, dfs(j))
    ans[i] = res + 1
    return ans[i]

for i in range(n):
    dfs(i)

print(max(ans))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    x, y = map(lambda z: int(z)-1, input().split())
    G[x].append(y)

ans = [-1]*n
def dfs(i):
    if ans[i] != -1:
        return ans[i]
    if len(G[i]) == 0:
        ans[i] = 0
        return ans[i]
    res = 0
    for j in G[i]:
        res = max(res, dfs(j))
    ans[i] = res + 1
    return ans[i]

for i in range(n):
    dfs(i)

print(max(ans))

Solution (Python):








import sys

sys.setrecursionlimit(10 ** 5 + 10)





def resolve():
    
    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)


resolve()

Solution (Python):
import sys
sys.setrecursionlimit(100000000)

inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if g[x] == []:
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(1,N+1):
    g[i] = []

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from collections import deque
import numpy as np

n, m = map(int, input().split())
path = [[] for i in range(n + 1)]
inbounds = [0] * (n + 1)

for i in range(m):
    x, y = map(int, input().split())
    path[x].append(y)
    inbounds[y] += 1


topological = list(v for v in range(1, n + 1) if inbounds[v] == 0)
deq = deque(topological)

while deq:
    v = deq.popleft()
    for t in path[v]:
        inbounds[t] -= 1
        if inbounds[t] == 0:
            deq.append(t)
            topological.append(t)


dp = np.zeros(n + 1, dtype='int64')

for v in topological:
    for t in path[v]:
        dp[t] = max(dp[t], dp[v] + 1)

print(dp.max())

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

N,M = map(int,input().split())
G = [[] for i in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    G[x].append(y)

dp = [-1]*(N+5)
def rec(v):
    if dp[v] != -1:
        return dp[v]

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

Solution (Python):
N, M = map(int, input().split())
xys = [list(map(int, input().split())) for _  in range(M)]

children = [[] for _ in range(N)]
for x, y in xys:
    children[x-1].append(y-1)

has_no_parent = [True] * N
has_no_child = [True] * N
for x, y in xys:
    has_no_child[x-1] = False
    has_no_parent[y-1] = False

dp = [None] * N
for node in range(N):
    if has_no_child[node]:
        dp[node] = 0

for node in range(N):
    if dp[node] is not None:
        continue
    stack = []
    stack.append(node)
    while stack:
        parent = stack[-1]
        all_children_defined = True
        for child in children[parent]:
            if dp[child] is None:
                stack.append(child)
                all_children_defined = False
        if all_children_defined:
            stack.pop()
            dp[parent] = max([dp[child] + 1 for child in children[parent]])

print(max(dp))