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**5)
def dfs(now):
  if v[now]:return v[now]
  res=1
  for to in e[now]:
    res=max(res,dfs(to)+1)
  v[now]=res
  return res
n,m=map(int,input().split())
e=[[]for _ in range(n+1)]
for i in range(m):
  x,y=map(int,input().split())
  e[x]+=[y]
v=[0]*(n+1)
v[0]=1
ans=0
for i in range(n+1):
  ans=max(ans,dfs(i))
print(ans-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**5+10)
def memo(v):
    if dp[v]!=-1:return dp[v]
    ans = 0
    for next_v in g[v]:
        ans = max(ans,memo(next_v)+1)
    dp[v] = ans
    return ans

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

ans = 0
for v in range(1,n+1):
    ans = max(ans, memo(v))
    
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def f(x):
    if flg[x]:
        flg[x] = 0
        p = 0
        for y in glaph[x]:
            p = max(p,f(y)+1)
        dp[x] = p
    return dp[x]
n,m = map(int,input().split())
flg = [1]*(n+1)
dp = [0]*(n+1)
glaph = [[] for i in range(n+1)]
for _ in range(m):
    x,y = map(int,input().split())
    glaph[x].append(y)
ans = 0
for i in range(1,n+1):
    ans = max(ans,f(i))
print(ans)

Solution (Python):
temparr = input()
from heapq import heappush, heappop

import sys
x=150000
sys.setrecursionlimit(x)
temparr = temparr.split()
n = int(temparr[0])
edg = int(temparr[1])
dicts = {}
secdict = {}
firstdict = {}
for e in range(edg):
    temparr = input()
    temparr = temparr.split()
    edgearr = []
    for i in temparr:
        edgearr.append(int(i))
    first = int(edgearr[0])
    sec = int(edgearr[1])
    if first not in dicts:
        dicts[first] = []
    dicts[first].append(sec)
    if first not in firstdict:
        firstdict[first] = 1 
tail = []
ans = {}

for i in range(1, n + 1):
    if i not in firstdict:
        tail.append(i)
        ans[i] = 0
        
def dfs(node):
    global ans, dicts
    if node in ans:
        return ans[node]
    if node not in  dicts:
        return 0  
    best = 0 
    for neigh in dicts[node]:
        curnew = dfs(neigh) + 1
        if curnew > best:
            best = curnew
    ans[node] = best 
    return best
ans2 = 0 
for i in range(1, n + 1):
    ans2 = max(dfs(i), ans2)
print(ans2)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = sys.stdin.readline

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

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

dp = [-1] * N


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

    ans = 0
    lst_nv = lst_edge[v]
    for nv in lst_nv:
        ans = max(ans, rec(nv) + 1)
    dp[v] = ans 
    return dp[v]

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

print(ans_memo)

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

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

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

    dp = [-1] * n
    def dfs(node):
        if len(edges[node]) == 0:
            dp[node] = 0
        else:
            max_len = 0
            for new_node in edges[node]:
                if dp[new_node] == -1:
                    dfs(new_node)
                if max_len < dp[new_node]:
                    max_len = dp[new_node]
            dp[node] = max_len + 1

    for node in range(n):
        if dp[node] == -1:
            dfs(node)

    print(max(dp))

main()

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 7)



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

G = {i: [] for i in range(1, N + 1)}

for x, y in xy:
    G[x].append(y)

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

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

    t = 0

    for g in G[num]:
        t = max(t, dfs(g) + 1)

    dp[num] = t
    return t

ans = 0
for i in range(1, N + 1):
    ans = max(ans, dfs(i))

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfs(self, node):
        ans = 0
        for child in self.adj[node]:
            ans = max(ans, 1 + self.dfs(child))
        return ans

    def dfsWithMemo(self, node, memo, visited):
        if(visited[node]):
            return memo[node]
        visited[node] = True
        for child in self.adj[node]:
            memo[node] = max(
                memo[node], 1 + self.dfsWithMemo(child, memo, visited))
        return memo[node]

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    
    def findLongestPathNaive(self):
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfs(i))
        return ans

    
    def findLongestPathWithMemo(self):
        visited = [False] * self.n
        memo = [0] * self.n
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithMemo(i, memo, visited))
        return ans

    
    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    
    
    print(dag.findLongestPathWithDp())


