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:
from collections import defaultdict


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

Submission status: Runtime Error

Solution code:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def solve():
	n, m = read()
	graph = [[] for i in range(n+1)]
	for _ in range(m):
		u, v = read()
		graph[u].append(v)
	visited = [0 for i in range(n+1)]
	def dfs(node):
		if visited[node]:
			return(visited[node])
		if not graph[node]:
			visited[node] = 0
			return(0)
		m = 0
		for i in graph[node]:
			m = max(m, dfs(i))
		visited[node] = 1 + m#ax(dfs(i) for i in graph[node])
		# print(node, visited[node])
		return(visited[node])

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




if __name__ == "__main__":
	solve()

Submission status: Runtime Error

Solution code:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def solve():
	n, m = read()
	graph = [[] for i in range(n+1)]
	for _ in range(m):
		u, v = read()
		graph[u].append(v)
	visited = [0 for i in range(n+1)]
	def dfs(node):
		if visited[node]:
			return(visited[node])
		if not graph[node]:
			visited[node] = 1
			return(1)
		visited[node] = 1 + max(dfs(i) for i in graph[node])
		return(visited[node])

	ans = 1
	for i in range(1, n+1):
		ans = max(ans, dfs(i))
	print(ans-1)




if __name__ == "__main__":
	solve()

Submission status: Runtime Error

Solution code:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def solve():
	n, m = read()
	graph = [[] for i in range(n+1)]
	for _ in range(m):
		u, v = read()
		graph[u].append(v)
	visited = [0 for i in range(n+1)]
	def dfs(node):
		if visited[node]:
			return(visited[node])
		if not graph[node]:
			visited[node] = 1
			return(1)
		# m = 0
		# for i in graph[node]:
		# 	m = max(m, dfs(i))
		visited[node] = 1 + max(dfs(i) for i in graph[node])
		# print(node, visited[node])
		return(visited[node])

	ans = 1
	for i in range(1, n+1):
		ans = max(ans, dfs(i))
	# print(visited)
	print(ans-1)




if __name__ == "__main__":
	solve()

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
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[0]].append(li[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))

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
from queue import Queue

inp = stdin.readline
out = stdout.write

n,m = map(int,inp().split())
adj = [[] for _ in range(n+1)]

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

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

def dfs(u):
    if dp[u] != -1: return dp[u]
    if adj[u] == []: return 1
    for i in adj[u]: dp[u] = max(dp[u],dfs(i)+1)
    return dp[u]

ans = 0

for u in range(1,n+1): 
    ans = max(ans,dfs(u))

out(str(ans-1))

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
inp = stdin.readline
out = stdout.write
n,m = map(int,inp().split())
g = [[] for _ in range(n+1)]
for i in range(m):
    u,v = map(int,inp().split())
    g[u].append(v)
dp = [1 for _ in range(n+1)]

def dfs(root):
    for v in g[root]:
        dp[v] = max(dp[v],dp[i]+1)
        dfs(v)

for i in range(1,n+1):
    dfs(i)
out(str(max(dp)))

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
inp = stdin.readline
out = stdout.write
n,m = map(int,inp().split())
g = [[] for _ in range(n+1)]
for i in range(m):
    u,v = map(int,inp().split())
    g[u].append(v)
dp = [0 for _ in range(n+1)]
seen = [False for _ in range(n+1)]
def dfs(root):
    seen[root] = True
    for v in g[root]:
        dp[v] = max(dp[root]+1,dp[v])
        dfs(v)
for i in range(1,n+1):
    if not seen[i]: dp[i] = 1
    dfs(i)
out(str(max(dp)-1))

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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]])
        
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)

Submission status: Runtime Error

Solution code:
import sys
import numpy as numpy
input = sys.stdin.readline

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as numpy
#input = sys.stdin.readline

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

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as numpy
input = sys.stdin.readline

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

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as numpy
input = sys.stdin.readline

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

path = [-1] * (N)

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as numpy
input = sys.stdin.readline

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

path = [-1] * N

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

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

print(max(path))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
#for _ in range(int(input())):
#	n=int(input())
#	n,m=map(int,input().split())
#	s=input().strip()

def dfs(i):
	if dp[i]!=-1:return dp[i]
	c=0
	for j in v[i]:c=max(c,dfs(j)+1)
	dp[i]=c
	return c

n,m=map(int,input().split())
v=[[] for i in range(n+1)]
for i in range(m):
	x,y=map(int,input().split())
	v[x].append(y)
dp = [-1]*(n+1) 
m=0
for i in range(1,n+1):
	m=max(m,dfs(i))
