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
sys.setrecursionlimit(10**9)

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

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

dp = [-1]*(N)

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

ans = 0
for i in range(N):
    ans = max(ans, f(i))

print(max(dp))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a-1]+=[b-1]



dp = [-1] * n

def f(x):
    if dp[x] != -1:
        return dp[x]
    ret = 0
    for y in G[x]:
        ret = max(f(y) + 1, ret)
    dp[x] = ret
    return ret

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

print(max(dp))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a-1]+=[b-1]



dp = [-1] * n

def f(x):
    if dp[x] != -1:
        return dp[x]
    ret = 0
    for y in G[x]:
        ret = max(f(y) + 1, ret)
    dp[x] = ret
    return ret

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

print(max(dp))

Solution (Python):
import sys

try:
    import solve
except:
    from distutils.core import setup
    from distutils.extension import Extension
    from Cython.Distutils import build_ext
    from Cython.Build import cythonize

    if len(sys.argv) < 2:
        sys.argv.append("build_ext")
    else:
        sys.argv[1] = "build_ext"
    sys.argv.append("--inplace")

    with open(__file__) as f:
        with open('solve.pyx', 'w') as fw:
            while c := f.readline():
                if c.strip() == '"""':
                    nc = f.readline()
                    if nc.strip() == "solve.pyx":
                        while cc := f.readline():
                            if cc.strip() == '"""':
                                break
                            fw.write(cc)
    setup(
        name="my_module",
        ext_modules=cythonize(
            Extension("solve",
                      sources=["solve.pyx"],
                      extra_compile_args=["-O3"],
                      language="c++",
                      ),
            compiler_directives={'language_level': "3"}
        ),
        cmdclass={'build_ext': build_ext},
    )
    exit(0)

solve.main()

"""
solve.pyx


 
import sys
 
from libcpp.vector cimport vector
 
DEF MAX_N = 100100
DEF MAX_M = 100100
cdef vector[long] *g
cdef long memo[MAX_N]
 
 
cdef long f(long x):
    cdef long ret
    if memo[x] == -1:
        ret = 0
        for y in g[x]:
            ret = max(ret, f(y) + 1)
        memo[x] = ret
    return memo[x]
 
 
def resolve(in_):
    cdef long i
    global g
    cdef vector[long] _g[MAX_M]
    g = _g
    for i in range(MAX_N):
        memo[i] = -1
 
    _n, _m = next(in_).split()
    cdef int n, m
    n = int(_n)
    m = int(_m)
    for line in in_:
        _x, _y = line.split()
        g[int(_x) - 1].push_back(int(_y) - 1)
 
    cdef long ret = 0
    for i in range(n):
        ret = max(f(i), ret)
    return ret
 
 
def main():
    ans = resolve(sys.stdin.buffer)
    print(ans)
"""

Solution (Python):
import collections
import sys
sys.setrecursionlimit(10**9)
cache,edge={},collections.defaultdict(list)
def dp(node):
  if node in cache:
    return cache[node]
  lcl_max=0
  for child in edge[node]:
    
    lcl_max=max(lcl_max,1+dp(child))
  cache[node]=lcl_max
  return lcl_max
 
max_dis=0

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

Solution (Python):
import collections
import sys
from functools import lru_cache
sys.setrecursionlimit(int(10**9))
n, m  = [int(i) for i in input().strip().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().strip().split(' ')]
    edges[s-1].append(d-1) 

maxPath = 0 
@lru_cache(None)
def dfs(node): 
    ans = 0 
    for i in edges[node]:
        ans = max(ans,dfs(i)+1)
    return ans

for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





def topological_sort(graph):
  N = len(graph)
  in_cnt = [0 for i in range(N)]
  for x in range(N):
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in range(N) if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in range(N) if in_cnt[i]]:
    return None
  return ret

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  
L = topological_sort(graph)

d = [0 for i in range(N)]
for x in L:
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
print(max(d))

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
v,e=map(int,input().split())
m=defaultdict(list)

for i in range(e):
    x,y=map(int,input().split())
    m[x].append(y)
dp=defaultdict(lambda:-1)
def longestPath():
    
    def findLongestPath(vtx):
        if(dp[vtx]!=-1):
            return dp[vtx]
        res=0
        for i in m[vtx]:
            res=max(res,1+findLongestPath(i))
        dp[vtx]=res
        return res
        
        
    
    ans=0
    for i in range(1,v+1):
        ans=max(ans,findLongestPath(i))
    
    return ans;

