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):
def main():
    n, adj = getInputs()
    sequence = getTopologicalSort(n, adj)

    distance = [-1] * n
    longest = -1

    for v in sequence:
        if len(adj[v]) == 0:
            distance[v] = 0
        else:
            for dest in adj[v]:
                distance[v] = max(distance[v], 1 + distance[dest])
                longest = max(longest, distance[v])

    print(longest)

def getTopologicalSort(n, adj):
    state = [0] * n
    toVisit = list(range(n))

    topologicalSort = []
    order = []

    while len(toVisit) > 0:
        curr = toVisit.pop()

        if state[curr] == 0:
            order.append(curr)
            state[curr] = 1

            foundNewDest = False
            for dest in adj[curr]:
                if state[dest] == 0:
                    toVisit.append(dest)
                    foundNewDest = True

            if not foundNewDest:
                while True:
                    v = order[-1]

                    allProcessed = True
                    for dest in adj[v]:
                        if state[dest] == 0:
                            allProcessed = False
                            break

                    if allProcessed:
                        state[v] = 2
                        topologicalSort.append(order.pop())

                    if len(order) == 0 or not allProcessed:
                        break

    return topologicalSort

def getInputs():
    n, m = map(lambda x: int(x), input().split())

    adj = []
    for i in range(n):
        adj.append([])

    for i in range(m):
        a, b = map(lambda x: int(x), input().split())
        adj[a - 1].append(b - 1)

    return n, adj

main()

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

dp = [0] * n
s = []
for i in range(n):
    if not enter[i]:
        s.append(i)

while(s!=[]):
    v = s.pop(0)
    for i in G[v]:
        enter[i] -= 1
        if not enter[i]:
            s.append(i)
            dp[i] = dp[v]+1

print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10000)
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 = [-1 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())

g = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
    x, y = map(int, input().split())
    g[x].append(y)
    deg[y] += 1

q = deque()

for i in range(1, n + 1):
    if deg[i] == 0:
        q.append(i)

dp = [0] * (n + 1)
while q:
    n = q.popleft()
    for zzz in g[n]:
        deg[zzz] -= 1
        if deg[zzz] == 0:
            q.append(zzz)
            dp[zzz] = dp[n] + 1

print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges)]

nodes = [[] for _ in range(edges)]

for i in range(vertices):
    start, end = map(int, input().split())
    nodes[end -1].append(start-1)

for i in range(edges):
    if not len(nodes[i]):
        dp[i] = 0
def find(arr):
    if not len(arr):
        return 0
    for x in arr:
        if dp[x] is None:
            dp[x] = find(nodes[x])
    return 1 + max(dp[x] for x in arr)

for i in range(edges):
    dp[i] = find(nodes[i])

print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges)]

nodes = [[] for _ in range(edges)]

for i in range(vertices):
    start, end = map(int, input().split())
    nodes[end -1].append(start-1)

def find(arr):
    if not len(arr):
        return 0
    for x in arr:
        if dp[x] is None:
            dp[x] = find(nodes[x])
    return 1 + max(dp[x] for x in arr)

for i in range(edges):
    dp[i] = find(nodes[i])

print(max(dp))

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))


N, M = LI()
XY = [LI() for _ in range(M)]

w = [None] * N
links = [[] for _ in range(N)]
visit = [False] * N


def create_links():
    for x, y in XY:
        links[x - 1].append(y - 1)


def dfs(u):
    visit[u] = True
    n = 0
    for v in links[u]:
        if not visit[v]:
            w[v] = dfs(v)
        n = max(n, w[v])
    return n + 1


def main():
    create_links()
    for i in range(N):
        if not visit[i]:
            w[i] = dfs(i)
    ans = max(w) - 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)

ds = {}
def sub(u):
    if u in ds:
        return ds[u]
    d = 0
    for v in ns[u]:
        d = max(d, sub(v)+1)
    ds[u] = d
    return d

for i in range(n):
    if i not in ds:
        sub(i)
print(max(ds.values()))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def dfs(start):
    q = [start]
    d0 = 0
    d1 = 0
    while q:
        u = q.pop()
        if u>=0:
            if seen[u]:
                continue
            seen[u] = d0
            d0 += 1
            q.append(~u)
            for v in ns[u]:
                if seen[v] is None:
                    q.append(v)
        else:
            if ns[~u]:
                done[~u] = max(done[v] for v in ns[~u]) + 1
            else:
                done[~u] = 0

n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)


seen = [None] * n

done = [None] * n
    
for i in range(n):
    if seen[i] is not None:
        continue
    dfs(i)
print(max(done))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    edges[x].append(y)