print(m)

Submission status: Runtime Error

Solution code:
def main():
    N,M = map(int, input().split())
    dp = [-1] * N
    G = [[] for i in range(N)]
    # G[x]:xから直接行ける町リスト
    for i in range(M):
        x,y = map(lambda x:x-1, map(int, input().split()))
        G[x].append(y)
        
    # メモ化再帰
    def memorec(x):
        if dp[x] != -1:
            return dp[x]
        res = 0
        # x->dest->...で更新していく
        for dest in G[x]:
            res = max(res, 1+memorec(dest))
        dp[x] = res
        return res

    # 町iを始点とした時の最長経路長dp[i]をメモ化再帰で
    for i in range(N):
        dp[i] = memorec(i)
    print(max(dp))

main()

Submission status: Runtime Error

Solution code:
def main():
    N,M = map(int, input().split())
    dp = [-1] * N
    G = [[]] * N
    for i in range(M):
        x,y = map(lambda x:x-1, map(int, input().split()))
        G[x].append(y)

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

    # 町iを始点とした時の最長経路長dp[i]をメモ化再帰で
    for i in range(N):
        dp[i] = memorec(i)
    print(max(dp))

main()

Submission status: Runtime Error

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

def f(x):#dpは
    if dp[x]!=-1:
        return dp[x]#すでに値が決まっていたらそれをかえす
    ans=0
    for e in d[x]:#すべての枝について
        ans=max(ans,1+f(e))
    dp[x]=ans
    return ans

n,m = list(map(int, input().split()))
d = {}
dp = [[-1] for i in range(n+1)]#初期値を全て-1に設定
    
for _ in range(m):
    a,b = list(map(int, input().split()))
    d[a].append(b)#有向グラフ
    
ans=0
for i in range(1,n+1):
    ans=max(ans,f(i))
print(ans)

Submission status: Runtime Error

Solution code:
from _collections import defaultdict
import sys


class Graph:

    def __init__(self, n):
        self.g = defaultdict(list)
        self.dp = [-1 for i in range(n + 1)]

    def add_edge(self, x, y):
        self.g[x].append(y)

    def longest_path_util(self, node):

        if self.dp[node] != -1:
            return self.dp[node]

        leaf = 1
        best_child = 0
        for neib in self.g[node]:
                leaf = 0
                best_child = max(best_child, self.longest_path_util(neib))

        if leaf != 0:

            self.dp[node] = 0

        else:
            self.dp[node] = best_child + 1

        return self.dp[node]

    def longest_path(self, n):

        ans = 0

        for i in range(1, n + 1):

            ans = max(ans, self.longest_path_util(i))

        return ans


n, k =  map(int, input().split())
graph = Graph(n)
for _ in range(k):
    x, y = list(map(int, sys.stdin.readline().split()))
    graph.add_edge(x, y)

print(graph.longest_path(n))

Submission status: Runtime Error

Solution code:
from _collections import defaultdict
import sys

class Graph:

    def __init__(self, n):
        self.g = defaultdict(list)
        self.dp = [-1 for i in range(n + 1)]


    def add_edge(self, x, y):
        self.g[x].append(y)

    def longest_path_util(self, node):

        # if node not in self.g:
        #     # print(node)
        #     return 0

        if self.dp[node] != -1:
            return self.dp[node]

        leaf = 1
        best_child = 0
        for neib in self.g[node]:
                leaf = 0
                best_child = max(best_child, self.longest_path_util(neib))

        if leaf != 0:

            self.dp[node] = 0

        else:
            self.dp[node] = best_child + 1

        return self.dp[node]


    def longest_path(self, n):

        ans = 0

        for i in range(1, n + 1):

            ans = max(ans, self.longest_path_util(i))


        return ans


n, k =  list(map(int, sys.stdin.readline().split()))
graph = Graph(n)
for _ in range(k):
    x, y = list(map(int, sys.stdin.readline().split()))
    graph.add_edge(x, y)

# print(graph.g)
print(graph.longest_path(n))

Submission status: Runtime Error

Solution code:
from _collections import defaultdict
import sys

class Graph:

    def __init__(self, n):
        self.g = defaultdict(list)
        self.dp = [-1 for i in range(n + 1)]


    def add_edge(self, x, y):
        self.g[x].append(y)

    def longest_path_util(self, node):

        # if node not in self.g:
        #     # print(node)
        #     return 0

        if self.dp[node] != -1:
            return self.dp[node]

        leaf = 1
        best_child = 0
        for neib in self.g[node]:
                leaf = 0
                best_child = max(best_child, self.longest_path_util(neib))

        if leaf != 0:

            self.dp[node] = 0

        else:
            self.dp[node] = best_child + 1

        return self.dp[node]


    def longest_path(self, n):

        for i in range(1, n + 1):

            if self.dp[i] == -1:
                self.longest_path_util(i)

        return max(self.dp)