print(longestPath())

Solution (Python):
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]

MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])


G = defaultdict(list)
first = 1 

def addEdge(a,b):
    G[a].append(b)
	
def DFSutil(node,vis,size):
    vis[node] = True
    for child in G.get(node,[]):
        if vis[child] ==  False:
            DFSutil(child,vis,size)
        size[node] = max(size[node],1 + size[child])
    
def findsubtree(first,N):
    vis = [False] * (N+1)
    size = [0]* (N+1)
    for i in range(1,N+1):
        if vis[i] == False:
            DFSutil(i,vis,size)
    return max(size)
        
N,M = ilele()
G = defaultdict(list)
for i in range(M):
    u,v =ilele()
    addEdge(u,v)
print(findsubtree(first,N))

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)


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

for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1

    al[a].append(b)

@functools.lru_cache(None)
def depth(u):
    if len(al[u]) == 0:
        return 0
    else:
        max_d = 0
        for v in al[u]:
            max_d = max(max_d, depth(v) + 1)
        return max_d

ans = 0
for i in range(n):
    ans = max(ans, depth(i))
print(ans)

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

N,M = map(int,input().split())
G = {}
for node in range(1,N+1):
	G[node] = set()
for _ in range(M):
	x,y = map(int,input().split())
	G[x].add(y)

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

def maxpa(G,source,maxpath):
	if maxpath[source] != -1:
		return maxpath[source]
	else:	
		if len(G[source]) == 0:
			maxpath[source] = 0
			return maxpath[source]
		else:	
			for ngbr in G[source]:
				maxpath[source] = max(maxpath[source],1+maxpa(G,ngbr,maxpath))
			return maxpath[source]

for i in range(1,N+1):
	if maxpath[i]==-1:
		maxpa(G,i,maxpath)

print(max(maxpath))

Solution (Python):




from sys import stdin, stdout
import sys
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007
sys.setrecursionlimit(100000)
n, m = iia()
dp = [-1] * (n + 1)
d = {}
for i in range(m):
    a, b = iia()
    d.setdefault(a, []).append(b)

def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    t = 0
    for i in d.get(cur, []):
        t = max(1 + dfs(i), t)
    dp[cur] = t
    return dp[cur]

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

Solution (Python):


import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

dp=[-1]*n

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

ans=0
for i in range(n):
    ans=max(ans,memo(i))

print(ans)

Solution (Python):


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

dp = [-1] * n

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

    for i in co[v]:
        x = memo(i) + 1
        if x > dp[v]:
            parent[v] = i + 1
            dp[v] = x

    return max(dp[v], 0)

parent = [0] * n


ans = 0
for i in range(n):
    ans = max(ans, memo(i))

print(ans)

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

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

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

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

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

longest = [-1]*N
for i in range(N):
  if longest[i]==-1:
    longest[i] = dfs(i)
ans = max(longest)
print(ans)

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

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

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

longest = [-1]*N
for i in range(N):
  if longest[i]==-1:
    longest[i] = dfs(i)
ans = max(longest)
print(ans)

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








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

    res = 0
    for obj in G[num]:
        res = max(res, dfs(obj) + 1)

    dp[num] = res
    return res


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

dp = [-1] * N
G = {i:[] for i in range(N)}

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

res = 0
for i in range(N):
    res = max(res, dfs(i))

print(res)

Solution (Python):

"""
Created on Sun Jul 26 14:22:54 2020

@author: Maruthi Srinivas
"""
import sys
sys.setrecursionlimit(1000000)
def dfs(node,graph,dp):
    temp=0
    if dp[node]!=-1:
        return dp[node]
    for i in graph[node]:
        temp=max(temp,dfs(i,graph,dp)+1)
    dp[node]=temp
    return temp
            
v,e=map(int,input().split())
adj={x:[] for x in range(v+1)}
for i in range(e):
    x,y=map(int,input().split())
    adj[x].append(y)
m=-1
dp=[-1]*(v+1)
for i in range(1,v+1):
    x=dfs(i,adj,dp)
    m=max(m,x)
print(m)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    edge[x].append(y)
flag=[0]*n
dp=[0]*n
def dfs(s):
    if flag[s]:
        return dp[s]
    flag[s]=1
    dist=0
    for i in edge[s]:
        dist=max(dist,dfs(i)+1)
    dp[s]=dist
    return dp[s]