def dfs(v, parent):
    if visited[v]:
        return
    visited[v] = 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)
        if dist[v] >= dist[v2]+1:
            continue
        dist[v] = dist[v2]+1


dist = [0]*n
visited = [0]*n

for i in range(n):
    if visited[i]:
        continue
    dfs(i, -1)

print(max(dist))

Solution (Python):
from collections import deque
n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
deg = [0]*(n+1)
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    deg[v] += 1
q = deque()

for i in range(1, n+1):
    if deg[i] == 0:
        q.append(i)

dp = [0]*(n+1)
while q:
    n = q.popleft()
    for s in graph[n]:
        deg[s] -= 1
        if deg[s] == 0:
            q.append(s)
            dp[s] = dp[n]+1

print(max(dp))

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

from collections import deque
topo = [0]
deq = deque(topo)

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

dp = [-1] * (N+1)
for v in topo:
    for t in G[v]:
        dp[t] = max(dp[t], dp[v] + 1)

print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
graph={}
n,m=map(int,input().split())
for i in range(1,n+1):
    graph[i]=[]
for _ in range(m):
    u,v=map(int,input().split())
    graph[u].append(v)

def dfs(i,dp):
    temp=0
    if dp[i]!=-1:
        return dp[i]
    for nvr in graph[i]:
        temp=max(temp,dfs(nvr,dp)+1)
    dp[i]=temp
    return temp 

dp=[-1]*(n+1)
res=0
for i in range(1,n+1):
    res=max(res,dfs(i,dp))
print(res)

Solution (Python):
import sys


input = sys.stdin.readline

def main():
    N, M = map(int, input().split())

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

    
    dp = [0] * N

    
    deg = [0] * N

    for _ in range(M):
        v, nv = map(int, input().split())
        adjacencyList[v-1].append(nv-1)
        
        deg[nv-1] += 1

    queue = []

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

    while queue:
        
        v = queue.pop(0)
        for nv in adjacencyList[v]:
            
            deg[nv] -= 1

            
            if deg[nv] == 0:
                
                queue.append(nv)
                dp[nv] = max(dp[v] + 1, dp[nv])

    print(max(dp))
    
main()

Solution (Python):
import sys
import collections

input = sys.stdin.readline
def main():
    
    N, M = map(int, input().split())
    
    lst_edge = [[] for _ in range(N)]
    
    deg = [0] * N
    for _ in range(M):
        x, y = map(int, input().split())
        
        lst_edge[x-1].append(y-1)
        deg[y-1] += 1
    
    que = collections.deque()
    for v in range(N):
        if deg[v] == 0:
            que.append(v)
    
    dp = [0] * N
    
    
    while que:
        v = que.popleft()
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            
            deg[nv] -= 1
            if deg[nv] == 0:
                
                que.append(nv)
                
                dp[nv] = max(dp[nv], dp[v] + 1)
    print(max(dp))
main()

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


@lru_cache(maxsize=None)
def rec(node):
    if len(graph[node]) == 0:
        return 0
    ans = 0
    for after in graph[node]:
        ans = max(ans, rec(after) + 1)
    return ans


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

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

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

print(ans)

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

n,m=map(int,input().split())
dp=[-1]*n
E=[ [] for i in range(n) ]

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

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

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

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

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

  x=0
  for w in G[v]:
    r=dfs(w)+1
    x=max(x,r)

  dp[v]=x
  return x

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

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

  return ans


print(main())

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

N,M = map(int,readline().split())
G = [[] for i in range(N)]
indegree = [0 for i in range(N)]

for i in range(M):
  x,y = map(int,readline().split())
  G[x - 1].append(y - 1)
  indegree[y - 1] += 1
  
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)
    
cnt = -1
while stack:
  cnt += 1
  newstack = []
  while stack:
    v = stack.pop()
    for child in G[v]:
      indegree[child] -= 1
      if indegree[child] == 0:
        newstack.append(child)
  stack = newstack

print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  
  path[y-1].append(x-1)

memo = [-1]*n
def dfs(v):
  if memo[v] < 0:
    if len(path[v])==0:
      memo[v]=0
    else:
      memo[v]=max([dfs(p)+1 for p in path[v]])
  return memo[v]

res = 0
for i in range(n):
  tmp = dfs(i)
  if res < tmp:
    res = tmp
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  
  path[y-1].append(x-1)

memo = [-1]*n
def dfs(v):
  if memo[v] < 0:
    if len(path[v])==0:
      memo[v]=0
    else:
      memo[v]=max([dfs(p)+1 for p in path[v]])
  return memo[v]

