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:



Sample input:
4 5
1 2
1 3
3 2
2 4
3 4


Sample output:
3

Submission status: Runtime Error

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

paths = [[] for i in range(N)]
longest_paths = [-1 for i in range(N)]

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

def get_longest(node):
    if longest_paths[node] != -1:
        return longest_paths[node]
    if paths[node] == []:
        longest_paths[node] = 0
        return 0
    else:
        result = max([get_longest(nd) for nd in paths[node]]) + 1
        longest_paths[node] = result
        return result

print(max([get_longest(i) for i in range(N)]))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
x = [0] * M
y = [0] * M
G = [[] for _ in range(N + 1)]
for i in range(M):
    X, Y = map(int, input().split())
    x[i] = X
    y[i] = Y
    G[X] += [Y]

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


def f(n):
    if dp[n] != -1:
        return dp[n]
    res = 0
    for m in G[n]:
        res = max(res, f(m) + 1)
    dp[n] = res
    return res


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

Submission status: Runtime Error

Solution code:

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

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



def f(n):
    if dp[n] != -1:
        return dp[n]
    res = 0
    for m in G[n]:
        res = max(res, f(m) + 1)
    dp[n] = res
    return res


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

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit = 1000000

input  = stdin.readline

n,m = list(map(int,input().split()))
par = [[] for _ in range(n+1)]
dis = [0]*(n+1)
vis = dis[:]

def dfs(n):
	for i in par[n]:
		dis[i] = max(dis[i], dis[n]+1)
		dfs(i)

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

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

print(max(dis))

Submission status: Runtime Error

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

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

dp = [-1]*(N)

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