main()

Solution (Python):

import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfs(self, node):
        ans = 0
        for child in self.adj[node]:
            ans = max(ans, 1 + self.dfs(child))
        return ans

    def dfsWithMemo(self, node, memo, visited):
        if(visited[node]):
            return memo[node]
        visited[node] = True
        for child in self.adj[node]:
            memo[node] = max(
                memo[node], 1 + self.dfsWithMemo(child, memo, visited))
        return memo[node]

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    
    def findLongestPathNaive(self):
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfs(i))
        return ans

    
    def findLongestPathWithMemo(self):
        visited = [False] * self.n
        memo = [0] * self.n
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithMemo(i, memo, visited))
        return ans

    
    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    
    print(dag.findLongestPathWithMemo())
    


main()

Solution (Python):

import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    print(dag.findLongestPathWithDp())


main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
n,m=map(int,input().split())
d=defaultdict(list)
for _ in range(m):
  x,y=map(int,input().split())
  d[x-1].append(y-1)

dp=[-1]*n

def rec(v):
  if dp[v]!=-1:
    return dp[v]
  res=0
  for nv in d[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):
def getval():
    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)
    return n,m,g

def main(n,m,g):
    d = [-1 for i in range(n)]
    visited = [False for i in range(n)]
    temp = [[] for i in range(n)]
    
    for i in range(n):
        
        if d[i] != -1:
            continue
        q = [[i,-1]]
        prev = [-1]
        while q:
            idx = q.pop(-1)
            cur = idx[0]
            
            if not visited[cur]:
                visited[cur] = True
                
                if g[cur]:
                    prev.append(cur)
                    
                    for j in g[cur]:
                        q.append([j,cur])
                    continue
                
                else:
                    d[cur] = 0
                    temp[idx[1]].append(0)
            
            else:
                
                if d[cur] == -1:
                    d[cur] =  1 + max(temp[cur])
                if idx[1] != -1:
                    temp[idx[1]].append(d[cur])
            
            if prev[-1] == -1:
                break
            
            if q:
                if q[-1][1]==idx[1]:
                    continue
            
            par = prev.pop(-1)
            q.append([par,prev[-1]])

    print(max(max(d),0))

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

Solution (Python):
def getval():
    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)
    return n,m,g

def main(n,m,g):
    d = [-1 for i in range(n)]
    visited = [False for i in range(n)]
    temp = [[] for i in range(n)]
    ans = 0
    
    
    for i in range(n):
        if d[i] != -1:
            continue
        q = [[i,-1]]
        prev = [-1]
        while q:
            idx = q.pop(-1)
            
            if not visited[idx[0]]:
                visited[idx[0]] = True
                if g[idx[0]]:
                    prev.append(idx[0])
                    for j in g[idx[0]]:
                        q.append([j,idx[0]])
                else:
                    d[idx[0]] = 0
                    temp[idx[1]].append(0)
                    if idx[1]==-1:
                        break
                    if prev[-1]!=-1 and q:
                        
                        if q[-1][1]==idx[1]:
                            continue
                    bef = prev.pop(-1)
                    q.append([bef,prev[-1]])
            else:
                if d[idx[0]] == -1:
                    d[idx[0]] = 1 + max(temp[idx[0]])
                    if idx[1]!=-1:
                        temp[idx[1]].append(d[idx[0]])
                else:
                    if idx[1]!=-1:
                        temp[idx[1]].append(d[idx[0]])
                if prev[-1]!=-1 and q:
                    
                    if q[-1][1]==idx[1]:
                        continue
                if idx[1]==-1:
                    break
                bef = prev.pop(-1)
                q.append([bef,prev[-1]])   
    print(max(max(d),0))
    
                

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

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

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