res = 0
for i in range(n):
  tmp = dfs(i)
  if res < tmp:
    res = tmp
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
(n,m),*xy = [list(map(int,r.split())) for r in open(0)]
g = [[] for _ in range(n)]
dp = [0 for _ in range(n)]

for i in xy:
    x,y = i[0],i[1]
    x -= 1
    y -= 1
    g[y].append(x)

def rec(node):
    if dp[node] > 0:
        return dp[node]
    
    if not g[node]:
        dp[node] = 0
        return 0

    for child in g[node]:
        dp[node] = max(dp[node], rec(child) + 1)

    return dp[node]

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

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

def dfs(n,arr,visited):
    for i in graph[n]:
        if visited[i]==False:
            arr[n]=max(arr[n],dfs(i,arr,visited)+1)
            visited[i]=True
        else:
            arr[n]=max(arr[n],arr[i]+1)
    return arr[n]

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

graph=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    if a!=b:
        graph[a-1].append(b-1)

visited=[False for i in range(n)]

arr=[0 for i in range(n)]

for i in range(n):
    if visited[i]==False:
        dfs(i,arr,visited)
print(max(arr))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
n,m=map(int,input().split())
adjacent_list=[[] for i in range(n+1)]
for i in range(m):
  x,y=map(int,input().split())
  adjacent_list[x].append(y)



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

def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  res=0
  for j in adjacent_list[i]:
    res=max(res,dfs(j)+1)
  dp[i]=res
  return dp[i]
ans=0
for i in range(1,n+1):
  ans=max(ans,dfs(i))
  
print(ans)

Solution (Python):
import sys
 
sys.setrecursionlimit(100000)
 
N, M = map(int, input().split())
memo = [-1]*N
dic = [[] for i in range(N)]
def dfs(dic, memo, v):
    if memo[v] != -1:
        return memo[v]
    plen = 0
    for i in dic[v]:
        plen = max(plen, dfs(dic, memo, i)+1)
    memo[v] = plen
    return plen
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1].append(y-1)
    
ans = 0
for i in range(N):
    ans = max(ans, dfs(dic, memo, i))
print(ans)

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

Solution (Python):
import sys

sys.setrecursionlimit(100000)

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

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

dp = [-1] * N
def pathlen(G, dp, v):
    if dp[v] != -1:
        return dp[v]

    plen = 0
    for i in G[v]:
        plen = max(plen, pathlen(G, dp, i)+1)
    dp[v] = plen
    return plen

ans = 0
for i in range(N):
    ans = max(ans, pathlen(G, dp, i))
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(100000)

def rec(v):
    global dp, path
    if dp[v] != -1:
        return dp[v]

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

    dp[v] = res
    return res



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

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

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


result = 0
for i in range(N):
    result = max(result, rec(i))

print(result)

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

memo=[0]*(n+1)
def chain(v):
    if memo[v]!=0:
        return memo[v]
    else:
        for a in l[v]:
            memo[v]=max(chain(a)+1,memo[v])
        return memo[v]
res=0
for i in range(1,n+1):
    res=max(res,chain(i))
print(res)

Solution (Python):
n, m = map(int, input().split())
G = [[] for _ in range(n)]
deg = [0] * n 
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)
    deg[y] += 1

from collections import deque

q = deque([])
for i in range(n):
    if deg[i] == 0:
        q.append(i)
dp = [0] * n

while q:
    v = q.popleft()

    for nv in G[v]:
        
        deg[nv] -= 1
        if deg[nv] == 0:
            q.append(nv)
            dp[nv] = max(dp[nv], dp[v]+1)
    
print(max(dp))

Solution (Python):
import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

dp=[-1]*n  
  
def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp=0
  for nv in g[i]:
    temp=max(temp,dfs(nv)+1)
  dp[i]=temp  
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(500000)
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
 
def rec(s):
    if dp[s] != -1:
        return dp[s]

    ret = 0
    for ns in G[s]:
        ret = max(ret, rec(ns)+1)
    dp[s] = ret
    return ret

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

Solution (Python):
import sys

sys.setrecursionlimit(20000)

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

def rec_dp(x):
    global dp
    if dp[x] != -1:
        return dp[x]
    else:
        ans = 0
        for y in lst[x]:
            ans = max(ans, rec_dp(y) + 1)
        dp[x] = ans
        return dp[x]
      
dp = [-1] * n
ans = 0
for _ in range(n):
    ans = max(ans, rec_dp(_))
print(ans)

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

connected=[0]*n
for i in range(n):
    for e in es[i]:
        connected[e]+=1

from collections import deque
que=deque([])
for i in range(n):
    if connected[i]==0:
        que.append(i)
dp=[0]*n