n, k =  list(map(int, sys.stdin.readline().split()))
graph = Graph(n)
for _ in range(k):
    x, y = list(map(int, sys.stdin.readline().split()))
    graph.add_edge(x, y)

# print(graph.g)
print(graph.longest_path(n))

Submission status: Runtime Error

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

table = {}

def dfs(v, e):
    glabal table
    if (v, e) in table:
        return table[(v, e)]
    res = 0
    for next_v in e[v]:
        res = max(dfs(next_v, e) + 1, res)
    table[(v,e)] = res
    return res


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
    ans = -1
    for v in range(N):
        ans = max(ans, dfs(v, e))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(v, e, visited, dp):
    if v in visited:
        return []
    ret = []
    if not e[v]:
        dp[v] = 0
    for next_v in e[v]:
        ret += dfs(next_v, e, visited, dp)
    ret.append(v)
    visited.add(v)
    return ret


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    e_ = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        e_[v].append(u)
    topological_sorted = []
    visited = set()
    dp = [-1]*N
    for v in range(N):
        topological_sorted += dfs(v, e, visited, dp)
    for v in topological_sorted:
        for other_side in e_[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import collections

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]
#Topological sort Gは辞書として渡す
def tsort(N,G,dic):
    res = 0
    #Topological Sort
    if dic[N] != -1:
        return dic[N]
    for node in G[N]:
        res = max(res,tsort(node,G,dic)+1)
    dic[N] = res
    return dic[N]

[n,m] = getlsi()
dic_next = collections.defaultdict(list)
dp = [-1] * n
for i in range(m):
    [x,y] = getlsi()
    dic_next[x-1].append(y-1)
ans = 0
for i in range(n):
    ans = max(ans,tsort(i,dic_next,dp))
print(ans)

Submission status: Runtime Error

Solution code:
import collections

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]
#Topological sort Gは辞書として渡す Lは空のリスト
def tsort(N,G,dic):
    res = 0
    #Topological Sort
    if dic[N] != -1:
        return dic[N]
    for node in G[N]:
        res = max(res,tsort(node,G,dic)+1)
    dic[N] = res
    return dic[N]

[n,m] = getlsi()
dic_next = collections.defaultdict(list)
dp = [-1] * n
for i in range(m):
    [x,y] = getlsi()
    dic_next[x-1].append(y-1)
ans = 0
for i in range(n):
    ans = max(ans,tsort(i,dic_next,dp))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(u, dp, graph, visited):
    if dp[u] != -1:
        return dp[u]
    visited[u] = True
    max_length = 0
    for v in graph[u]:
        max_length = max(max_length, dfs(v, dp, graph, visited))
    dp[u] = 1 + max_length
    visited[u] = False
    return dp[u]

def solve():
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for i in range(M):
        src, dest = map(int, input().split())
        graph[src].append(dest)
    dp = [-1] * (N+1)
    visited = [False] * (N+1)
    for i in range(1, N+1):
        if i in graph and not visited[i]:
            dfs(i, dp, graph, visited)
    print(max(dp)-1)

solve()

Submission status: Runtime Error

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

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


def dp_LP(v):# 頂点nから始まる最長経路を返す.
  if MEMO[v] != -1:
    return MEMO[v]
  else:
    ans = 0
    for i in G[v]:
      ans = max(ans, dp_LP(i)+1)
    MEMO[v] = ans

    return ans



answer = 0
for n in range(1,N+1):
  answer = max(answer, dp_LP(n))
print(answer)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
Grapeee = {j+1:[] for j in range(N)}
memo = {j+1: 0 for j in range(N)} # 各頂点からの最長経路をメモ. -1で初期化.
doneee = {j+1: False for j in range(N)}
ans = 0

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

#print(memo)
#print(done)
def dp(v):# 頂点nから始まる最長経路を返す.
  if doneee[v]: 
    return memo[v]
  elif doneee[v] == False:
    answ = 0
    for to in Grapeee[v]:
      answ = max(answ, dp(to)+1)
    memo[v] = answ
    doneee[v] = True
    #print(memo)
    #print(done)
    return answ