visited = [False]*n
memo = [0]*n
def dp(v):
    if visited[v]:
        return memo[v]
    ret = 0
    for child in edges[v]:
        ret = max(ret, dp(child)+1)
    visited[v] = True
    memo[v] = ret
    return ret


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

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

Solution (Python):
def li():
    return [int(x) for x in input().split()]

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

INF = 10 ** 60

G = defaultdict(list)

N, M = li()

for _ in range(M):
    x, y = li()
    G[x].append(y)

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

def dfs(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for cv in G[v]:
        ret = max(ret, dfs(cv) + 1)
    dp[v] = ret
    return ret


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

print(ans)

Solution (Python):
def li():
    return [int(x) for x in input().split()]

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

INF = 10 ** 60

G = defaultdict(list)

N, M = li()

for _ in range(M):
    x, y = li()
    G[x].append(y)

dp = [-1] * (10 ** 5 + 100)

def dfs(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for cv in G[v]:
        ret = max(ret, dfs(cv) + 1)
    dp[v] = ret
    return ret


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

print(ans)

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


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

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


dp = [0] * N
seen = [0] * N

def dfs(v):
    if seen[v]:
        return dp[v]
    seen[v] = 1
    res = 0
    for nv in to[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return res


def main():
    ans = 0
    for i in range(N):
        ans = max(ans, dfs(i))
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

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

Solution (Python):

import sys,os,io

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
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(start):
  stack = [start]
  while stack:
    v = stack[-1]
    marker = 0
    path_l[v] = 0
    for u in edge[v]:
      if path_l[u]==-1: 
        marker = 1
        stack.append(u)
      else: 
        
        path_l[v] = max(path_l[v], path_l[u]+1)
    if marker==0:
      stack.pop()
  return

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

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

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(start):
  stack = [start]
  while stack:
    v = stack[-1]
    marker = 0
    path_l[v] = 0
    for u in edge[v]:
      if path_l[u]==-1: 
        marker = 1
        stack.append(u)
      else: 
        
        path_l[v] = max(path_l[v], path_l[u]+1)
    if marker==0:
      stack.pop()
  return

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

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

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

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

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

def f(x):
    if dp[x] != -1:
        return dp[x]

    t = 0
    for v in V[x]:
        t = max(t, f(v)+1)

    dp[x] = t
    return dp[x]

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

print(t)

Solution (Python):
from collections import defaultdict, deque
n,m = map(int,input().split())
d = defaultdict(list)
deg = [0]*n  

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

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

dp = [0]*100100

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

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

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

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

dp = [-1]*n

def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in d[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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



N, M = inpl()
graph = [[] for i in range(N+1)]

for i in range(M):
    x, y = inpl()
    graph[x].append(y)

flag = [False] * (N + 1)
dp = [0] * (N + 1)


def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = True
    fans = 0
    for y in graph[x]:
        fans = max(fans, f(y) + 1)
    dp[x] = fans
    return dp[x]

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



N, M = inpl()
graph = [[] for i in range(N+1)]

for i in range(M):
    x, y = inpl()
    graph[x].append(y)

flag = [False] * (N + 1)
dp = [0] * (N + 1)


def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = True
    fans = 0
    for y in graph[x]:
        fans = max(fans, f(y) + 1)
    dp[x] = fans
    return dp[x]

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

Solution (Python):
from collections import deque

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Num = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    Num[y] += 1
Q = deque()
for i, n in enumerate(Num):
    if n == 0:
        Q.append(i)

DP = [0] * N
ans = 0
while Q:
    now = Q.pop()
    for nex in Edge[now]:
        DP[nex] = max(DP[nex], DP[now] + 1)
        Num[nex] -= 1
        if not Num[nex]:
            Q.append(nex)
print(max(DP))

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

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

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

def dfs(pos):
    if not edges[pos]:
        dp[pos] = 0
        return
    for n_pos in edges[pos]:
        if not used[n_pos]:
            dfs(n_pos)
        used[n_pos] = 1
        dp[pos] = max(dp[pos],dp[n_pos]+1)

    
for i in range(N):
    if used[i]:
        continue
    used[i] = True
    dfs(i)

print(max(dp))

Solution (Python):
n, m = map(int, input().strip().split())
graph = {i:[] for i in range(1, n+1)}

deg = [0 for i in range(n+1)]
for i in range(m):
    v1, v2 = map(int, input().strip().split())
    graph[v1].append(v2)
    deg[v2] += 1

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

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

while len(Q):
    curr = Q.pop()
    for i in graph[curr]:
        dp[i] = max(dp[i], dp[curr]+1)
        deg[i] -= 1
        if deg[i] == 0:
            Q.append(i)

print(max(dp))

Solution (Python):


from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

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

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



def saiki(num):
    if visited[num]==1:
        return dp[num]
    
    visited[num]=1
    value=0
    if linked[num]:
        for item in linked[num]:
            value=max(value,saiki(item)+1)
    dp[num]=value
    return value

dp=[0]*N
visited=[0]*N
ans=0
for i in range(N):
    ans=max(ans,saiki(i))

print(ans)

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

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

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

dp=[-1]*N

def longest_path(v): 
    if dp[v] != -1: 
        return dp[v]
    
    
    tmp_max = 0
    for u in G[v]:
        tmp_max = max(tmp_max,longest_path(u)+1)
    dp[v] = tmp_max 
    
    return dp[v]

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

print(ans)

Solution (Python):
from collections import deque

def read_pair():
    return map(int, input().strip().split())


N, M = read_pair()
adj = [[] for x in range(N)]
rev = [[] for y in range(N)]

outdegree = [0] * N
for i in range(M):
    x, y = read_pair()

    
    x -= 1
    y -= 1

    adj[x].append(y)
    rev[y].append(x)
    outdegree[x] += 1

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

for x in range(N):
    if outdegree[x] == 0:
        q.append(x)

while q:
    x = q.popleft()
    for y in adj[x]:
        maxpath[x] = max(maxpath[x], 1 + maxpath[y])
    for z in rev[x]:
        outdegree[z] -= 1
        if outdegree[z] == 0:
            q.append(z)

print(max(maxpath))

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


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        graph[x].append(y)
    dp = [-1 for _ in range(n)]
    

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

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split())
G = defaultdict(list)
V = defaultdict(int)

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

q = deque(v for v in range(N) if V[v] == 0)

dp = [0]*(N)
while q:
    From = q.popleft()
    for to in G[From]:
        dp[to] = max(dp[From]+1, dp[to])
        V[to] -= 1
        if V[to] == 0:
            q.append(to)
print(max(dp))

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

def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        edges[y - 1].append(x - 1)
    used = [False for _ in range(n)]
    dp = [0 for _ in range(n)]
    
    def dfs(pos):
        if not edges[pos]:
            dp[pos] = 0
            return
        for n_pos in edges[pos]:
            if not used[n_pos]:
                dfs(n_pos)
            used[n_pos] = True
            dp[pos] = max(dp[pos], dp[n_pos] + 1)
            
    
    for i in range(n):
        if used[i]:
            continue
        used[i] = True
        dfs(i)
        
    print(max(dp))

main()

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)
def f(i, e, dp):
    if dp[i] is not None:
        return dp[i]
    val = 0
    for nxt in e[i]:
        val = max(val, f(nxt, e, dp) + 1)
    dp[i] = val
    return dp[i]


def edu_dp_g_longest_path():
    n, m = map(int, input().split())
    e = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        e[x - 1].append(y - 1)
    dp = [None] * n
    result = 0
    for i in range(n):
        result = max(result, f(i, e, dp))
    print(result)

edu_dp_g_longest_path()

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

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

graph = [[] for _ in range(110000)]

for _ in range(M):
    x, y = map(int, input().split())

    graph[x].append(y)

dp_memo = [-1] * 110000

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

    ret = 0
    for item in graph[v]:
        ret = max(ret, dp(item) + 1)

    dp_memo[v] = ret
    return ret

ans = 0

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

print(ans)

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())
    edge[x-1].append(y-1)
dp = [-1]*N

def calc(x):
    if dp[x]!=-1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max([calc(i) for i in edge[x]])+1
    return dp[x]

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

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())
    edge[x-1].append(y-1)