while que:
    s=que.popleft()
    for e in es[s]:
        connected[e]-=1
        dp[e]=max(dp[e], dp[s]+1)
        if connected[e]==0:
            que.append(e)
print(max(dp))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)

def dfs(i):
    if distance[i] != -1:
        return distance[i]
    ans = 0
    for node in graph[i]:
        ans = max(ans, dfs(node) + 1)
    distance[i] = ans
    return ans

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

graph = [[] for i in range(n)]
distance = [-1 for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)

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

print(ans)

Solution (Python):
import sys
from collections import defaultdict
    
sys.setrecursionlimit(10**9)
    
n, m = map(int, input().split())
adj = defaultdict(list)
radj = defaultdict(list)

for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    
dp = [-1]*(n+1)

def dfs(e):
    if dp[e] != -1:
        return dp[e]
    
    temp = 0
    for i in adj[e]:
        temp = max(temp, 1+dfs(i))
        
    dp[e] = temp
    return temp
    
    
for i in range(1, n+1):
    dfs(i)
    
print(max(dp))

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

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)

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

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

Solution (Python):









import os
import sys
from collections import deque




def main():
    n,m = map(int,input().split())
    path = [[] for _ in range(n+1)]
    to_cnt = [0]*(n+1)
    longest_cnt = [0]*(n+1)
    for _ in range(m):
        x,y = map(int,input().split())
        path[x].append(y)
        to_cnt[y]+=1
    
    Q = deque()
    for i in range(1,n+1):
        if to_cnt[i]==0:
            Q.append(i)



    while(Q):
        u = Q.popleft()
        for v in path[u]:
            to_cnt[v]-=1
            if longest_cnt[u]+1>longest_cnt[v]:
                longest_cnt[v]=longest_cnt[u]+1
            if to_cnt[v]==0:
                Q.append(v)
    print(max(longest_cnt))



if __name__ == "__main__":
    main()

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

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

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

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


def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    dp[v] = ret
    return ret
for v in range(N):
    dp[v] = f(v)
print(max(dp))

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

sys.setrecursionlimit(10**9)

vertices = [[] for i in range(N+1)]
dp = [-1] * (N+1)

for _ in range(M):
    fro, to = map(int, input().split())
    vertices[fro].append(to)

def dfs(i):
    
    if dp[i] != -1:
        return dp[i]
    
    temp = 0
    for vertex in vertices[i]:
        temp = max(temp, dfs(vertex)+1)
        
    dp[i] = temp
    return temp

for i in range(1,N+1):
    dfs(i)
    
print(max(dp))

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

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

g = [[] for i in range(n+1)]

dp = [-1] * (n+1)
for _ in range(m):
    v1 , v2 = map(int,input().split())
    g[v1].append(v2)
    

def dfs(i):
    if dp[i]!=-1:
        return dp[i]
    temp = 0
    for nv in g[i]:
        temp = max(temp, dfs(nv)+1)

    dp[i]=temp
    return temp
  

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

Solution (Python):
N,M=map(int,input().split())
graph=[[]for _ in range(N)]
deg=[0]*N
for i in range(M):
    xx,yy=map(int,input().split())
    graph[xx-1].append(yy-1)
    deg[yy-1]+=1

que=[]
dp=[0]*N

for i in range(N):
    if deg[i]==0:
        que.append(i)
while len(que)>0:
    k=que.pop(0)
    for x in graph[k]:
        deg[x]-=1
        if deg[x]==0:
            que.append(x)
            dp[x]=max(dp[x],dp[k]+1)
print(max(dp))

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(100000)


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

    def rec(v):
        if dp[v] >= 0:
            return dp[v]
        ret = 0
        for nv in adj_nodes[v]:
            ret = max([ret, rec(nv) + 1])
        dp[v] = ret
        return ret

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


if __name__ == '__main__':
    main()

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

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n,m=reads()
link=[[]for i in range(n)]
for i in range(m):
  x,y=reads()
  link[x-1].append(y-1)

@lru_cache(None)
def dp(k):
  res=0
  for ele in link[k]:
    res=max(res,dp(ele)+1)
  return res
res=1
for i in range(n)  :
  res=max(res,dp(i))
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def dfs(a,adjl,visited,dp):
  for i in adjl[a]:
    if visited[i]==0:
      visited[i]=1
      dfs(i,adjl,visited,dp)
 
    dp[a]=max(dp[a],1+dp[i])
n,m=map(int,input().split())
li=[]
for i in range(m):
  li.append([int(k) for k in input().split()])
adjl=[[] for j in range(n+1)]
for k in range(len(li)):
  adjl[li[k][0]].append(li[k][1])