for i in range(n):
    dfs(i)
print(max(dp))

Solution (Python):
import sys
from collections import *
sys.setrecursionlimit(10**5)
def dfs(x):
    visited[x]=True
    for i in range(len(adj[x])):
        t=adj[x][i]
        distance[t]=max(distance[t],distance[x]+1)
        indegree[t]-=1
        if(indegree[t]==0):
            dfs(t)

MAX = 10**5+5
indegree=[0]*(MAX)
distance=[0]*(MAX)
visited = [False]*(MAX)
adj = defaultdict(list)
N,M=list(map(int,input().split()))
for i in range(M):
    a,b=list(map(int,input().split()))
    adj[a].append(b)
    indegree[b]+=1
ans=0
for i in range(1,N+1):
    if(visited[i]==False and indegree[i]==0):
        dfs(i)
for i in range(1,N+1):
    ans=max(ans,distance[i])

print(ans)

Solution (Python):
import sys


def resolve():
    sys.setrecursionlimit(10 ** 6)
    readline = sys.stdin.readline
    
    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 dp[v]

    N, M = map(int, readline().split())
    G = [[] for _ in [0] * N]
    for _ in [0] * M:
        x, y = map(int, readline().split())
        G[x - 1].append(y - 1)

    
    dp = [-1] * N
    res = 0
    for v in range(N):
        res = max(res, rec(v))
    print(res)


resolve()

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

def dfs(x):
  if x in memo:
    return memo[x]
  ret=0
  for y in g[x]:
    ret=max(ret,dfs(y)+1)
  memo[x]=ret
  return ret

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

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


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




def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        e[a - 1].append(b - 1)

    res = [-1 for _ in range(n)]

    def dfs(ti):
        tmp = 0
        for vi in e[ti]:
            if res[vi] != -1:
                tmp = max(tmp, res[vi] + 1)
            else:
                tmp = max(tmp, dfs(vi) + 1)
        res[ti] = tmp
        return tmp

    ans = 0
    for i in range(n):
        if res[i] == -1:
            ans = max(ans, dfs(i))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


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




def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        e[a - 1].append(b - 1)

    res = [-1 for _ in range(n)]

    def dfs(ti):
        tmp = 0
        for vi in e[ti]:
            if res[vi] != -1:
                tmp = max(tmp, res[vi] + 1)
            else:
                tmp = max(tmp, dfs(vi) + 1)
        res[ti] = tmp
        return tmp

    ans = 0
    for i in range(n):
        if res[i] == -1:
            ans = max(ans, dfs(i))

    print(ans)


if __name__ == '__main__':
    main()

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

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

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

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

answer = 0
for i in range(N):
  answer = max(answer, judge(i))
print(answer)

Solution (Python):
import sys

global N, M
global edgeList

global longestPathFrom

def dfs(x):
    if longestPathFrom[x] == -1:
        
        longest = -1
        for nextNode in edgeList[x]:
            longest = max(longest, dfs(nextNode))
        
        if longest == -1:
            longestPathFrom[x] = 0
        else:
            longestPathFrom[x] = longest + 1
    
    return longestPathFrom[x]


if __name__ == '__main__':
    
    sys.setrecursionlimit(1000001)

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

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

    
    longestPathFrom = [-1] * N

    for node in range(N):
        if longestPathFrom[node] == -1:
            dfs(node)

    
    print(max(longestPathFrom))

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

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

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

dp = [-1] * N

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

answer = 0  
for i in range(N):
  answer = max(answer, judge(i))
print(answer)

Solution (Python):
import sys
from functools import lru_cache
from collections import defaultdict


g = None


@lru_cache(100000)
def f(x):
    ret = 0
    for y in g[x]:
        ret = max(ret, f(y) + 1)
    return ret


def resolve(in_):
    global g
    n, m = map(int, next(in_).split())
    _g = defaultdict(list)
    for line in in_:
        x, y = map(int, line.split())
        _g[x - 1].append(y - 1)
    g = _g
    f.cache_clear()
    return max(f(i) for i in range(n))


def main():
    sys.setrecursionlimit(1000000)
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict


g = None
memo = None


def f(x):
    if memo[x] == -1:
        ret = 0
        for y in g[x]:
            ret = max(ret, f(y) + 1)
        memo[x] = ret
    return memo[x]