dp = [-1]*N

def calc(x):
    if dp[x]!=-1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max([calc(i) for i in edge[x]])+1
    return dp[x]

ans = 0
for i in range(N):
    if dp[i] != -1: continue
    ans = max(ans, calc(i))
print(ans)

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

import sys
sys.setrecursionlimit(10**6)

def dfs(u):
    global grpah,vis,dp
    vis[u] = 1
    for i in graph[u]:
        if not vis[i]:
            dfs(i)
        dp[u] = max(dp[u],dp[i] + 1)

n,m = ip()
graph = [[] for i in range(n+1)]
for i in range(m):
    a,b = ip()
    graph[a].append(b)

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

print(max(dp))

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

import sys
sys.setrecursionlimit(10**6)

def dfs(u):
    global grpah,vis,dp
    vis[u] = 1
    for i in graph[u]:
        if not vis[i]:
            dfs(i)
        dp[u] = max(dp[u],dp[i] + 1)

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)

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

print(max(dp))

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

import sys
sys.setrecursionlimit(10**6)

def dfs(u):
    global grpah,vis,dp
    vis.add(u)
    for i in graph[u]:
        if i not in vis:
            dfs(i)
        dp[u] = max(dp[u],dp[i] + 1)

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
dp = [0]*(n+1)