for n in range(1,N+1):
  #print(dp(n))
  ans = max(ans, dp(n))
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
Grap = {j+1:[] for j in range(N)}
memo = {j+1: 0 for j in range(N)} # 各頂点からの最長経路をメモ. -1で初期化.
done = {j+1: False for j in range(N)}
ans = 0

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

#print(memo)
#print(done)
def dp(v):# 頂点nから始まる最長経路を返す.
  if done[v]: 
    return memo[v]
  elif done[v] == False:
    answ = 0
    for to in Grap[v]:
      answ = max(answ, dp(to)+1)
    memo[v] = answ
    done[v] = True
    #print(memo)
    #print(done)
    return answ

for n in range(1,N+1):
  #print(dp(n))
  ans = max(ans, dp(n))
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
Grap = {j+1:[] for j in range(N)}
memo = {j+1: 0 for j in range(N)} # 各頂点からの最長経路をメモ. -1で初期化.
done = {j+1: False for j in range(N)}
ans = 0

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


def dp(v):# 頂点nから始まる最長経路を返す.
  if done[v]: 
    return memo[v]
  elif done[v] == True:
    answ = 0
    for to in Grap[v]:
      answ = max(answ, dp(to)+1)
    memo[v] = answ
    done[v] = True
    return answ

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
Grap = {j+1:[] for j in range(N)}
memo = {j+1: -1 for j in range(N)} # 各頂点からの最長経路をメモ. -1で初期化.
ans = 0

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


def dp(v):# 頂点nから始まる最長経路を返す.
  if memo[v] != -1: 
    return memo[v]
  else:
    answ = 0
    for to in Grap[v]:
      answ = max(answ, dp(to)+1)
    memo[v] = answ
    return answ

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

Submission status: Runtime Error

Solution code:
def dp(v):# 頂点nから始まる最長経路を返す.
  if memo[v] != -1: return memo[v]
  answ = 0

  for to in Grap[v]:
    answ = max(answ, dp(to)+1)
  memo[v] = answ
  return answ


N, M = map(int, input().split())
Grap = {j+1:[] for j in range(N)}
memo = {j+1: -1 for j in range(N+5)} # 各頂点からの最長経路をメモ. -1で初期化.

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

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

Submission status: Runtime Error

Solution code:
def dp(v):# 頂点nから始まる最長経路を返す.
  if memo[v] != -1: return memo[v]
  to_list = Grap[v]
  answ = 0

  for to in to_list:
    answ = max(answ, dp(to)+1)
  memo[v] = answ
  return answ


N, M = map(int, input().split())
Grap = {j+1:[] for j in range(N)}
memo = {j+1: -1 for j in range(N)} # 各頂点からの最長経路をメモ. -1で初期化.

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

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

Submission status: Runtime Error

Solution code:
def dp(v):# 頂点nから始まる最長経路を返す.
  if memo[v] != -1: return memo[v]
  to_list = Graph[v]
  answ = 0

  for to in to_list:
    answ = max(answ, dp(to)+1)
  memo[v] = answ
  return answ


N, M = map(int, input().split())
Graph = {j+1:[] for j in range(N)}
memo = {j+1: -1 for j in range(N)} # 各頂点からの最長経路をメモ. -1で初期化.

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

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

Submission status: Runtime Error

Solution code:
def dp(v):# 頂点nから始まる最長経路を返す.
  if memo[v] != -1: return memo[v]
  to_list = Graph[v]
  answ = 0

  for i in to_list:
    answ = max(answ, dp(i)+1)
  memo[v] = answ
  return answ


N, M = map(int, input().split())
Graph = {j+1:[] for j in range(N)}
memo = [-1] * (N+1) # 各頂点からの最長経路をメモ. -1で初期化.

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

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

Submission status: Runtime Error

Solution code:
def dp(n):# 頂点nから始まる最長経路を返す.
  if memo[n] != -1: return memo[n]
  to_list = Graph[n]
  answ = 0

  for i in to_list:
    answ = max(answ, dp(i)+1)
  memo[n] = answ
  return answ


N, M = map(int, input().split())
Graph = {n+1:[] for n in range(N)}
memo = [-1] * (N+1) # 各頂点からの最長経路をメモ. -1で初期化.

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

ans = 0
for n in range(1,N+1):

  ans = max(ans, dp(n))
print(ans)

Submission status: Runtime Error

Solution code:
def rec(x):
    if dp[x] == -1:
        ans = 0
        for l in e[x]:
            ans = max(ans,1+rec(l))
        dp[x] = ans
        return ans
    else:
        return dp[x]

N, M = map(int, input().split())
e = {}
dp=[-1]
for i in range(1,N+1):
    e[i]=[]
    dp.append(-1)
