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

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines






def main():
	n,m=map(int,input().split())
	
	inc=[0]*(n)
	out=[[] for _ in range(n)]
	
	for i in range(m):
		x,y=map(int,input().split())
		inc[y-1]+=1
		out[x-1].append(y-1)
	
	q={i for i,c in enumerate(inc) if c==0}
	C=[]
	
	while q:
		k=q.pop()
		C.append(k)
		for i in out[k]:
			inc[i]-=1
			if inc[i]==0:
				q.add(i)
	
	ans=[0]*n
	
	for i in C:
		for j in out[i]:
			ans[j]=max(ans[j],ans[i]+1)
	
	
	print(max(ans))
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

    def dfs(v):
        """最長有向パスに含まれる頂点数"""
        if memo[v] != -1:
            return memo[v]

        ret = 0
        for u in g[v]:
            ret = max(ret, dfs(u))
        ret += 1  
        memo[v] = ret
        return ret

    n, m = map(int, readline().split())

    g = tuple(set() for _ in range(n))
    for _ in range(m):
        x, y = (int(c) - 1 for c in input().split())
        g[x].add(y)

    memo = [-1] * n

    ret = 0
    for i in range(n):
        ret = max(ret, dfs(i))
    print(ret - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, deque


def solve():
    N, M = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    G = defaultdict(list)
    in_edge = [0] * N
    for x, y in zip(m, m):
        G[y-1].append(x-1)
        in_edge[x-1] += 1

    dp = [0] * N
    q = deque(i for i, x in enumerate(in_edge) if not x)
    q_enqueue = q.append
    q_dequeue = q.popleft
    while(q):
        x = q_dequeue()
        for j in G[x]:
            in_edge[j] -= 1
            if not in_edge[j]:
                q_enqueue(j)
                if dp[j] < dp[x] + 1:
                    dp[j] = dp[x] + 1
    return max(dp)


if __name__ == "__main__":
    answer = solve()
    print(answer)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**7)

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, m = na()
memo = [-1] * n
def dp(v):
    if memo[v] != -1:
        return memo[v]
    if G[v]:
        memo[v] = max(dp(i) for i in G[v]) + 1
    else:
        memo[v] = 0
    return memo[v]


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(max([dp(i) for i in range(n)]))

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**7)

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, m = na()
memo = [-1] * n
def dp(v):
    if memo[v] != -1:
        return memo[v]
    if G[v]:
        memo[v] = max(dp(i) for i in G[v]) + 1
    else:
        memo[v] = 0
    return memo[v]


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(max([dp(i) for i in range(n)]))

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)

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

in_ = set()
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    in_.add(b)

dist = [-1]*n

from collections import deque
def dfs(cur):
    if dist[cur] != -1:
        return dist[cur]
    r = 0
    for to in G[cur]:
        r = max(r, dfs(to)+1)
    dist[cur] = r
    return r

for i in range(n):
    if i in in_:
        continue
    dfs(i)

ans = max(dist)

print(ans)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)

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

in_ = set()
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    in_.add(b)

dist = [-1]*n

from collections import deque
def dfs(cur):
    if dist[cur] != -1:
        return dist[cur]
    r = 0
    for to in G[cur]:
        r = max(r, dfs(to)+1)
    dist[cur] = r
    return r

for i in range(n):
    if i in in_:
        continue
    dfs(i)

ans = max(dist)

print(ans)

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

def search(index: int, dp: list, graph: list) -> int:
    if dp[index] != -1:
        return dp[index]+1

    tmp = 0
    for d in graph[index]:
        tmp = max(tmp, search(d, dp, graph))

    dp[index] = tmp
    return tmp+1


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)

ans = 0
for i in range(N):
    ans = max(ans, search(i, dp, graph))

print(ans-1)

Solution (Python):
from collections import defaultdict, deque

n, m = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(m)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1 - 1].append(v2 - 1)
    ins[v2 - 1] += 1


q = deque(v1 for v1 in range(n) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
            
LP = {v:0 for v in res}
for v0 in res:
    for v1 in outs[v0]:
        LP[v1] = max(LP[v1], LP[v0] + 1)
print(max(LP.values()))

Solution (Python):

from collections import deque,defaultdict

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

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

in_cnt=defaultdict(int) 
outs=defaultdict(list) 

for out_node,in_node in edges:
    in_cnt[in_node-1]+=1
    outs[out_node-1].append(in_node-1)

topo_sort=[] 
q=deque([i for i in range(n) if in_cnt[i]==0]) 

dp=[0]*n
while q:
    v1=q.popleft()
    topo_sort.append(v1)
    for v2 in outs[v1]:
        in_cnt[v2]-=1
        dp[v2]=dp[v1]+1
        if in_cnt[v2]==0:
            q.append(v2)
print(max(dp))

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

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)