visited=[0]*(n+1)
dp=[0]*(n+1)
for a in range(1,n+1):
  if visited[a]==0:
    visited[a]=1
    dfs(a,adjl,visited,dp)
print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def f(x):
	global hashi
	if(x in hashi):
		return hashi[x]
	if(adj[x]==[]):
		return 0
	mino=0
	for i in adj[x]:
		mino=max(mino,f(i))
	hashi[x]=mino+1
	return mino+1
l=input().split()
n=int(l[0])
m=int(l[1])
adj=[[] for i in range(n+1)]
for i in range(m):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	adj[u].append(v)
maxa=0
hashi=dict()
for i in range(1,n+1):
	maxa=max(maxa,f(i))
print(maxa)

Solution (Python):
def addEdge(adj, u, v):
    adj[u].append(v)
def dfs(node,dp,vis,adj):
    vis[node] = True 
    for i in range(len(adj[node])):
        if not vis[adj[node][i]]: 
            dfs(adj[node][i], dp,vis,adj)
        dp[node] = max(dp[node], 1 + dp[adj[node][i]])
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())
adj = [[] for i in range(n + 1)] 
for i in range(m):
    u,v=map(int, input().split())
    addEdge(adj,u,v)
dp=[0]*(n+1)
vis=[False]*(n+1)
for i in range(1,n+1):
    if not vis[i]:
        dfs(i,dp,vis,adj)
ans=0
for i in range(1, n + 1):   
    ans = max(ans, dp[i])  
print(ans)

Solution (Python):
from collections import defaultdict, deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    out_degree = [0]*N
    max_path = [0]*N
    G = defaultdict(list)
    for _ in range(M):
        x, y = read_ints()
        x -= 1
        y -= 1
        out_degree[x] += 1
        G[y].append(x)
    Q = [i for i, degree in enumerate(out_degree) if degree == 0]
    while len(Q):
        node = Q.pop()
        while len(G[node]):
            parent = G[node].pop()
            out_degree[parent] -= 1
            max_path[parent] = max(max_path[parent], max_path[node]+1)
            if out_degree[parent] == 0:
                Q.append(parent)
    return max(max_path)


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

Solution (Python):
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] += 1
    d = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while d:
        i = d.popleft()
        for j in li[i]:
            deg[j] -= 1
            if deg[j] == 0:
                dp[j] = max(dp[j] ,dp[i] + 1)
                d.append(j)
    print(max(dp))
a()

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

N,M = map(int,input().split())
XY = [[] for i in range(N + 1)]

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

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

  
def recur(n):
  if path[n] != -1:
    return path[n]
  
  elif XY[n] == []:
    path[n] = 0
    return path[n]
        
  else:
    ret = 0
    for chi in XY[n]:
      ret = max(ret,recur(chi) + 1)
    
    path[n] = ret
    return path[n]
    
for i in range(N):
  recur(i)

print(max(path))

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

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


in_count = [0]*N
edge = [[] for _ in range(N)]
for u,v in xy:
    in_count[v-1] += 1
    edge[u-1].append(v-1)

S = []
L = [] 
index = [0]*N 
for i in range(N):
    if in_count[i]==0: S.append(i)
while S:
    v = S.pop()
    index[v] = len(L)
    L.append(v)
    for nv in edge[v]:
        in_count[nv] -= 1
        if in_count[nv]==0:
            S.append(nv)

dp = [0] * N
for i,v in enumerate(L):
    for nv in edge[v]:
        dp[index[nv]] = max(dp[index[nv]], dp[i]+1)

print(max(dp))

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

    
    deg = [0 for _ in range(n)]
    
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        deg[b - 1] += 1

    
    que = deque([])
    for i in range(n):
        if deg[i] == 0:
            que.append(i)

    
    dp = [0 for _ in range(n)]
    while que:
        v = que.popleft()
        for nv in edge[v]:
            
            deg[nv] -= 1
            if deg[nv] == 0:
                que.append(nv)
                dp[nv] = max(dp[nv], dp[v] + 1)

    print(max(dp))


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

    
    deg = [0 for _ in range(n)]
    
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        deg[b - 1] += 1

    que = deque([])
    for i in range(n):
        if deg[i] == 0:
            que.append(i)

    dp = [0 for _ in range(n)]
    while que:
        v = que.popleft()
        for nv in edge[v]:
            deg[nv] -= 1
            if deg[nv] == 0:
                que.append(nv)
                dp[nv] = max(dp[nv], dp[v] + 1)

    res = 0
    for j in range(n):
        res = max(res, dp[j])
    print(res)


if __name__ == '__main__':
    resolve()