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:
edges, vertices = map(int, input().split())
dp = [None for _ in range(100000)]

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

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


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



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

print(max(dp))

Submission status: Runtime Error

Solution code:
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges)]

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

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


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

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

print(max(dp))

Submission status: Runtime Error

Solution code:
#!python3

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

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

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


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


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


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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
memo = {}
def dfs(v):
  if v in memo:
    return memo[v]
  
  if v in adj.keys() and len(adj[v]) == 0:
    memo[v] = 0
    return memo[v]
  
  res = 0
  for u in adj[v]:
    res = max(res, 1+dfs(u))
  memo[v] = res
  return res


N, M = (int(x) for x in input().split())
adj = defaultdict(list)
for _ in range(M):
  v1, v2 = (int(x) for x in input().split())
  adj[v1].append(v2)

G = [x for x in range(1, N+1)]
longestPath = 0
for v in G:
  if v in memo:
    longestPath = max(longestPath, memo[v])
    continue
  longestPath = max(longestPath, dfs(v))

print(longestPath)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
memo = {}
def dfs(v):
  if v in memo:
    return memo[v]
  
  if len(adj[v]) == 0:
    memo[v] = 0
    return memo[v]
  
  res = 0
  for u in adj[v]:
    res = max(res, 1+dfs(u))
  memo[v] = res
  return res


N, M = (int(x) for x in input().split())
adj = defaultdict(list)
for _ in range(M):
  v1, v2 = (int(x) for x in input().split())
  adj[v1].append(v2)

G = [x for x in range(1, N+1)]
longestPath = 0
for v in G:
  if v in memo:
    longestPath = max(longestPath, memo[v])
    continue
  longestPath = max(longestPath, dfs(v))

print(longestPath)

Submission status: Runtime Error

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



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


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

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

