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**7)
N, M = [int(i) for i in input().split()]
edges = {j : [] for j in range(N + 1)}
for j in range(M):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    edges[x].append(y)
for i in range(N):
    edges[N].append(i)

memo_ls = [None for i in range(N + 1)]


def dfs(last):
    if memo_ls[last] is not None:
        return memo_ls[last]
    if len(edges[last]) == 0:
        return 0
    cnt = max([dfs(_next) + 1 for _next in edges[last]])
    memo_ls[last] = cnt
    return cnt


print(dfs(N) - 1)

Solution (Python):
N,M = map(int,input().split())

path = [[] for _ in range(N)]
pin = [0]*N
for _ in range(M):
  ip,op = map(int,input().split())
  pin[op-1]+=1
  path[ip-1].append(op-1)

cur = []
for i in range(N):
  if pin[i]==0:
    cur.append(i)

ans = 0
while cur:
  ans += 1
  nxt = []
  for ip in cur:
    for op in path[ip]:
      pin[op] -= 1
      if pin[op]==0 and not(op in nxt):
        nxt.append(op)
  cur = [x for x in nxt]
print(ans-1)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = sys.stdin.readline

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

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

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

    
    ans = 0
    for v in range(N):
        ans = chmax(ans,rec(v))

    print(ans)

main()

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


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


dp = [0]*N
ans.reverse()
for i in range(N):
    if edge[ans[i]]:
        for v in edge[ans[i]]:
            dp[ans[i]] = max(dp[ans[i]], dp[v]+1)
            
print(max(dp))

Solution (Python):
import sys

N, M = [int(s) for s in input().split()]
sys.setrecursionlimit(10**5)
dp = [-1] * (N+1)
neighbors = [[] for _ in range(N+1)]

for _ in range(M):
    x, y = [int(s) for s in input().split()]
    neighbors[x].append(y)

def LP(v):
    if dp[v] != -1:
        return dp[v]
    else:
        res = 0
        lp = [-1]
        for nv in neighbors[v]:
            lp.append(LP(nv))
        res = max(res, max(lp) + 1)
        dp[v] = res
        return res

ans = 0
for v in range(1,N+1):
    ans = max(ans, LP(v))

print(ans)

Solution (Python):
def lp(node,memo,graph):
    if memo[node] != -1:
        return memo[node]
    cand = [0]
    if graph[node]:
        for neighbor in graph[node]:
            cand.append(lp(neighbor,memo,graph))
        maximam = max(cand)+1
    else:
        maximam = 0
    memo[node]=maximam
    return maximam

import sys
sys.setrecursionlimit(10**5)
N,M = map(int, input().split())
graph = {}
for i in range(N+1):
    graph[i] = []
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
ans = 0
memo = [-1]*(N+1)
for i in range(1,N+1):
    ans = max(ans, lp(i,memo,graph))
print(ans)

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


dp = [-1]*n 

def solve(i):
    if dp[i] != -1:
        return dp[i]
    if len(graph[i]) == 0:
        dp[i] = 0
        return 0
    max_length = 0
    for next_node in graph[i]:
        dp[next_node] = solve(next_node)
        max_length = max(max_length,dp[next_node])

    dp[i] = max_length + 1
    return dp[i]

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


print(ans)

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


dp = [-1]*n 

def solve(i):
    if dp[i] != -1:
        return dp[i]
    if len(graph[i]) == 0:
        dp[i] = 0
        return 0
    max_length = 0
    for next_node in graph[i]:
        dp[next_node] = solve(next_node)
        max_length = max(max_length,dp[next_node])

    dp[i] = max_length + 1
    return dp[i]

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


print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)


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

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

        return dp[v]

    res = 0
    for i in range(1,N+1):
        res = max(res, rec(i))
    print(res)



    return



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

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

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



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

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

for i in range(N):
  rec(i)
print(max(dp))

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

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


def dfs(n):
    global dp
    if dp[n] >= 0:
        return dp[n]

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


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


if __name__ == '__main__':
    main()

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

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


def dfs(n):
    global dp
    if dp[n] >= 0:
        return dp[n]

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


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


if __name__ == '__main__':
    main()

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

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


def dfs(n):
    global dp
    if dp[n] > 0:
        return dp[n]

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


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i)
    print(max(dp))


if __name__ == '__main__':
    main()

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

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


def dfs(n):
    global dp
    if dp[n] > 0:
        return dp[n]

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


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i)
    print(max(dp))


if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque
from collections import defaultdict
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))

T = defaultdict(list)
in_num = defaultdict(int)

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

q = deque()

for n in range(N):
    if in_num[n] == 0:
        q.append(n)


DP = [0] * N

while q:
    v = q.popleft()
    t = T[v]
    for y in t:
        in_num[y] -= 1
        if in_num[y] == 0:
            q.append(y)
            DP[y] = max(DP[y], DP[v]+1)