vis = set()
for i in range(1,n+1):
    if i not in vis:
        dfs(i)

print(max(dp))

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())
    edge[x-1].append(y-1)
dp = [-1]*N

def calc(x):
    if dp[x]!=-1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max([calc(i) for i in edge[x]])+1
    return dp[x]

ans = 0
for i in range(N):
    if dp[i] != -1: continue
    ans = max(ans, calc(i))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N, M = list(map(int, input().split()))
P = [set() for _ in range(N)]
for i in range(M):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    P[x].add(y)

dp = [-1]*N


def lpth(n):
    if dp[n] > -1:
        return dp[n]
    l = P[n]
    
    if l:
        s = [lpth(k) for k in l]
        
        a = max(s)+1
    else:
        a = 0
    dp[n] = a
    return a


for i in range(N):
    dp[i] = lpth(i)
print(max(dp))

Solution (Python):
from collections import deque, defaultdict

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

def topological_sort(adj, indeg):
    """
    幅優先探索によるトポロジカルソート
    O(|V|+|E|)

    adj: 隣接リスト
    indeg: 各ノード入次数を管理するリスト

    ret: トポロジカルソートされたリスト
    """
    is_visited = [0]*(N+1)
    ret = []

    def bfs(s):
        """
        sからBFSする
        """
        queue = deque([s])
        is_visited[s] = 1
        while queue:
            u = queue.popleft()
            
            ret.append(u)

            for v in adj[u]: 
                indeg[v] -= 1 
                if (indeg[v] == 0) and (not is_visited[v]):
                    
                    queue.append(v)
                    is_visited[v] = 1
    
    for u in range(1, N+1):
        if (indeg[u]==0) and (not is_visited[u]):
            
            bfs(u) 
    
    return ret

L = topological_sort(G,indeg.copy())
dp = [0]*(N+1)
for i in range(N):
    node = L[i]
    for nx in G[node]:
        dp[nx] = max(dp[nx], dp[node]+1)
print(max(dp))