print(max(dist))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[list() for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  A[a-1].append(b)
dp=[0]*n  
def dfs(v):
  if A[v-1]==[]:
    return 0
  else:
    t=0
    for j in A[v-1]:
      t=max(t,dfs(j))
    dp[v-1]=t+1
    return t+1
for i in range(1,n+1):
  dfs(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(s, graph, dp, visited):
  visited.add(s)
  if s not in graph:
      dp[s-1] = 0
  for v in graph[s]:
    dfs(v, graph, dp, visited)
    dp[s-1] = max(dp[s-1], 1+dp[v-1])

def main():
  graph = defaultdict(set)
  i = 0

  while True:
    line = input()
    if line:
      s = line.split(' ')
      if i == 0:
        n, m = int(s[0]), int(s[1])
      else:
        u, v = int(s[0]), int(s[1])
        graph[u].add(v)
    else:
      break
    i += 1

  dp = [float('-inf')]*n
  visited = set()
  for i in range(1, n+1):
    if i not in visited:
      dfs(i, graph, dp, visited)
  return max(dp)

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(s, graph, dp, visited):
  visited.add(s)
  if s not in graph:
      dp[s-1] = 0
  for v in graph[s]:
    dfs(v, graph, dp, visited)
    dp[s-1] = max(dp[s-1], 1+dp[v-1])

def main():
  graph = defaultdict(set)
  i = 0

  while True:
    line = input()
    if line:
      s = line.split(' ')
      if i == 0:
        n, m = int(s[0]), int(s[1])
      else:
        u, v = int(s[0]), int(s[1])
        graph[u].add(v)
    else:
      break
    i += 1

  dp = [float('-inf')]*n
  visited = set()
  for i in range(1, n+1):
    if i not in visited:
      dfs(i, graph, dp, visited)
  return max(dp)

if __name__ == '__main__':
  ans = main()
  print(ans, '\n')

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(s, graph, dp, visited):
  visited.add(s)
  if s not in graph:
      dp[s-1] = 0
  for v in graph[s]:
    dfs(v, graph, dp, visited)
    dp[s-1] = max(dp[s-1], 1+dp[v-1])

def main():
  graph = defaultdict(set)
  i = 0

  while True:
    line = input()
    if line:
      s = line.split(' ')
      if i == 0:
        n, m = int(s[0]), int(s[1])
      else:
        u, v = int(s[0]), int(s[1])
        graph[u].add(v)
    else:
      break
    i += 1

  dp = [float('-inf')]*n
  visited = set()
  for i in range(1, n+1):
    if i not in visited:
      dfs(i, graph, dp, visited)
  return max(dp)

if __name__ == '__main__':
  ans = main()
  print(ans)
  print('\n')

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(s, graph, dp, visited):
  visited.add(s)
  if s not in graph:
      dp[s-1] = 0
  for v in graph[s]:
    dfs(v, graph, dp, visited)
    dp[s-1] = max(dp[s-1], 1+dp[v-1])

def main():
  graph = defaultdict(set)
  i = 0

  while True:
    line = input()
    if line:
      s = line.split(' ')
      if i == 0:
        n, m = int(s[0]), int(s[1])
      else:
        u, v = int(s[0]), int(s[1])
        graph[u].add(v)
    else:
      break
    i += 1

  dp = [float('-inf')]*n
  visited = set()
  for i in range(1, n+1):
    if i not in visited:
      dfs(i, graph, dp, visited)
  return max(dp)

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

Submission status: Runtime Error

Solution code:
def dfs(s, graph, dp, visited):
  visited.add(s)
  for v in graph[s]:
    dfs(v, graph, dp, visited)
  if s not in graph:
    dp[s] = 1  
  else:
    for v in graph[s]:
      dp[s] = max(dp[s], 1+dp[v])


from collections import defaultdict
graph = defaultdict(set)
i = 0

while True:
  line = input()
  if line:
    s = line.split(' ')
    if i == 0:
      n, m = int(s[0]), int(s[1])
    else:
      u, v = int(s[0]), int(s[1])
      graph[u].add(v)
  else:
    break
  i += 1

dp = [float('-inf')]*n
visited = set()
for i in range(1, n+1):
  if i not in visited:
    dfs(i, graph, dp, visited)
    
return max(dp)

Submission status: Runtime Error

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

# 隣接リストを作成
adjacencyList = [[0] for i in range(N)]

# 距離の情報
dp = [0] * N

# 入次数　（いりじすう）
deg = [0] * N

for _ in range(M):
    v, nv = map(int, input().split())
    adjacencyList[v-1].append(nv-1)
    #　入次数に1を足す
    deg[nv-1] += 1
    
queue = []

# BFS探索
# 入次数がゼロの頂点から探索を始める
for v in range(N):
    if deg[v] == 0:
        queue.append(v)

while queue:
    # 現在の頂点をqueueからpop
    v = queue.pop(0)
    for nv in adjacencyList[cur]:
        # 探索済みの頂点の入次数を減らす
        deg[nv] -= 1
        
        # 完全に探索済みの頂点の入次数がゼロの時、経路の距離を出発点から計算
        if deg[nv] == 0:
            # 頂点をqueueに追加する
            queue.append(nv)
            dp[nv] = max(dp[v] + 1, dp[nv])
            
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)
#print(sys.getrecursionlimit())
n,m=map(int,input().split())
dp=[-1]*n
E=[ [] for i in range(n) ]

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

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100)
#print(sys.getrecursionlimit())
n,m=map(int,input().split())
dp=[-1]*n
E=[ [] for i in range(n) ]

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

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
MAX=100100
dp=[-1]*MAX
G=[[] for _ in range(MAX)]

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

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

    dp[v]=ret
    return ret

n,m=map(int,input().split())
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1

    G[a].append(b)

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

print(x)

Submission status: Runtime Error

Solution code:
MAX=100100
dp=[-1]*MAX
G=[[] for _ in range(MAX)]

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

n,m=map(int,input().split())
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    
    G[a].append(b)
    
for i in range(n):
    dfs(i)
    
print(max(dp))

Submission status: Runtime Error

Solution code:
MAX=100100
dp=[-1]*MAX
G=[[] for _ in range(MAX)]

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

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

    dp[v]=ret
    return ret

n,m=map(int,input().split())
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1

    G[a].append(b)

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

print(max(dp))

Submission status: Runtime Error

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

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

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

    dp[x-1].append(y-1)

result=1

taisho=[]
next_taisho=[]

for i in range(N):
    if len(dp[i])>=1:
        for j in dp[i]:
            taisho.append(j)


while True:
    for k in taisho:
        if len(dp[k])>=1:
            for j in dp[k]:
                next_taisho.append(j)
    
    if len(next_taisho)==0:
        break

    else:
        result+=1
        taisho=next_taisho.copy()
        next_taisho=[]

print(result)

Submission status: Runtime Error

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

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

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

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

    return dp[node]

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

Submission status: Runtime Error

Solution code:
(n,m),*xy = [list(map(int,r.split())) for r in open(0)]
g = [[] for _ in range(n)]
dp = [0 for _ in range(n)]

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

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

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

    return dp[node]

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

Submission status: Runtime Error

Solution code:
def dfs(graph,i,visited,distance):
    visited[i]=1
    x=0
    edges=graph.get(i,[])
    for j in edges:
        if(distance[j]!=-1):
            x = max(x,1+distance[j])
        else:
            x=max(x,1+dfs(graph,j,visited,distance))
    distance[i]=x
    return distance[i]