for i in range(M):
    a, b = map(int, input().split())
    e[a].append(b)
ans = 0
for i in range(1,N+1):
    ans = max(ans,rec(i))
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    ans=0
    for e in d[x]:
        ans=max(ans,1+f(e))
    return ans

n,m = list(map(int, input().split()))
d={}
for i in range(1,n+1):
    d[i]=[]
for _ in range(m):
    a,b = list(map(int, input().split()))
    d[a].append(b)
ans=0
for i in range(1,n+1):
    ans=max(ans,f(i))
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(8000)

def main():
	n, m = rli()
	G = [[] for i in range(n+1)]
	for _ in range(m):
		u, v = rli()
		G[u].append(v)
	ans = 0
	memo = [-1 for _ in range(n+1)]

	def longest(v):
		if memo[v] > -1:
			return memo[v]
		pathlen = 0
		for nbhr in G[v]:
			pathlen = max(pathlen, 1 + longest(nbhr))
		memo[v] = pathlen
		return pathlen

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

	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(8000)

def main():
	n, m = rli()
	G = defaultdict(lambda: [])
	for _ in range(m):
		u, v = rli()
		G[u].append(v)
	ans = 0
	memo = defaultdict(lambda: 0)

	def longest(v):
		if v in memo:
			return memo[v]
		pathlen = 0
		for nbhr in G[v]:
			pathlen = max(pathlen, 1 + longest(nbhr))
		memo[v] = pathlen
		return pathlen

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

	print(ans)

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(4000)

def main():
	n, m = rli()
	G = defaultdict(lambda: [])
	for _ in range(m):
		u, v = rli()
		G[u].append(v)
	ans = 0
	memo = defaultdict(lambda: 0)

	def longest(v):
		if v in memo:
			return memo[v]
		pathlen = 0
		for nbhr in G[v]:
			pathlen = max(pathlen, 1 + longest(nbhr))
		memo[v] = pathlen
		return pathlen

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

	print(ans)

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n, m = rli()
	G = defaultdict(lambda: [])
	for _ in range(m):
		u, v = rli()
		G[u].append(v)
	ans = 0
	memo = defaultdict(lambda: 0)

	def longest(v):
		if v in memo:
			return memo[v]
		pathlen = 0
		for nbhr in G[v]:
			pathlen = max(pathlen, 1 + longest(nbhr))
		memo[v] = pathlen
		return pathlen

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

	print(ans)

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
adj=[]
dp=[0 for i in range(0,n+1)]
def dfs(i,p,adj,dp):
    # print(i)
    # print(i,p)
    if dp[i]!=0:
        return dp[i]
    for j in (adj[i]):
        if j==p:
            continue 
        else:
            dfs(j,i,adj,dp)
            dp[i]=max(dp[i],1+dp[j])
    return dp[i]
    
for i in range(n+1):
    adj.append([])
for _ in range(m):
    u,v=map(int,input().split())
    adj[u].append(v)

for i in range(1,n+1):
    if dp[i]==0:
        dfs(i,i,adj,dp)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
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
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def dfs(u):
    if(dp[u]!=-1):
        return dp[u]
    for i in d[u]:
        if(dp[i]!=-1):
            dp[u]=max(dp[u],dp[i]+1)
        else:
            dp[u]=max(dp[u],dfs(i)+1)
    return max(dp[u],0)
from collections import defaultdict as dd
n,m=map(int,input().split())
d=dd(list)
for i in range(m):
    u,v=map(int,input().split())
    d[u].append(v)
dp=dd(lambda: -1)
mx=0
for i in range(1,n+1):
    if(dp[i]==-1):
        dp[i]=dfs(i)
    mx=max(mx,dp[i])
print(mx)

Submission status: Runtime Error

Solution code:
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)


d = [0] * n

def dfs(v,edge):
    global depth
    depth = 0
    for next_v in edge[v]:
        if d[next_v] == 0:
            dfs(next_v,edge)
        else:
            depth = max(depth,d[next_v])
    depth += 1 
    d[v] = depth

for i in range(n):
    dfs(i,edge)
print(max(d)-1)

Submission status: Runtime Error

Solution code:
#G
N,M=map(int,input().split())
A=[[] for i in range(N+1)]
dp=[[] for j in range(N)]

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

flag=False
for i in range(2,N):
    for x in dp[i-1]:
        dp[i]=dp[i]+A[x]
            
        if dp[i]==[]:
            flag=True
            result=i
            break
    if flag:
        break

print(result)