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

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

def dfs(x): 
    if dp[x] != -1:
        return dp[x] 
    ans = 0
    for e in graph[x]: 
        ans = max(ans,1 + dfs(e))
    dp[x] = ans
    return ans 

n,m = list(map(int, input().split()))

graph = [[] for i in range(n+1)]
dp = [-1]
for i in range(1,n+1):
    dp.append(-1) 

for _ in range(m): 
    a,b = map(int, input().split())
    graph[a].append(b)
    
    
ans=0

for i in range(1,n+1):
    ans=max(ans,dfs(i))
print(ans)

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

Solution (Python):
from _collections import defaultdict
import sys
import collections
import sys
sys.setrecursionlimit(10**6)


def get_ls():
    return list(map(int, input().split()))


def longest_path_util(node, graph, dp):

    res = 0

    if dp[node] != -1:
        return dp[node]

    for neib in graph[node]:
        res = max(res, longest_path_util(neib, graph, dp) + 1)

    dp[node] = res

    return dp[node]


graph = defaultdict(list)

[n, k] = get_ls()

dp = [-1] * n

for _ in range(k):
    [x, y] = get_ls()
    graph[x - 1].append(y - 1)

ans = 0

for i in range(n):
    ans = max(ans, longest_path_util(i, graph, dp))

print(ans)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

dp=[-1]*100100
G=[[] for _ in range(100100)]

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

def main():
  n,k=LI()

  for _ in range(k):
    a,b=LI()
    a-=1
    b-=1
    G[a].append(b)

  return max(dfs(v) for v in range(n))


print(main())

Solution (Python):
import collections
import sys
sys.setrecursionlimit(10**6)

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]

def tsort(N,G,dic):
    res = 0
    
    if dic[N] != -1:
        return dic[N]
    for node in G[N]:
        res = max(res,tsort(node,G,dic)+1)
    dic[N] = res
    return dic[N]

[n,m] = getlsi()
dic_next = collections.defaultdict(list)
dp = [-1] * n
for i in range(m):
    [x,y] = getlsi()
    dic_next[x-1].append(y-1)
ans = 0
for i in range(n):
    ans = max(ans,tsort(i,dic_next,dp))
print(ans)

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

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

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


def dfs(v):
    global dp
    if dp[v] != -1:
        return dp[v]
    res = 0
    for next_v in e[v]:
        res = max(dfs(next_v) + 1, res)
    dp[v] = res
    return res


def main():
    N, M = map(int, input().split())
    global e
    e = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
    global dp
    dp = [-1]*N
    ans = -1
    for v in range(N):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import collections
import sys
sys.setrecursionlimit(10**6)

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]

def tsort(N,G,dic):
    res = 0
    
    if dic[N] != -1:
        return dic[N]
    for node in G[N]:
        res = max(res,tsort(node,G,dic)+1)
    dic[N] = res
    return dic[N]

[n,m] = getlsi()
dic_next = collections.defaultdict(list)
dp = [-1] * n
for i in range(m):
    [x,y] = getlsi()
    dic_next[x-1].append(y-1)
ans = 0
for i in range(n):
    ans = max(ans,tsort(i,dic_next,dp))
print(ans)

Solution (Python):
from collections import deque


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    input_edges = [0]*N
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        input_edges[v] += 1
    queue = deque()
    dp = [-1] * N
    for i, input_edge in enumerate(input_edges):
        if input_edge == 0:
            queue.appendleft(i)
            dp[i] = 0
    topological_sorted = []
    while queue:
        v = queue.pop()
        topological_sorted.append(v)
        for other_side in e[v]:
            input_edges[other_side] -= 1
            if input_edges[other_side] == 0:
                queue.appendleft(other_side)
    for v in topological_sorted:
        for other_side in e[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


if __name__ == "__main__":
    main()

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

Solution (Python):
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 = list(map(int, input().split()))
    d[a].append(b)
ans=0
for i in range(1,n+1):
    ans=max(ans,f(i))
print(ans)

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): 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 LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N,M = MI()
to = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = MI()
    to[x].append(y)