n,m = map(int,input().split())
graph = dict()
for i in range(m):
    u,v= map(int,input().split())
    if(graph.get(u-1,0)==0):
        graph[u-1]=[v-1]
    else:
        graph[u-1].append(v-1)
visited=[0]*n
distance=[-1]*n

for i in range(n):
    if(visited[i]==0):
        distance[i]=dfs(graph,i,visited,distance)
print(max(distance))

Submission status: Runtime Error

Solution code:
def dfs(graph,i,visited,distance):
    visited[i]=1
    x=0
    edges=graph.get(i,[])
    for j in edges:
        if(distance[j]!=-1):
            x = max(x,1+distance[j])
        else:
            x=max(x,1+dfs(graph,j,visited,distance))
    return x



n,m = map(int,input().split())
graph = dict()
for i in range(m):
    u,v= map(int,input().split())
    if(graph.get(u-1,0)==0):
        graph[u-1]=[v-1]
    else:
        graph[u-1].append(v-1)
visited=[0]*n
distance=[-1]*n

for i in range(n):
    if(visited[i]==0):
        distance[i]=dfs(graph,i,visited,distance)
print(max(distance))

Submission status: Runtime Error

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

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

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

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

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

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

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

Submission status: Runtime Error

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

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

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

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

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

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

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

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(" "))
    G[x-1].append(y-1)
dp = [-1] * N
def pathlen(G, dp, v):
    if dp[v] != -1:
        return dp[v]
 
    plen = 0
    for i in G[v]:
        plen = max(plen, pathlen(G, dp, i)+1)
    dp[v] = plen
    return plen
ans = 0
for i in range(N):
    ans = max(ans, pathlen(G, dp, i))
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
memo = [-1]*N
def dfs(dic, p, memo):
    if memo[p] != -1:
        return memo[p]
    m = 0
    for d in dic[p]:
        m = max(m, dfs(dic, d, memo)+1)
    memo[p] = m
    return m
dic = [[] for i in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1].append(y-1)
ans = 0
for i in range(N):
    k= dfs(dic, i, memo)
    ans = max(ans,k)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
def dfs(dic, p, memo):
    if memo[p] != -1:
        return memo[p]
    m = 0
    for d in dic[p]:
        m = max(m, dfs(dic, d, memo)+1)
    memo[p] = m
    return m
dic = [[] for i in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1].append(y-1)
    
inf = -1
memo = [inf]*N
ans = 0
for i in range(N):
    k= dfs(dic, i, memo)
    ans = max(ans,k)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
def dfs(p):
    if memo[p] != -1:
        return memo[p]
    m = 0
    for d in dic[p]:
        m = max(m, dfs(d)+1)
    memo[p] = m
    return m
dic = [[] for i in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1].append(y-1)
    
inf = -1
memo = [inf]*N
ans = 0
for i in range(N):
    k= dfs(i)
    memo[i] = k
    ans = max(ans,k)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
def make_graph(x, y, dic):
    if x in dic.keys():
        dic[x].append(y)
    else:
        dic[x] = [y]
def dfs(p):
    if memo[p] != -1:
        return memo[p]
    if p not in dic.keys():
        return 0
    m = 0
    for d in dic[p]:
        m = max(m, dfs(d)+1)
    return m
dic = {}
for m in range(M):
    x, y = map(int, input().split())
    make_graph(x-1, y-1, dic)
inf = -1
memo = [inf]*N
ans = 0
for i in range(N):
    k= dfs(i)
    memo[i] = k
    ans = max(ans,k)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
def make_graph(x, y, dic):
    if x in dic.keys():
        dic[x].append(y)
    else:
        dic[x] = [y]
def dfs(p):
    if memo[p] != -1:
        return memo[p]
    if p not in dic.keys():
        return 0
    m = 0
    for d in dic[p]:
        m = max(m, dfs(d)+1)
    return m

dic = {}
for m in range(M):
    x, y = map(int, input().split())
    make_graph(x-1, y-1, dic)

inf = -1
memo = [inf]*N
ans = 0
for i in range(N):
    k= dfs(i-1)
    memo[i-1] = k
    ans = max(ans,k)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy
N, M = map(int, input().split())
dic = numpy.zeros([N,N], dtype = int)
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1][y-1] = 1
mat = numpy.matrix(dic, int)
memo = numpy.zeros([N+1, N], dtype = int)
memo[0] = 1
z = numpy.zeros([N], int)
ans = 0
for n in range(N):
    memo[n+1] = numpy.dot(mat,(memo[n].reshape(-1,1))).reshape(N)
    if memo[n+1].any() == 0:
        if ans == 0:
            ans = n
            print(ans)