print(max(DP))

Solution (Python):
from sys import setrecursionlimit


def f(i, links, dp):
  if dp[i] != -1:
    return dp[i]
  if len(links[i]) == 0:
    dp[i] = 0
  else:
    dp[i] = max(f(j, links, dp) for j in links[i]) + 1
  return dp[i]


setrecursionlimit(1000000)

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

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

dp = [-1] * N
print(max(f(i, links, dp) for i in range(N)))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)

n,e = [int(i) for i in input().split()]
mat = [[] for i in range(n)]
for i in range(e):
    a,b = [int(i) for i in input().strip().split()]
    mat[a-1].append(b-1)

dp=[-1 for i in range(n)]

def cal(i):  
    if mat[i]==[]:
        return 0
    else:
        if dp[i]==-1:
            nei = mat[i]
            dp[i] = max([1+cal(j) for j in nei])
        return dp[i]


m=0
for i in range(n):
    if dp[i]==-1:
        m=max(m,cal(i))
print(m)

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


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

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

cnt_in = defaultdict(int)
outs = defaultdict(list)
for vs in G:
    for v in vs:
        cnt_in[v] += 1

res = []
q = deque([i for i in range(N) if cnt_in[i]==0])
dp = [0]*(N+1)


while len(q) > 0:
    v = q.popleft()
    res.append(v)
    for next_v in G[v]:
        cnt_in[next_v] -= 1
        if cnt_in[next_v] == 0:
            q.append(next_v)
            dp[next_v] = max(dp[next_v], dp[v] + 1)

print(max(dp))

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

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

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

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

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

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

Solution (Python):
def tpsort(n,lst):
    parent=[0]*(n+1)
    child=[[] for _ in range(n+1)]
    for p,c in lst:
        child[p].append(c)
        parent[c]+=1
    ans=[]
    que=[]
    for i in range(1,n+1):
        if parent[i]==0:
            que.append(i)
    while que:
        h=que.pop()
        ans.append(h)
        for u in child[h]:
            parent[u]-=1
            if parent[u]==0:
                que.append(u)
    return ans
N,m=map(int,input().split())
data=[list(map(int,input().split())) for i in range(m)]
t=[[] for i in range(N+1)]
for p,c in data:
    t[p].append(c)
s=tpsort(N,data)
dp=[0]*(N+1)
for v in s:
    for r in t[v]:
        dp[r]=max(dp[v]+1,dp[r])
print(max(dp))

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s):
    if dp[s] != -1:
        return dp[s]
    elif len(edge[s]) == 0:
        dp[s] = 0
        return 0
    else:
        res = 0
        for v in edge[s]: 
            res = max(res,dfs(v)+1)
        dp[s] = res
        return res
n,m = LI()
dp = [-1]*n
edge = [[] for _ in range(n)]
for _ in range(m):
    x,y = LI()
    x -= 1
    y -= 1
    edge[x].append(y)

for i in range(n):
    dfs(i)
print(max(dp))

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s):
    if dp[s] != -1:
        return dp[s]
    elif len(edge[s]) == 0:
        return 0
    else:
        res = 0
        for v in edge[s]: 
            res = max(res,dfs(v)+1)
        dp[s] = res
        return res
n,m = LI()
dp = [-1]*n
edge = [[] for _ in range(n)]
for _ in range(m):
    x,y = LI()
    x -= 1
    y -= 1
    edge[x].append(y)

for i in range(n):
    dfs(i)
print(max(dp))

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

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

Solution (Python):
import sys
sys.setrecursionlimit(100000 + 1)

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

maxDist = [0 for i in range(N+1)]
in_degree = [0 for i in range(N+1)]
adj_list = [[] for i in range(N+1)]

for i in range(M):
    x, y = map(int, input().split())
    adj_list[x].append(y)
    in_degree[y] += 1

for node in range(1, N+1):
    adj_list[0].append(node)
    in_degree[node] += 1


flattenedNodes = []
def dfs(node):
    for child in adj_list[node]:
        maxDist[child] = max(maxDist[child], 1 + maxDist[node])
        in_degree[child] -= 1
        if in_degree[child] == 0:
            dfs(child)
            
dfs(0)
print(max(maxDist) - 1)

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

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

dp = [0] * N
g = [[] for _ in range(N)]

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

def dfs(node):
    if dp[node] > 0:
        return dp[node]
    mx = 0
    for i in g[node]:
        a = dfs(i) + 1
        if mx < a:
            mx = a
    dp[node] = mx
    return mx

ans = 0
for i in range(N):
    if dp[i] == 0:
        ans = max(ans, dfs(i))

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)


def dfs(v):
    if d[v] != -1:
        return d[v]
    res = -1
    for u in e[v]:
        res = max(res, dfs(u))
    res += 1
    d[v] = res
    return res


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