def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)
    
    for i in range(len(g)):
        if i not in visited:
            dfs(i)
        
    return topological_list[::-1]

T = topological_sort(G)
dist = [0]*N
for n in T:
    for v in G[n]:
        dist[v] = max(dist[v],dist[n]+1)       
        
print(max(dist))

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

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

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

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

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

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

g=[[] 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
 g[x].append(y)

def rec(x):
 if memo[x]!=-1:
  return memo[x]

 res=0
 for i in g[x]:
  res=max(res,rec(i)+1)

 memo[x]=res
 return res

ans=0
for v in range(n):
 ans=max(ans,rec(v))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)


def dfs(v, graph, memo):
    if memo[v] != -1:
        return memo[v]
    ret = 0
    for c in graph[v]:
        ret = max(ret, dfs(c, graph, memo) + 1)
    memo[v] = ret
    return ret


def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        graph[x].append(y)
    memo = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, dfs(i, graph, memo))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


def create_graph(V: int, edges: np.array, dtype=None):
    """csr_matrix を作成する

    もし精度が足りない場合は dtype=object にする。
    """
    return csr_matrix((edges[:, 2], (edges[:, 0], edges[:, 1])),
                      shape=(V, V), dtype=dtype)


def main() -> None:
    N, M = map(int, input().split())
    edges = []
    adj_list = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        edges.append([x-1, y-1, 1])
        adj_list[x-1].append(y-1)
    graph = create_graph(N, np.asarray(edges))
    _, labels = connected_components(
        csgraph=graph, directed=True,
        connection="strong", return_labels=True)
    order = [(x, i) for i, x in enumerate(labels)]
    order.sort(reverse=True)
    dp = [0] * N
    for _, i in order:
        for v in adj_list[i]:
            dp[v] = max(dp[v], dp[i] + 1)
    print(max(dp))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def path(start):
    if dp[start]!=-1:
        return dp[start]
    visited[start]=1
    maxi=-1
    for i in adjacency_list[start]:
        maxi=max(maxi,path(i))
    dp[start]=maxi+1
    return dp[start]
N,M=map(int,input().split())
dp=[-1]*(N+1)
visited=[0]*(N+1)
adjacency_list=[]
for i in range(N+1):
    adjacency_list.append([])

for r in range(M):
    u,v=map(int,input().split())
    adjacency_list[u].append(v)

for i in range(1,N+1):
    if len(adjacency_list[i])==0:
        dp[i]=0

for i in range(1,N+1):
    if (visited[i]==0):
        path(i)
print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=list(s)
    memo=[0]*N
    def saiki(v):
        if memo[v]:
            return memo[v]
        tmp=0
        for nv in edge[v]:
            memo[v]=max(memo[v],saiki(nv)+1)
            tmp=max(tmp,memo[v])
        return tmp
    ans=0
    for v in que:
        ans=max(ans,saiki(v))
    print(ans)
    
    

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=list(s)
    memo=[0]*N
    def saiki(v):
        if memo[v]:
            return memo[v]
        tmp=0
        for nv in edge[v]:
            memo[v]=max(memo[v],saiki(nv)+1)
            tmp=max(tmp,memo[v])
        return tmp
    ans=0
    for v in que:
        ans=max(ans,saiki(v))
    print(ans)
    
    

if __name__ == '__main__':
    main()

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

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


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

move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

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

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)

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

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

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

Solution (Python):
V,m = map(int,input().split())

from collections import defaultdict
g = defaultdict(list)
deg = defaultdict(int)
for _ in range(m):
    x,y = map(int,input().split())
    g[x-1].append(y-1)
    deg[y-1] += 1
    






from collections import deque
ans = list(v for v in range(V) if deg[v]==0)
deq = deque(ans)
used = [0]*V
while deq:
    v = deq.popleft()
    for t in g[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)



dp = [0 for i in range(V)]

for a in ans:
    for b in g[a]:
        dp[b] = dp[a] + 1

print(max(dp))

Solution (Python):
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    
    
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)

    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examG()

"""

"""

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline  
from copy import deepcopy
from functools import lru_cache
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
s = set()
for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    s.add(y)
    graph[x].append(y)