def resolve(in_):
    global g, memo
    n, m = map(int, next(in_).split())
    _g = defaultdict(list)
    for line in in_:
        x, y = map(int, line.split())
        _g[x - 1].append(y - 1)
    g = _g
    memo = [-1] * 100000
    return max(f(i) for i in range(n))


def main():
    sys.setrecursionlimit(1000000)
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
arrive=[0]*n
ready=[]
for i in range(m):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    arrive[y-1]+=1
for i in range(n):
    if arrive[i]==0:
        ready.append(i)

path_num=[0]*n
while ready:
    depart=ready.pop()
    for to in edge[depart]:
        path_num[to]=max(path_num[to],path_num[depart]+1)
        arrive[to]-=1
        if arrive[to]==0:
            ready.append(to)
print(max(path_num))

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

n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    for j in range(2):
        C[i][j] -= 1

D = [0] * n
M = [[] for i in range(n)]
for i in range(m):
    M[C[i][0]].append(C[i][1])

IN = [0] * n
for i in range(m):
    IN[C[i][1]] += 1

S = []
s = 0

for i in range(n):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        if IN[x] == 0:
            S.append(x)
    s += 1



for i in range(n):
    for j in range(len(M[S[i]])):
        D[M[S[i]][j]] = max(D[M[S[i]][j]], D[S[i]] + 1)
print(max(D))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 1)
N,M = map(int,input().split())

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

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

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

print(max(dp))

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

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

def rec(v,visited,order):
    visited[v] = 0
    for u in adj[v]:
        if visited[u] < 0:
            rec(u,visited,order)
    order.append(v)

def main():
    xy = []
    for _ in range(M):
        x, y = map(int, input().split())
        xy.append((x-1,y-1))
        adj[x-1].append(y-1)
    
    
    visited = [-1] * N
    order = []
    for i in range(N):
        if visited[i] < 0:
            rec(i,visited,order)

    
    dp = [0]*(N+1)
    for o in order:
        for u in adj[o]:
            dp[o] = max(dp[o],dp[u]+1)
    
    print(max(dp))

if __name__ == "__main__":
    main()

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

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

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

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

dp = [-1] * N

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

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

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

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

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

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


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**7)
def LPP():
    n, m = map(int, readline().split())
    edges = [[] for _ in range(n)]
    for _ in range(m):
        s, t = map(int, readline().split())
        s -= 1
        t -= 1
        edges[s].append(t)
    dp = [-1]*n
    def dfs(s):
        if dp[s] != -1:
            return dp[s]
        if len(edges[s]) == 0:
            dp[s] = 0
            return 0
        res = 0
        for t in edges[s]:
            res = max(res, dfs(t)+1)
        dp[s] = res
        return res
    for i in range(n):
        dfs(i)
    print(max(dp),end="")

LPP()

Solution (Python):
import sys
readline = sys.stdin.readline

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

G = [[] for i in range(N)]
indegree = [0] * N

for i in range(M):
  x,y = map(int,readline().split())
  G[x - 1].append(y - 1)
  indegree[y - 1] += 1
  
start = set()
for i in range(len(indegree)):
  if indegree[i] == 0:
    start.add(i)
    
cnt = 0
while start:
  nex = set()
  hasnext = False
  for s in start:
    for y in G[s]:
      indegree[y] -= 1
      if indegree[y] == 0:
        nex.add(y)
        hasnext = True
  if hasnext:
    cnt += 1
  start = nex

print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

G = []
dp = []

def rec(v):
    global dp
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for node in G[v]:
        ans = max(ans, rec(node) + 1)
    dp[v] = ans
    return dp[v]

def main():
    global G, dp
    n, m = list(map(int, input().strip().split()))
    G = [[] for _ in range(n)]
    dp = [-1] * n
    for i in range(m):
        p, q = list(map(int, input().strip().split()))
        p -= 1
        q -= 1
        G[p].append(q)
    ans = 0
    for i in range(n):
        r = rec(i)
        
        ans = max(ans, r)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
dp=[0]*n
indegree=[0]*n
edges=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  indegree[b-1]+=1
  edges[a-1].append(b-1)
  
starting=[]
for i in range(n):
  if(indegree[i]==0):
  	starting.append(i)
visited=set()


while starting:
  
  
  start=starting.pop()
  end=edges[start]
  for j in end:
    dp[j]=max(dp[j],dp[start]+1)
    indegree[j]-=1
    if(indegree[j]==0):
      starting.append(j)
print(max(dp))

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