d = [-1] * n
res = -1
for v in range(n):
    res = max(res, dfs(v))
print(res)

Solution (Python):
import sys
from collections import deque
n, m = map(int, input().split( ))
Edg = [[] for _ in range(n)]
rev_Edg = [[] for _ in range(n)]
deg = [len(rev_Edg[i]) for i in range(n)]


Root_check = [1]*n
Dist = [0]*n
for i in range(m):
    v1,v2 = map(int, sys.stdin.readline().split( ))
    v1-=1
    v2-=1
    Edg[v1].append(v2)
    rev_Edg[v2].append(v1)
    deg[v2] += 1
    Root_check[v2] = 0
    

Q =deque()
for i in range(n):
    if Root_check[i] == 1:
        Q.append(i)

while len(Q) > 0:
    v = Q.popleft()
    for w in Edg[v]:
        Dist[w] = max(Dist[w],Dist[v] +1)
        deg[w] -=1 
        if deg[w] == 0:
            Q.append(w)
            


print(max(Dist))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

input = sys.stdin.readline

inf = float('inf')


def rec(v):
    if used[v]:
        return dp[v]
    used[v] = True
    res = 0
    for u in es[v]:
        res = max(res, rec(u) + 1)
    dp[v] = res
    return res


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

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

used = [False] * n
dp = [inf] * n

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7




def main():
    N, M = LI()
    es = [[x for x in LI()] for _ in range(M)]

    from collections import defaultdict
    outs = defaultdict(list)  
    
    for from_v, to_v in es:
        outs[from_v].append(to_v)
        

    
    memo = [None for _ in range(N+1)]
    def max_len(v):
        if memo[v] is not None:
            return memo[v]

        if not outs[v]:
            memo[v] = 0
            return 0
        else:
            memo[v] = max([max_len(x)+1 for x in outs[v]])
            return memo[v]

    print(max([max_len(x) for x in range(1,N+1)]))


main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    
    N, M = LI()
    es = [[x for x in LI()] for _ in range(M)]
    all_v = list(range(1, N+1))

    
    
    
    
    

    from collections import defaultdict

    outs = defaultdict(list)  
    ins = defaultdict(int)    
    for from_v, to_v in es:
        outs[from_v].append(to_v)
        ins[to_v] += 1


    
    

    from collections import deque
    q = deque()
    for v in all_v:
        if ins[v] == 0:
            q.append((v, 0))  


    

    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append((v2, depth+1))
                depth_max = max(depth_max, depth+1)


    
    

    
    

    
    print(depth_max)


main()

Solution (Python):
from collections import deque

def main(n, edges):
    deg = [0] * (n + 1)
    adj = {}

    for j in range(1, n + 1):
        adj[j] = []

    for u, v in edges:
        adj[u].append(v)
        deg[v] += 1

    S = deque()

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

    for u in range(1, n + 1):
        if deg[u] == 0:
            S.append(u)
            dp[u] = 0

    L = []

    while S:
        v = S.popleft()
        L.append(v)
        for u in adj[v]:
            deg[u] -= 1
            if deg[u] == 0:
                S.append(u)
                dp[u] = max(dp[u], dp[v] + 1)

    return max(dp)

assert main(6, [ (2, 3), (4, 5), (5, 6) ]) == 2
assert main(4, [ (1, 2), (1, 3), (3, 2), (3, 4), (2, 4) ]) == 3

n, m = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))
ans = main(n, edges)
print(ans)

Solution (Python):
from collections import deque

N, M = map(int,input().split())
edges = [[int(e)-1 for e in input().split()] for _ in range(M)]
ad = [[] for _ in range(N)]
num = [0] * N
for x, y in edges:
    ad[x].append(y)
    num[y] += 1

S = deque()
L = []
dp = [-1] * N

for v in range(N):
    if num[v] == 0:
        S.append(v)
        dp[v] = 0

while S:
    v = S.popleft()
    L.append(v)
    for nv in ad[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)
        dp[nv] = max(dp[nv], dp[v] + 1)

ans = max(dp)
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N,M = map(int,input().split())
    dp = [-1]*N
    ad = [deque() for _ in range(N)]
    num = [0]*N
    for _ in range(M):
        x,y = map(int,input().split())
        x -= 1; y -= 1
        ad[x].append(y)
        num[y] += 1

    L = []
    S = deque()

    for v in range(N):
        if num[v] == 0:
            S.append(v)
            dp[v] = 0

    while S:
        v = S.popleft()
        L.append(v)
        for _ in range(len(ad[v])):
            nv = ad[v].popleft()
            num[nv] -= 1
            if num[nv] == 0:
                S.append(nv)
                dp[nv] = dp[v] + 1

    ans = max(dp)
    print(ans)

main()