@lru_cache(maxsize = None)
def dfs(x):
    if not graph[x]:
        return 0
    stack = deepcopy(graph[x])
    ret = 0
    while stack:
        now = stack.pop(0)
        ret = max(ret,dfs(now)+1)
    return ret

ans = 0
for i in range(N):
    if i not in s:
        ans = max(ans,dfs(i))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

n,m = mii()

arr=[[] for i in range(n)]
deg=[0 for i in range(n)]
dp = [0]*(n+1)


for i in range(m):
    x,y = mii()
    arr[x-1].append(y-1)
    deg[y-1]+=1







ans = list(i for i in range(n) if deg[i]==0)
deq = deque(ans)
used = [0]*m

while deq:
    v = deq.popleft()
    for t in arr[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)




for i in ans:
    ari = arr[i]
    
    for j in range(len(ari)):
        dp[ari[j]] = max(dp[i]+1,dp[ari[j]])
    
print(max(dp))

Solution (Python):

import queue
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
adj=[[] for _ in range(N)]
deg_in=[0]*N

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    adj[x].append(y)
    deg_in[y]+=1
    
dp=[0]*N
L=[]
q=queue.Queue()

for i in range(N):
    if deg_in[i]==0:
        q.put(i)

while not q.empty():
    v=q.get()
    L.append(v)
    for to in adj[v]:
        deg_in[to]-=1
        if deg_in[to]==0:
            q.put(to)
            dp[to]=max(dp[to],dp[v]+1)
        
print(max(dp))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, readline().split())
outdeg = {i: [] for i in range(N)}
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    outdeg[a].append(b)

dp = [-1] * (N)


def rec(s):
    if dp[s] != -1:
        return dp[s]

    res = 0
    for t in outdeg[s]:
        res = max(res, rec(t)+1)
    dp[s] = res
    return res


ans = 0
for s in range(N):
    ans = max(ans, rec(s))
print(ans)

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