dp = [-1]*(N+1)
def rec(i):
    if dp[i] != -1:
        return dp[i]
    ret = 0
    if to[i]:
        for v in to[i]:
            ret = max(ret,rec(v)+1)
    dp[i] = ret
    return ret

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

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(10000)

def main():
	n, m = rli()
	G = [[] for i in range(n+1)]
	for _ in range(m):
		u, v = rli()
		G[u].append(v)
	ans = 0
	memo = [-1 for _ in range(n+1)]

	def longest(v):
		if memo[v] > -1:
			return memo[v]
		pathlen = 0
		for nbhr in G[v]:
			pathlen = max(pathlen, 1 + longest(nbhr))
		memo[v] = pathlen
		return pathlen

	for i in range(1, n+1):
		ans = max(ans, longest(i))

	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

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

Solution (Python):
from collections import defaultdict, deque

n, m = map(int, input().split())
xy = []
node = defaultdict(int)
branch = defaultdict(list)
dp = [0]*(n+1) 

for _ in range(m):
    x, y = map(int, input().split())
    xy.append([x, y])
    node[y] += 1 
    branch[x].append(y) 


res = []
queue = deque([i for i in range(1, n+1) if node[i]==0])
while queue:
    v = queue.popleft()
    res.append(v)
    
    for u in branch[v]:
        dp[u] = max(dp[u], dp[v]+1)
        node[u] -= 1
        if node[u] == 0:
            queue.append(u)



print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
adj=[]
dp=[0 for i in range(0,n+1)]
def dfs(i,p,adj,dp):
    
    
    if dp[i]!=0:
        return dp[i]
    for j in (adj[i]):
        if j==p:
            continue 
        else:
            dfs(j,i,adj,dp)
            dp[i]=max(dp[i],1+dp[j])
    return dp[i]
    
for i in range(n+1):
    adj.append([])
for _ in range(m):
    u,v=map(int,input().split())
    adj[u].append(v)

for i in range(1,n+1):
    if dp[i]==0:
        dfs(i,i,adj,dp)

print(max(dp))

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

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w=1):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

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

edgenum=[0]*(n+1)
edge=[[] for i in range(n+1)]

for i in range(m):
    x,y=xy[i]
    edgenum[x]+=1
    edge[y].append(x)



d=deque()
itta=[0]*(n+1)
for i in range(n):
    i+=1
    if edgenum[i]==0:
        d.append(i)


while d:
    now=d.popleft()
    
    

    for i in edge[now]:
        edgenum[i]-=1
        if edgenum[i]==0:
            d.append(i)
            itta[i]=max(itta[i],itta[now]+1)