Solution (Python):
import collections
import sys
def main():

    sys.setrecursionlimit(10 ** 6)

    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(M):
        x, y = map(int, input().split())
        graph[x].append(y)

    memo = dict()
    def helper(node):
        if node in memo:
            return memo[node]

        max_l = 0
        for nxt in graph[node]:
            max_l = max(max_l, helper(nxt) + 1)
        memo[node] = max_l
        return max_l

    max_l = 0
    for i in range(1, N+1):
        l = helper(i)
        max_l = max(max_l, l)
    return max_l

if __name__ == '__main__':
    print(main())

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

Solution (Python):
from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    n, m = map(int, input().split())
    e = [[]for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        e[a].append(b)

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

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


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    n, m = map(int, input().split())
    e = [[]for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        e[a].append(b)

    dp = [-1 for i in range(n)]
    vis = [False for i in range(n)]

    def f(i):
        if vis[i]:
            return dp[i]
        ret = 0
        for v in e[i]:
            ret = max(ret, f(v) + 1)
        vis[i] = True
        dp[i] = ret
        return dp[i]

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


if __name__ == '__main__':
    main()

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = ""; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def inp(): return int(sys.stdin.readline())
def st(): return input()
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]

def main():
    n, m = wi()
    xy = mip(m)
    direct = [[] for _ in range(n)]
    for x, y in xy:
        direct[x].append(y)
    flag = [0 for _ in range(n)]
    """f(x)=(xを始点とする最長経路)とすると
    f(x)=
    {0 (xが葉のとき)
    max{f(y)+1|xからyへの辺があるようなy (そうでないとき)}
    として再帰で計算できるよ。答えはmax{f(x)}だね。
    再帰の深さがO(N)くらいになる
    """
    dp = [0 for _ in range(n)]
    def f(x):
        if flag[x]:
            return dp[x]
        flag[x] = 1
        fans = 0
        for y in direct[x]:
            fans = max(fans, f(y) + 1)
        dp[x] = fans
        return dp[x]

    ans = []
    for i in range(n):
        ans.append(f(i))
    print(max(ans))
    
if __name__ == '__main__':
    main()

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

n, m = [int(i) for i in raw_input().split()]
parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)

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

for i in range(M):
    x,y = map(int,input().split())
    graph[x-1].append(y-1)
    
def rec(v):
    if dp[v] != -1:
        return dp[v]
    tmp = 0
    for x in graph[v]:
        r = rec(x)+1
        if tmp < r:
            tmp = r
    dp[v] = tmp
    return dp[v]

result = 0
for i in range(N):
    r = rec(i)
    result = r if r>result else result
print(result)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

def tpsort(es, ordered = False):
    n = len(es)
    indgr = [0] * n
    for e in es:
        for u in e:
            indgr[u] += 1
    if ordered:
        from heapq import heappop, heappush
        st = []
        for v in range(n):
            if indgr[v] == 0: heappush(st, v)
        ret = []
        while st:
            v = heappop(st)
            ret.append(v)
            for u in es[v]:
                indgr[u] -= 1
                if indgr[u] == 0: heappush(st, u)
    else:
        st = [v for v in range(n) if indgr[v] == 0]
        ret = []
        while st:
            v = st.pop()
            ret.append(v)
            for u in es[v]:
                indgr[u] -= 1
                if indgr[u] == 0: st.append(u)
    if len(ret) == n:
        return ret
    else:
        return False

N, M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    x, y = map(lambda x: int(x)-1, input().split())
    es[x].append(y)
tplst = tpsort(es)
dp = [0] * N
for v in tplst:
    for u in es[v]:
        dp[u] = max(dp[u], dp[v]+1)
print(max(dp))

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]

    for i in range(M):
        fr, to = map(int, input().split())
        fr -= 1
        to -= 1
        edge[fr].append(to)

    maxLeng = [-1] * N

    def search(now):
        if maxLeng[now] != -1:
            return maxLeng[now]

        ret = 0
        for to in edge[now]:
            ret = max(ret, search(to))

        maxLeng[now] = ret + 1
        return ret + 1

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

    print(ans - 1)

sol()

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

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

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

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

memo = ["empty" for _ in range(n)]

def dp(x):
    if memo[x] == "empty":
        res = 0
        for i in root[x]:
            res = max(res, dp(i)+1)
        memo[x] = res

    return memo[x]

for j in range(n):
    dp(j)

print(max(memo))

Solution (Python):
import sys

sys.setrecursionlimit(2147483647)

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

def solve(n, m):
    graph = dict()
    table = [None]*n

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

    

    
    def dp(i):
        
        if table[i]:
            return table[i]

        childs = graph.get(i)
        if not childs:
            table[i] = 0
        else:
            table[i] = max([dp(y) for y in childs]) + 1

        
        return table[i]

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

    return max(filter(lambda x: x, table))

print(solve(n, m))

"""
"""