Submission status: Runtime Error

Solution code:
import numpy
N, M = map(int, input().split())
dic = numpy.zeros([N,N], dtype = int)
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1][y-1] = 1
mat = numpy.matrix(dic, int)
memo = numpy.zeros([N+1, N], dtype = int)
memo[0] = 1
z = numpy.zeros([N], int)
ans = 0
for n in range(N):
    memo[n+1] = numpy.dot(mat,(memo[n].reshape(-1,1))).reshape(N)
    if memo[n+1].any() == 0:
        if ans == 0:
          ans = n
          print(ans)

Submission status: Runtime Error

Solution code:
import numpy
N, M = map(int, input().split())
dic = numpy.zeros([N,N], dtype = int)
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1][y-1] = 1
mat = numpy.matrix(dic, int)
memo = numpy.zeros([N+1, N], dtype = int)
memo[0] = 1
z = numpy.zeros([N], int)
for n in range(N):
    memo[n+1] = (mat@(memo[n].reshape(-1,1))).reshape(4)
    if memo[n+1].any() == 0:
        print(ans)

Submission status: Runtime Error

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

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

    dp[v] = res
    return res



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

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

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


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

print(result)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[[]for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    l[x].append(y)

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())

grid=[]
for i in range(n):
  x=list(input())
  grid.append(x)
  

dp=[[0 for i in range(m)] for j in range(n)]
dp[0][0]=1
for i in range(n):
  for j in range(m):
    if grid[i][j]!='#':
      if i>0:
        dp[i][j]+=dp[i-1][j]
      if j>0:
        dp[i][j]+=dp[i][j-1]
        
print(dp[n-1][m-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys

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

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

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

Submission status: Runtime Error

Solution code:
import sys

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

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(25000)
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)

# iを始点としたときの有効パスの最大長さ
dp = [-1] * n
 
def rec(s):
    if dp[s] != -1:
        return dp[s]

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)

# iを始点としたときの有効パスの最大長さ
dp = [-1] * n

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

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

print(ml)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)

# iを始点としたときの有効パスの最大長さ
dp = [-1] * n

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

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

print(ml)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
    
n, m = map(int, input().split())
adj = defaultdict(list)
radj = defaultdict(list)

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

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

Submission status: Runtime Error

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

memo = [0]*(n+1)
seen = [False]*(n+1)
def dp(v):
    if seen[v]:
        return memo[v]
    ans = 0
    for nv in G[v]:
        ans = max(ans, dp(nv) + 1)

    seen[v] = True
    memo[v] = ans
    return ans

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

Submission status: Runtime Error

Solution code:
import numpy as np
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = np.ones((N),dtype=int) * -1

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

#solve DAG and topological sort by recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    return ret
for v in range(N):
    dp[v] = f(v)
print(np.max(dp))

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = np.ones((N),dtype=int) * -1

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

#solve DAG and topological sort by recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    return ret
for v in range(N):
    dp[v] = f(v)
print(np.max(dp))

Submission status: Runtime Error

Solution code:
def main():
    n, m = list(map(int, input().split()))
    out = [[] for _ in range(n)]
    for _ in range(m):
        x, y = list(map(int, input().split()))
        out[x - 1].append(y - 1)
    dp = [-1] * n
    def count(i):
        if dp[i] != -1:
            return dp[i]
        else:
            cnt = 0
            for o in out[i]:
                cnt = max(cnt, count(o) + 1)
            return cnt

    for i in range(n):
        dp[i] = count(i)
    print(max(dp))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

sys.setrecursionlimit(10**9)

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

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

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

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

Submission status: Runtime Error

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

sys.setrecursionlimit(10**9)

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys

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

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

dp = [-1] * (n+1)
for _ in range(m):
    v1 , v2 = map(int,input().split())
    g[v1].append(v2)
    
# finding longest path for vertice i
def dfs(i):
    if dp[i]!=-1:
        return dp[i]
    temp = 0
    for nv in g[i]:
        temp = max(temp, dfs(nv)+1)

    dp[i]=temp
    return temp
  
# finding overall longest path  
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())

sys.setrecursionlimit(10**9)
 
vertices = [[] for i in range(N+1)]
dp = [-1] * (N+1)
 
for _ in range(M):
    fro, to = map(int, input().split())
    vertices[fro].append(to)

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

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

Submission status: Runtime Error

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

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

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

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

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