print(max(itta))

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    graph=[[]for _ in range(n)]
    deg=[0]*n 
    for x,y in XY:
        graph[x-1].append(y-1)
        deg[y-1]+=1
    que=deque()
    for v in range(n):
        if deg[v]==0:
            que.append(v)
    dp=[0]*n
    while que:
        v=que.popleft()
        for nv in graph[v]:
            deg[nv]-=1
            if deg[nv]==0:
                que.append(nv)
                dp[nv]=max(dp[nv],dp[v]+1)
    ans=0
    for v in range(n):
        ans=max(ans,dp[v])
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    graph=[[]for _ in range(n)]
    deg=[0]*n 
    for x,y in XY:
        graph[x-1].append(y-1)
        deg[y-1]+=1
    que=deque()
    for v in range(n):
        if deg[v]==0:
            que.append(v)
    dp=[0]*n
    while que:
        v=que.popleft()
        for nv in graph[v]:
            deg[nv]-=1
            if deg[nv]==0:
                que.append(nv)
                dp[nv]=max(dp[nv],dp[v]+1)
    ans=0
    for v in range(n):
        ans=max(ans,dp[v])
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
memo=dict()
def rec(v):
    if v in memo:return memo[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    memo[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
memo=dict()
def rec(v):
    if v in memo:return memo[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    memo[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func
@memoize
def rec(v):
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
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 res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n 
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache
sys.setrecursionlimit(10**6)
@lru_cache(maxsize=None)
def rec(v):
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
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 res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n 
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def dfs(u):
    if(dp[u]!=-1):
        return dp[u]
    for i in d[u]:
        if(dp[i]!=-1):
            dp[u]=max(dp[u],dp[i]+1)
        else:
            dp[u]=max(dp[u],dfs(i)+1)
    return max(dp[u],0)
from collections import defaultdict as dd
n,m=map(int,input().split())
d=dd(list)
for i in range(m):
    u,v=map(int,input().split())
    d[u].append(v)
dp=dd(lambda: -1)
mx=0
for i in range(1,n+1):
    if(dp[i]==-1):
        dp[i]=dfs(i)
    mx=max(mx,dp[i])
print(mx)

Solution (Python):









import os
import sys
from collections import deque


def chmax(s,t):
    if s<t:
        return t
    else:
        return s


def longest_path(ans_list,node_list,lon_path):
    while ans_list:
        u = ans_list.pop()
        for v,_from in enumerate(node_list):
            if u in _from and lon_path[v]<lon_path[u]+1:
                lon_path[v]=lon_path[u]+1
    print(max(lon_path))

def main():
    n,m = map(int,input().split())
    node_list = [[] for _ in range(n+1)]
    to_count = [0]*(n+1)
    for _ in range(m):
        s,t = map(int,input().split())
        node_list[s].append(t)
        to_count[t]+=1
    q = deque()
    for i,x in enumerate(to_count):
        if x==0:
            q.append(i)
    q.popleft()
    distance = [0]*(n+1)
    ans_list = []
    while q:
        u = q.popleft()
        for v in node_list[u]:
            to_count[v]-=1
            if to_count[v]==0:
                q.append(v)
                distance[v]=chmax(distance[v],distance[u]+1)
        ans_list.append(u)
    print(max(distance))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import collections


input = sys.stdin.readline

def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    return b

def main():
    
    N, M = map(int, input().split())
    
    lst_edge = [[] for _ in range(N)]
    
    deg = [0] * N
    for _ in range(M):
        x, y = map(int, input().split())
        
        lst_edge[x-1].append(y-1)
        deg[y-1] += 1

    
    que = collections.deque()
    for v in range(N):
        if deg[v] == 0:
            que.append(v)

    
    dp = [0] * N

    
    
    while que:
        v = que.popleft()
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            
            deg[nv] -= 1
            if deg[nv] == 0:
                
                que.append(nv)
                
                dp[nv] = chmax(dp[nv], dp[v] + 1)

    print(max(dp))

main()

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

def rec(i, dp, nodes):
    
    if dp[i] != -1:
        return dp[i]

    res = 0
    for next in nodes[i]:
        res = max(res, rec(next, dp, nodes) + 1)
    dp[i] = res
    return res

def main():
    input = sys.stdin.readline  
    N, M = map(int, input().rstrip().split())
    nodes = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().rstrip().split())
        nodes[x-1].append(y-1)

    
    dp = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, rec(i, dp, nodes))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

import threading
sys.setrecursionlimit(10**5)
threading.stack_size(10**8)
def dfs(x):
    global l,adj,v
    if v[x]==1:
        return(l[x])
    v[x]=1
    c=0
    for i in adj[x]:
        c=max(c,dfs(i)+1)
    l[x]=c
    return c
def main():
    global l,adj,v
    n,m=map(int,input().split())
    l=[0]*(n+1)
    v=[0]*(n+1)
    adj=[]
    for i in range(n+1):
        adj.append([])
    for i in range(m):
        x,y=map(int,input().split())
        adj[x].append(y)
    ans=0
    for i in range(1,n+1):
        if not v[i]:
            ans=max(ans,dfs(i))
    print(ans)
t=threading.Thread(target=main)
t.start()
t.join()

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

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M = geta(int)
    g = defaultdict(lambda: [])
    for _ in range(M):
        x, y = geta(int)
        g[x].append(y)

    dp = [-1] * (N + 1)

    def dfs(i):
        if dp[i] == -1:
            dist = 0
            for j in g[i]:
                dist_j = 1 + dfs(j)
                if dist_j > dist: dist = dist_j
            dp[i] = dist
        return dp[i]

    ans = 0
    for i in range(1, N + 1):
        tmp = dfs(i)
        if tmp > ans: ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict, deque

n,m = map(int,input().split())
edge = []
for _ in range(m):
    x,y = map(int,input().split())
    edge.append((x,y))

in_cnt = defaultdict(int)
outs = defaultdict(list)
for x,y in edge:
    in_cnt[y-1]+= 1
    outs[x-1].append(y-1)

res = []
queue = deque([i for i in range(n) if in_cnt[i] == 0])

while  len(queue)> 0:
    node = queue.popleft()
    res.append(node)
    for next_node in outs[node]:
        in_cnt[next_node] -= 1
        if in_cnt[next_node] == 0:
            queue.append(next_node)

dp = [0]*n

for i in range(n):
    for nv in outs[res[i]]:
        dp[nv] =max(dp[nv],dp[res[i]] + 1)
print(max(dp))

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

longs = []
edges = {}
def graph_DP(node_to):
    global longs
    if longs[node_to] != -1:
        return longs[node_to]
    else:
        nodes_next = edges[node_to]
        if not nodes_next:
            longs[node_to] = 0
            return 0
        else:
            long_max_t = 0
            for node_next in nodes_next:
                if longs[node_next] != -1:
                    long_max_t = max(long_max_t, longs[node_next] + 1)
                else:
                    long_max_t = max(long_max_t, graph_DP(node_next) + 1)
            longs[node_to] = long_max_t
            return long_max_t

def main():
    global longs, edges
    n, m = map(int, input().split())
    edges = {e:set() for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].add(g)
    longs = [-1] * (n + 1)

    for i1 in range(1, n + 1):
        if longs[i1] == -1:
            graph_DP(i1)
    print(max(longs))

if __name__ == '__main__':
    main()

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

longs = []
edges = {}
def graph_DP(node_to, long):
    global longs
    if longs[node_to] != -1:
        return longs[node_to]
    else:
        nodes_next = edges[node_to]
        if not nodes_next:
            longs[node_to] = 0
            return 0
        else:
            long_max_t = 0
            for node_next in nodes_next:
                if longs[node_next] != -1:
                    long_max_t = max(long_max_t, longs[node_next] + 1)
                else:
                    long_max_t = max(long_max_t, graph_DP(node_next, 0) + 1)
            longs[node_to] = long_max_t
            return long_max_t

def main():
    global longs, edges
    n, m = map(int, input().split())
    edges = {e:set() for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].add(g)
    longs = [-1] * (n + 1)

    for i1 in range(1, n + 1):
        if longs[i1] == -1:
            graph_DP(i1, 0)
    print(max(longs))

if __name__ == '__main__':
    main()

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

Solution (Python):

import sys

sys.setrecursionlimit(10**9)


def dfs(v, graph, memo):
    if v in memo:
        return memo[v]

    if graph[v]:
        res = float("-inf")
        for child in graph[v]:
            res = max(res, dfs(child, graph, memo) + 1)
        memo[v] = res
    else:
        res = 0
        memo[v] = 0

    return memo[v]


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    graph = [[] for _ in range(N)]
    for i in range(M):
        graph[x[i]-1].append(y[i]-1)

    memo = {}

    res = float("-inf")
    for i in range(N):
        res = max(res, dfs(i, graph, memo))
    print(res)



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    x = [int()] * (M)  
    y = [int()] * (M)  
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()