N,M=map(int,input().split())
adj=[[] for _ in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    adj[x].append(y)
    
dp=[0]*N

def rec(ii):
    new=0
    if len(adj[ii])==0:
        return 0
    for to in adj[ii]:
        if dp[to]!=0:
            new=dp[to]
        else:
            new=rec(to)
        dp[ii]=max(new+1,dp[ii])
    return dp[ii]
        
for i in range(N):
    rec(i)
    
print(max(dp))

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

N,M=map(int,input().split())
adj=[[] for _ in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    adj[x].append(y)
    
dp=[-1]*N
for i in range(N):
    if len(adj[i])==0:
        dp[i]=0

def rec(ii):
    new=0
    for to in adj[ii]:
        if dp[to]!=-1:
            new=dp[to]
        else:
            new=rec(to)
        dp[ii]=max(new+1,dp[ii])
    return dp[ii]
        
for i in range(N):
    rec(i)
    
print(max(dp))

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

N,M=map(int,input().split())
adj=[[] for _ in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    adj[x].append(y)
    
dp=[-1]*N
for i in range(N):
    if len(adj[i])==0:
        dp[i]=0

def rec(ii):
    new=0
    for to in adj[ii]:
        if dp[to]!=-1:
            new=dp[to]
        else:
            new=rec(to)
        dp[ii]=max(new+1,dp[ii])
    return dp[ii]
        
for i in range(N):
    rec(i)
    
print(max(dp))

Solution (Python):
from collections import deque
import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
dp = [-1 for i in range(n+1)]
def cul(x):
    if dp[x] != -1:
        return dp[x]
    else:
        if len(adjacent_list[x]) == 0:
            return 0
        dp[x] = max([cul(i) + 1 for i in adjacent_list[x]])
        return dp[x]
for i in range(1,n+1):
    cul(i)
print(max(dp))

Solution (Python):

"""
Created on Fri Jan 24 14:37:00 2020

@author: matsui
"""

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

g=dict()
h=[0]*(N+1)
for i in range(1,N+1):
    g[i]=[]
  
for i in range(M):
    x,y=map(int,input().split())
    g[x].append(y)
    h[y]+=1
     
st=[]

for i in range(1,N+1):
    if h[i]==0: 
        st.append(i)
    
ans=[]
dp=[0]*(N+1)

while(len(st)):
    i=st[0]
    st.remove(st[0])
    
    ans.append(i)
    
    for j in g[i]:
        h[j]-=1
        if h[j]==0: 
            st.append(j)
            if dp[i]+1>dp[j]: 
                dp[j]=dp[i]+1
        

print(max(dp))

Solution (Python):
from collections import deque
 
N, M = map(int, input().split())
 
graph = [[] for i in range(N)]
to_this = [0] * N
for i in range(M):
  x, y = map(int, input().split())
  graph[x-1].append(y-1)
  to_this[y-1] += 1
 
 
depth = [0] * N
d = deque([i for i in range(N) if not to_this[i]])
while d:
  l = len(d)
  for i in range(l):
    node = d.popleft()
    children = graph[node]
    for child in children:
      to_this[child] -= 1
      if not to_this[child]:
        d.append(child)
      depth[child] = depth[node] + 1
 
print(max(depth))

Solution (Python):
import sys

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 = [-1] * (10 ** 5 + 1)


def dfs(v):
    if dp[v] != -1:
        return dp[v]

    res = 0
    for child in graph[v]:
        res = max(res, dfs(child) + 1)
    dp[v] = res
    return res


def solve():
    ans = 0
    for v in range(1, N + 1):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

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 = [-1] * (10 ** 5 + 1)


def dfs(v):
    if dp[v] != -1:
        return dp[v]

    res = 0
    for child in graph[v]:
        res = max(res, dfs(child) + 1)
    dp[v] = res
    return res


def solve():
    ans = 0
    for v in range(1, N + 1):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import collections

input = sys.stdin.readline

def chmax(a,b):
	if a>b : 
		return a
	return b

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()
	for nv in lst_edge[v]:
		deg[nv] -= 1
		if(deg[nv] == 0):
			que.append(nv)
			dp[nv] = chmax(dp[nv], dp[v]+1)
print(max(dp))

Solution (Python):
from collections import defaultdict, deque

def solve(N, M, edges):
  outbound = defaultdict(deque)
  in_degree = defaultdict(int)
  for s,t in edges:
    outbound[s].append(t)
    in_degree[t] += 1

  q = deque()
  for i in range(N + 1):
    if in_degree[i] == 0:
      q.append(i)

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

  while q:
    node = q.popleft()
    for child in outbound[node]:
      dp[child] = max(dp[child], dp[node] + 1)
      in_degree[child] -= 1
      if in_degree[child] == 0:
        q.append(child)

  print(max(dp))


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


N, M = iln()
edges = []
for i in range(M):
  edges.append(iln())
  
solve(N, M, edges)

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

Solution (Python):




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


dp = [0]*n




edge = [[] for _ in range(n)]


to = [0]*n



for i in range(m): 
    a,b = map(int,input().split())
    a,b = a-1,b-1
    
    edge[a].append(b)
    to[b] += 1






st = []
for i,j in enumerate(to):
    if j == 0:
        st.append(i)



while len(st):
    go = st.pop()
    for e in edge[go]: 
        to[e] -= 1 
        if to[e] == 0: 
            st.append(e)
        dp[e] = max(dp[e],dp[go]+1) 
        



print(max(dp))

Solution (Python):
from collections import deque

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

xy = []

dic = {}
pnum = [0] * N

for i in range(M):

    x,y = map(int,input().split())
    x -= 1
    y -= 1

    if x not in dic:
        dic[x] = []

    dic[x].append(y)
    pnum[y] += 1

q = deque([])
dp = [0] * N

for i in range(N):

    if pnum[i] == 0:
        q.append(i)




while len(q) > 0:

    now = q.popleft()

    if now not in dic:
        continue

    for i in dic[now]:

        if dp[i] < dp[now] + 1:
            dp[i] = dp[now] + 1

        pnum[i] -= 1
        if pnum[i] == 0:
            q.append(i)


print (max(dp))

Solution (Python):
import random
from collections import defaultdict
import sys
sys.setrecursionlimit(100000000)

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

AN = defaultdict(list)
for i in range(M):
    u, v = map(int, raw_input().split())
    AN[u].append(v)
longest_path_from_vertex_cache = {}

def get_longest_path(V):


    if V in longest_path_from_vertex_cache:
        return longest_path_from_vertex_cache[V]

    adjacent_vertices = AN[V]
    longest_path = 0
    for vertex in adjacent_vertices:
        current_path_len = 1 + get_longest_path(vertex)
        if longest_path < current_path_len:
            longest_path = current_path_len

    longest_path_from_vertex_cache[V] = longest_path
    return longest_path

print max(get_longest_path(vertex) for vertex in range(1, N+1))

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