for i in range(N):
    dp[i] = f(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
n,m = [int(x) for x  in input().split()]


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

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

from functools import lru_cache

@lru_cache(None)
def dp(i):
    ans = 0
    for v in graph[i]:
        ans  = max(ans, 1 + dp(v))
    return ans
best = 0
for i in range(n):
    best = max(best, dp(i))
print(best)

Submission status: Runtime Error

Solution code:
n,m = [int(x) for x  in input().split()]


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

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

from functools import lru_cache

@lru_cache(None)
def dp(i):
    ans = 0
    for v in graph[i]:
        ans  = max(ans, 1 + dp(v))
    return ans
best = 0
for i in range(n):
    best = max(best, dp(i))
print(best)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import collections
def dp(node,cache,edge):
  if node in cache:
    return cache[node]
  lcl_max=0
  for child in edge[node]:
    cache[child]=dp(child,cache,edge)
    lcl_max=max(lcl_max,1+cache[child])
  return lcl_max
 
max_dis=0
cache,edge={},collections.defaultdict(list)
n,m=map(int,input().split())
for _ in range(m):
  a,b=map(int,input().split())
  edge[a].append(b)
for node in range(1,n+1):
  max_dis=max(max_dis,dp(node,cache,edge))

Submission status: Runtime Error

Solution code:
import collections
def dp(node,cache,edge):
  if node in cache:
    return cache[node]
  lcl_max=0
  for child in edge[node]:
    dp[child]=dp(child,cache,edge)
    lcl_max=max(lcl_max,1+dp[child])
  return lcl_max

max_dis=0
cache,edge={},collections.defaultdict(list)
n,m=map(int,input().split())
for _ in range(m):
  a,b=map(int,input().split())
  edge[a].append(b)
for node in range(1,n+1):
  max_dis=max(max_dis,dp(node,cache,edge))

Submission status: Runtime Error

Solution code:
import collections
import sys
from functools import lru_cache
sys.setrecursionlimit(20000)
n, m  = [int(i) for i in input().strip().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().strip().split(' ')]
    edges[s-1].append(d-1) 
# dp = [-1]*n
maxPath = 0 
@lru_cache(None)
def dfs(node): 
    # global dp
    ans = 0 
    for i in edges[node]:
        ans = max(ans,dfs(i)+1)
    # dp[node] = ans
    return ans
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Submission status: Runtime Error

Solution code:
import collections
import sys
from functools import lru_cache
sys.setrecursionlimit(20000)
n, m  = [int(i) for i in input().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().split(' ')] 
    edges[s-1].append(d-1) 
# dp = [-1]*n
maxPath = 0 
@lru_cache(None)
def dfs(node): 
    # global dp
    ans = 0 
    for i in edges[node]:
        ans = max(ans,dfs(i)+1)
    # dp[node] = ans
    return ans
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Submission status: Runtime Error

Solution code:
import collections
import sys
sys.setrecursionlimit(20000)
n, m  = [int(i) for i in input().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().split(' ')] 
    edges[s-1].append(d-1) 
dp = [-1]*n
maxPath = 0 
def dfs(node): 
    # global dp
    ans = 0 
    for i in edges[node]:
        if dp[i]>=0:
             ans = max(ans,dp[i]+1)
        else:
            ans = max(ans,dfs(i)+1)
    dp[node] = ans
    return ans
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Submission status: Runtime Error

Solution code:
import collections
import sys
sys.setrecursionlimit(20000)
n, m  = [int(i) for i in input().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().split(' ')] 
    edges[s-1].append(d-1) 
dp = [-1]*n
maxPath = 0 
def dfs(node): 
    global dp
    if dp[node]>=0:
        return dp[node] 
    ans = 0 
    for i in edges[node]: 
        ans = max(ans,dfs(i)+1)
    dp[node] = ans
    return ans
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Submission status: Runtime Error

Solution code:
import collections
import sys
sys.setrecursionlimit(10000)
n, m  = [int(i) for i in input().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().split(' ')] 
    edges[s-1].append(d-1) 
dp = [-1]*n
maxPath = 0 
def dfs(node): 
    global dp
    if dp[node]>=0:
        return dp[node] 
    ans = 0 
    for i in edges[node]: 
        ans = max(ans,dfs(i)+1)
    dp[node] = ans
    return ans
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Submission status: Runtime Error

Solution code:
import collections
n, m  = [int(i) for i in input().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().split(' ')] 
    edges[s-1].append(d-1) 
dp = [-1]*n
maxPath = 0 
def dfs(node): 
    global maxPath
    global dp
    if dp[node]>=0:
        return dp[node] 
    ans = 0 
    for i in edges[node]: 
        ans = max(ans,dfs(i)+1)
    dp[node] = ans
    # maxPath = max(maxPath, ans) 
    return ans
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Submission status: Runtime Error

Solution code:
import collections
n, m  = [int(i) for i in input().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().split(' ')] 
    edges[s-1].append(d-1) 
dp = [-1]*n
maxPath = 0 
def dfs(node): 
    global maxPath
    global dp
    if dp[node]>=0:
        return dp[node]+1  
    ans = 0 
    for i in edges[node]: 
        ans = max(ans,dfs(i))
    dp[node] = ans
    maxPath = max(maxPath, ans) 
    return ans+1 
for i in range(n):
    dfs(i)
print(maxPath)

Submission status: Runtime Error

Solution code:
import collections
n, m  = [int(i) for i in input().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().split(' ')] 
    edges[s-1].append(d-1) 
dp = [-1]*n

# global maxPath
maxPath = 0 
def dfs(node): 
    # nonlocal maxPath
    global maxPath
    if dp[node]>=0:
        return dp[node]+1  
    ans = 0 
    for i in edges[node]: 
        ans = max(ans,dfs(i))
    dp[node] = ans
    maxPath = max(maxPath, ans) 
    return ans+1 
for i in range(n):
    dfs(i)
print(maxPath)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
v,e=map(int,input().split())
m=defaultdict(list)

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

print(longestPath())

Submission status: Runtime Error

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

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

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

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

print(max(maxpath))

Submission status: Runtime Error

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

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

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

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

print(max(maxpath))

Submission status: Runtime Error

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 01/08/2020

from sys import stdin, stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, m = iia()
dp = [-1] * (n + 1)
d = {}
for i in range(m):
    a, b = iia()
    d.setdefault(a, []).append(b)

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

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

Submission status: Runtime Error

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 01/08/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, m = iia()
dp = [-1] * (n + 1)
d = {}
for i in range(m):
    a, b = iia()
    d.setdefault(a, []).append(b)

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

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

Submission status: Runtime Error

Solution code:


n,m = list(map(int,input().split()))
graph = [[] for i in range(n+1) ]
ind = {}
dist = {}
visited = [False for i in range(n+1) ]

for _ in range(m):
    x,y = list(map(int,input().split()))
    graph[x].append(y)
    ind[y] = ind.get(y,0) + 1


        
def dfs(node):
    if visited[node]:return
    visited[node] = True
    for nei in graph[node]:
        ind[nei] -= 1
        dist[nei] = max(dist.get(nei,0),dist.get(node,0)+1)
        if ind[nei]==0:
            dfs(nei)
            
for i in range(1,n+1):
    if visited[i]==False and ind.get(i,0)==0:
        dfs(i)
res = 0
if dist:
    res  = max(dist.values())
print(res)

Submission status: Runtime Error

Solution code:


n,m = list(map(int,input().split()))
graph = [[] for i in range(n+1) ]
ind = {}
dist = {}
visited = [False for i in range(n+1) ]

for _ in range(m):
    x,y = list(map(int,input().split()))
    graph[x].append(y)
    ind[y] = ind.get(y,0) + 1


        
def dfs(node):
    if visited[node]:return
    visited[node] = True
    for nei in graph[node]:
        ind[nei] -= 1
        dist[nei] = max(dist.get(nei,0),dist.get(node,0)+1)
        if ind[nei]==0:
            dfs(nei)
            
for i in range(1,n+1):
    if visited[i]==False and ind.get(i,0)==0:
        dfs(i)
        
res  = max(dist.values(),default=0)
print(res)

Submission status: Runtime Error

Solution code:


n,m = list(map(int,input().split()))
graph = [[] for i in range(n+1) ]
ind = {}
dist = {}
visited = [False for i in range(n+1) ]

for _ in range(m):
    x,y = list(map(int,input().split()))
    graph[x].append(y)
    ind[y] = ind.get(y,0) + 1


        
def dfs(node):
    if visited[node]:return
    visited[node] = True
    for nei in graph[node]:
        ind[nei] -= 1
        dist[nei] = max(dist.get(nei,0),dist.get(node,0)+1)
        if ind[nei]==0:
            dfs(nei)
            
for i in range(1,n+1):
    if visited[i]==False and ind.get(i,0)==0:
        dfs(i)
        
res  = max(dist.values())
print(res)

Submission status: Runtime Error

Solution code:


n,m = list(map(int,input().split()))
graph = [[] for i in range(n+1) ]
ind = {}
dist = {}
for _ in range(m):
    x,y = list(map(int,input().split()))
    graph[x].append(y)
    ind[y] = ind.get(y,0) + 1

indzero = []
for x in range(1,n+1):
    if ind.get(x,0)==0:
        indzero.append(x)
        
def dfs(node,h):
    for nei in graph[node]:
        if nei in dist and h+1 <= dist[nei]:
            continue
        dist[nei] = h+1
        dfs(nei,h+1)
        
for node in indzero:
    dfs(node,0)
res  = max(dist.values()) 
print(res)

Submission status: Runtime Error

Solution code:


n,m = list(map(int,input().split()))
graph = [[] for i in range(n+1) ]
ind = {}
dist = {}
for _ in range(m):
    x,y = list(map(int,input().split()))
    graph[x].append(y)
    ind[y] = ind.get(y,0) + 1

indzero = []
for x in range(1,n+1):
    if ind.get(x,0)==0:
        indzero.append(x)
        
def dfs(node,h):
    for nei in graph[node]:
        if nei in dist and h+1 < dist[nei]:
            continue
        dist[nei] = h+1
        dfs(nei,h+1)
        
for node in indzero:
    dfs(node,0)
res  = max(dist.values()) 
print(res)

Submission status: Runtime Error

Solution code:


n,m = list(map(int,input().split()))
graph = [[] for _ in range(n) ]
ind = {}
dist = {}
for _ in range(m):
    x,y = list(map(int,input().split()))
    graph[x-1].append(y-1)
    ind[y-1] = ind.get(y-1,0) + 1

indzero = []
for x in range(n):
    if ind.get(x,0)==0:
        indzero.append(x)
def dfs(node,h):
    for nei in graph[node]:
        if nei in dist and h+1 < dist[nei]:
            continue
        dist[nei] = h+1
        dfs(nei,h+1)
        
for node in indzero:
    dfs(node,0)
res  = max(dist.values())
print(res)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
adj = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    u-=1; v-=1
    adj[u].append(v)
    

dp = [0] * n
topo = []
vis = [False] * n
def topsort(v,topo):
    global vis
    vis[v] = True
    for u in adj[v]:
        if not vis[u]:
            topsort(u,topo)
    topo.append(v)

for i in range(n):
    if not vis[i]:
        topsort(i,topo)
topo = topo[::-1]

vis = [False] * n
def dfs(v,vis,dp,cur):
    vis[v] = True
    dp[v] = max(dp[v],cur)
    for u in adj[v]:
        if not vis[u]:
            dfs(u,vis,dp,cur + 1)

for i in topo:
    if not vis[i]:
        dfs(i,vis,dp,1)

print(max(dp))

Submission status: Runtime Error

Solution code:
#import
#import math
#import numpy as np
#= int(input())
#= input()
#= map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]
def dfs(num):
    if dp[num] != -1:
        return dp[num]

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

    dp[num] = res
    return res


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

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

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

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

print(res)

Submission status: Runtime Error

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

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

    dp[num] = res
    return res


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

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

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

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

print(res)

Submission status: Runtime Error

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

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

    dp[num] = res
    return res


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

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

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

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

print(res)

Submission status: Runtime Error

Solution code:
dp = [-1] * N
def dfs(num):
    if dp[num] != -1:
        return dp[num]

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

    dp[num] = res
    return res


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

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

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

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

print(res)

Submission status: Runtime Error

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

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

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

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

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

    dp[num] = res
    return res

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

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

print(res)

Submission status: Runtime Error

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

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

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

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

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

    dp[num] = res
    return res

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

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

print(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 14:22:54 2020

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

Submission status: Runtime Error

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

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

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
g =[[] for _ in range(n)]
for _ in range(m):
    x,y = map(int,input().split())
    x -=1
    y -=1
    g[x].append(y)
longest = [-1]*n
def dfs(i):
    if longest[i]==-1:
        l = -1
        for nx in g[i]:
            l = max(l,dfs(nx))
        if l ==-1:
            longest[i]=0
        else:
            longest[i] = 1+l
    return longest[i]
for i in range(n):
    if longest[i]==-1:
        dfs(i)
print(max(longest))

Submission status: Runtime Error

Solution code:
global N, M
global edgeList

global longestPathFrom

def dfs(x):
    if longestPathFrom[x] == -1:
        # get
        longest = -1
        for nextNode in edgeList[x]:
            longest = max(longest, dfs(nextNode))
        # set
        if longest == -1:
            longestPathFrom[x] = 0
        else:
            longestPathFrom[x] = longest + 1
    # -- longest path from x has been calculated
    return longestPathFrom[x]

# -- main
if __name__ == '__main__':
    # -- input
    N, M = map(int, input().split())
    edgeList = [[] for node in range(N)]

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

    # -- process
    longestPathFrom = [-1] * N

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

    # -- output
    print(max(longestPathFrom))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5 + 1)
import numpy as np
N, M = map(int, input().split())
path = np.zeros((N+1, N+1), dtype=np.int64)
 
def judge(bool_array):
  for index, bool_value in enumerate(bool_array[1:], 1):
    if bool_value > path[index, 0]:
      # print('index={}, bool_value={}'.format(index, bool_value))
      plus_value = bool_value - path[index, 0]
      np.where(path[index, 1:] > 0, path[index, 1:]+plus_value, 0)
      path[index, 0] = bool_value
      judge(path[index, :1])

for _ in range(M):
  x, y = map(int, input().split())
  # print('x={}, y={}'.format(x, y))
  path[x, y] = path[x, 0] + 1
  bool_array = np.zeros(N+1, dtype=np.int64)
  bool_array[y] = path[x, y]
  judge(bool_array)
  # print(path)
print(path[:, 0].max())

Submission status: Runtime Error

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

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

dp = [-1] * N

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

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

Submission status: Runtime Error

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

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

dp = [-1] * N

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

Submission status: Runtime Error

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

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

dp = [-1] * N

def judge(index):
  if dp[index] != -1:
    return dp[index]
  elif not nodes[index]:
    dp[index] = 0
    return 0
  else:
    dp[index] = max(1 + judge(i) for i in nodes[index])
    return dp[index]
    
for i in range(N):
  judge(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
path = np.zeros((N+1, N+1), dtype=np.int64)

def judge(bool_array):
  for index, bool_value in enumerate(bool_array[1:], 1):
    if bool_value > path[index, 0]:
      # print('index={}, bool_value={}'.format(index, bool_value))
      plus_value = bool_value - path[index, 0]
      np.where(path[index, 1:] > 0, path[index, 1:]+plus_value, 0)
      path[index, 0] = bool_value
      judge(path[index, :1])

for _ in range(M):
  x, y = map(int, input().split())
  # print('x={}, y={}'.format(x, y))
  path[x, y] = path[x, 0] + 1
  bool_array = np.zeros(N+1, dtype=np.int64)
  bool_array[y] = path[x, y]
  judge(bool_array)
  # print(path)
print(path[:, 0].max())

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from functools import lru_cache


g = None


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


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


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from functools import lru_cache


g = None


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


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


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from functools import lru_cache


g = None


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


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


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

dp = [-1] * N # dp[i] = 頂点iから進むことが出来る深さ
def search(v):
  if dp[v] != -1:
    return dp[v]
  max_depth = 0
  for child in G[v]:
    max_depth = max(max_depth, search(child) + 1)
    
  dp[v] = max(dp[v], max_depth)
  return dp[v]

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

print(max(dp))

Submission status: Runtime Error

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

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

dp = [-1] * N # dp[i] = 頂点iから進むことが出来る深さ
def search(v):
  if dp[v] != -1:
    return dp[v]
  max_depth = 0
  for child in G[v]:
    max_depth = max(max_depth, search(child) + 1)
    
  dp[v] = max(dp[v], max_depth)
  return dp[v]

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

print(max(dp))

Submission status: Runtime Error

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





print(LPP(), end="")

Submission status: Runtime Error

Solution code:

N,M = map(int,input().split())
dp = [[0] * N for i in range(N)]

for i in range(M):
    Start_Point,Stop_Point =  map(int,input().split())
    Max_Number = max([x[Start_Point - 1] for x in dp])
    dp[Start_Point - 1][Stop_Point - 1] = Max_Number + 1

print(max(map(lambda x:max(x),dp)))