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

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

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

def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp = 0
  for neighbour in g[i]:
    temp = max(temp, dfs(neighbour) + 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:
n , m = map(int,input().split())

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

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

def dfs(i):
  temp = 0
  for neighbour in g[i]:
    temp = max(temp, dfs(neighbour) + 1)
  return temp
  
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 = [[] for _ in range(n)]

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

dp = [-1] * n

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

    tmp = 0
    for j in g[i]:
        tmp = max(tmp, dfs(j) + 1)

    dp[i] = tmp
    return tmp

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

print(max(dp))

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)

dp = [-1] * n

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

    tmp = 1e9
    for j in g[i]:
        tmp = min(tmp, dfs(j) + 1)

    dp[i] = tmp
    return tmp

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

print(min(dp))

Submission status: Runtime Error

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

dp = [0] * N
def dfs(v, dist):
    for i in path[v]:
        dp[v] = max(dp[v], dfs(i, dist+1))
    return dist

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

Submission status: Runtime Error

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

# ノードからの最大移動回数をメモ
dp = [-1] * N

def dfs(v, dist):
  for nv in path[v]:
    dp[v] = max(dfs(nv, dist+1),dp[v])
  return dist

for i in range(N):
  if dp[i] < 0:
    dp[i] = dfs(i, 0)
  
print(max(dp))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
es = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append(b)

dp = [-1]*n

def rec(start):
    if dp[start] != -1:
        return dp[start]
    ans = 0
    for next_node in es[start]:
        ans = max(ans, rec(next_node)+1 )
    dp[start] = ans

    return dp[start]

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

print(ans)

Submission status: Runtime Error

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

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

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

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


def calc(x):
    if lst[x] != -1:
        return lst[x]
    tmp = 0
    for next_ in G[x]:
        tmp = max(tmp, calc(next_))
    
    lst[x] = tmp + 1
    return tmp + 1

for i in range(1, N + 1):
    if lst[i] == -1:
        calc(i)

print (max(lst) - 1)

Submission status: Runtime Error

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

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

    def longest(i, memo):
        if memo[i] >= 0:
            return memo[i]
        if len(net[i]) == 0:
            l = 0
        else:
            l = max(longest(j, memo) + 1 for j in net[i])
        memo[i] = l
        return l

    memo = [-1] * n
    l = max(longest(i, memo) for i in range(n))
    print(l)


main()

Submission status: Runtime Error

Solution code:
import collections
N,M = map(int,input().split())
A = [list(map(int, input().split())) for i in range(M)]
visit = set()
G = collections.defaultdict(set)
for idx,(f,to) in enumerate(A):
    G[f].add(to)

cache = {}
    
def dfs(start):
    if start in cache:
        return cache[start]
    ma = 0
    for i in G[start]:
        if i not in visit:
            visit.add(i)
            ma = max(ma,dfs(i))
            visit.remove(i)
    cache[start] = ma + 1 
    return ma + 1

ma = 0 
for f,to in A:
    visit.add(f)
    ma = max(ma,dfs(f))
    visit.remove(f)
print(ma - 1)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = [list(map(int, input().split())) for i in range(M)]
visit = set()
G = collections.defaultdict(set)
for idx,(f,to) in enumerate(A):
    G[f].add(to)

cache = {}
    
def dfs(start):
    if start in cache:
        return cache[start]
    ma = 0
    for i in G[start]:
        if i not in visit:
            visit.add(i)
            ma = max(ma,dfs(i))
            visit.remove(i)
    cache[start] = ma + 1 
    return ma + 1

ma = 0 
for f,to in A:
    visit.add(f)
    ma = max(ma,dfs(f))
    visit.remove(f)
print(ma - 1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

    dag = [[] for _ in range(n+1)]
    for _ in range(m):
        src, dst = map(int, input().split())
        dag[src].append(dst)
    for arr in dag:
        arr = sorted(arr)

    # Distance of longest path starting at node i
    dists = [0] * (n+1)

    def longest(v):
        if dists[v]:
            return dists[v]
        for to in dag[v]:
            dists[v] = max(dists[i], longest(to) + 1)
        return dists[v]

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    dag = [[] for _ in range(n+1)]
    for _ in range(m):
        src, dst = map(int, input().split())
        dag[src].append(dst)

    # Distance of longest path starting at node i
    dists = [0] * (n+1)

    def longest(v):
        if dists[v]:
            return dists[v]
        for to in dag[v]:
            dists[v] = max(dists[i], longest(to) + 1)
        return dists[v]

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

    print(max_len)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
 
sys.setrecursionlimit(150000)sys.setrecursionlimit(150000)

def gdp(n, dp, G):
    if dp[n]!=-1:
        return dp[n]
 
    if G[n]==[]:
        dp[n]=0
        return 0
 
    for i in G[n]:
        ll=gdp(i, dp, G)
        if dp[n]<ll+1:
            dp[n]=ll+1
 
    return dp[n]
 
def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    G=[[] for _ in range(N)]
    for i in range(M):
        G[x[i]-1].append(y[i]-1)
 
    dp=[-1]*N
 
    print(max(gdp(i, dp, G) for i in range(N)))
 
    return
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit()

def gdp(n, dp, G):
    if dp[n]!=-1:
        return dp[n]

    if G[n]==[]:
        dp[n]=0
        return 0

    for i in G[n]:
        ll=gdp(i, dp, G)
        if dp[n]<ll+1:
            dp[n]=ll+1

    return dp[n]

def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    G=[[] for _ in range(N)]
    for i in range(M):
        G[x[i]-1].append(y[i]-1)

    dp=[-1]*N

    print(max(gdp(i, dp, G) for i in range(N)))

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def gdp(n, dp, G):
    if dp[n]!=-1:
        return dp[n]

    if G[n]==[]:
        dp[n]=0
        return 0

    for i in G[n]:
        ll=gdp(i, dp, G)
        if dp[n]<ll+1:
            dp[n]=ll+1

    return dp[n]

def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    G=[[] for _ in range(N)]
    for i in range(M):
        G[x[i]-1].append(y[i]-1)

    dp=[-1]*N

    print(max(gdp(i, dp, G) for i in range(N)))

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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


def dfs(s):
    #print(s, dp)
    if dp[s] != -1:
        return dp[s]
    
    rep = 0
    for g in graph[s]:
        rep = max(rep, dfs(g)+1)
    dp[s] = rep
    return rep

#print(graph)
ans = 0
for i in range(n):
    #print('i:', i)
    ans = max(ans, dfs(i))

print(ans)

Submission status: Runtime Error

Solution code:
H, W = [int(item) for item in input().split()]
grid = [[item for item in input().strip()] for _ in range(H)]

# print(H, W) 
# print(grid)

dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
dp[0][1] = 1

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            pass
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]

print(dp[H][W]%(10**9+7))

Submission status: Runtime Error

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

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

edges_list = [[int(i) for i in input().split()] for _ in range(M)]

x_list = [item[0] for item in edges_list]
y_list = [item[1] for item in edges_list]

# print(set(x_list), set(y_list))
# print(set(x_list) ^ set(y_list))
start_node = (set(x_list) & (set(x_list) ^ set(y_list)))
# print(start_node)

dp = np.zeros((N+1, M+1), dtype='int32')

que = collections.deque()

for item in start_node:
    que.append(item)
    k = 0
    next_node = []

    while len(que):
        # print(que)
        # print(dp)
        q = que.popleft()
        next_node += [j[1] for j in edges_list if j[0] == q]
        
        if len(que) > 0:
            continue

        else:
            dp[item, k + 1] = dp[item, k] + 1
            k += 1
            for l in next_node:
                que.append(l)
            next_node = []

print(np.max(dp)-1)

Submission status: Runtime Error

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

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


dp = np.zeros((N+1, M+1), dtype='int32')
que = collections.deque()

for item in start_node:
    que.append(item)
    k = 0
    next_node = []

    while len(que):
        # print(que)
        # print(dp)
        q = que.popleft()
        next_node += [j[1] for j in edges_list if j[0] == q]
        
        if len(que) > 0:
            continue

        else:
            dp[item, k + 1] = dp[item, k] + 1
            k += 1
            for l in next_node:
                que.append(l)
            next_node = []

print(np.max(dp)-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import deque
# starting with start node and then looking for the kids
# and the solving the sub-problem with kids
def recursive_dfs(graph, start_node, map1):
  if start_node not in graph:
    map1[start_node] = 0
    return 0
  dist = 0
  for child in graph[start_node]:
    if child not in map1:
      dist = max(recursive_dfs(graph, child, map1), dist)
    else:
      dist = max(map1[child], dist)
  map1[start_node] = dist + 1
  #print(map1)
  return (dist + 1)

N,M = [int(i) for i in input().split()] # nodes, edges
graph = defaultdict(list)
for i in range(M):
  s,d = [i for i in input().split()]
  graph[s].append(d)
map1 = defaultdict(int)
ans = 0
for i in range(1, N+1):
  if i in map1:
    ans = max(ans, map1[str(i)])
  else:
    ans = max(recursive_dfs(graph, str(i), map1), ans)
print("%s" % ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import sys
sys.setrecursionlimit(10**5+100)

def main():
  n, m = map(int, input().strip().split())
  memo = [-1] * (n+1)
  graph = defaultdict(list)

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

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

    memo[v] = max([0] + [rec(t)+1 for t in graph[v]])
    return memo[v]

  print(max([rec(v) for v in range(1, n+1)]))

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import sys
sys.setrecursionlimit(10**5+1)

def main():
  n, m = map(int, input().strip().split())
  memo = [-1] * (n+1)
  graph = defaultdict(list)

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

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

    memo[v] = max([0] + [rec(t)+1 for t in graph[v]])
    return memo[v]

  print(max([rec(v) for v in range(1, n+1)]))

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict

def main():
  n, m = map(int, input().strip().split())
  memo = [-1] * (n+1)
  graph = defaultdict(list)

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

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

    memo[v] = max([0] + [rec(t)+1 for t in graph[v]])
    return memo[v]

  print(max([rec(v) for v in range(1, n+1)]))

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import numpy


def main():
  n, m = map(int, input().strip().split())
  memo = numpy.full(n+1, -1)
  graph = defaultdict(list)

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

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

    memo[v] = numpy.max([0] + [rec(t)+1 for t in graph[v]])
    return memo[v]

  print(numpy.max([rec(v) for v in range(1, n+1)]))

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
def main():
    from functools import lru_cache
    import sys
    readline = sys.stdin.readline

    @lru_cache(maxsize=None)
    def dfs(v, par=-1):
        """最長有向パスに含まれる頂点数"""
        ret = 0
        for u in g[v]:
            if u == par: continue
            ret = max(ret, dfs(u, v))
        return ret + 1

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

    g = tuple(set() for _ in range(n))
    for _ in range(m):
        x, y = (int(c) - 1 for c in input().split())
        g[x].add(y)

    ret = 0
    for i in range(n):
        ret = max(ret, dfs(i))
    print(ret - 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**10)

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(max([dp(i) for i in range(n)]))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(max([dp(i) for i in range(n)]))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(max([dp(i) for i in range(n)]))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(max([dp(i) for i in range(n)]))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(G)
print(max([dp(i) for i in range(n)]))

Submission status: Runtime Error

Solution code:
from collections import deque
n,m=map(int,input().split())
G=[ deque([]) for _ in range(n+1) ]
for _ in range(m):
  v,e=map(int,input().split())
  G[v].append(e)

DP=[-1]*(n+1)
def rec(v):
  res=0
  if G[v]:
    for w in G[v]:
      res=max(res,rec(w)+1)
  DP[v]=res
  return res

for i in range(n+1):
  rec(i)
print(max(DP))

Submission status: Runtime Error

Solution code:

def search(index: int, dp: list, graph: list) -> int:
    if dp[index] != -1:
        return dp[index]+1

    tmp = 0
    for d in graph[index]:
        tmp = max(tmp, search(d, dp, graph))

    dp[index] = tmp
    return tmp+1


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

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

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

ans = 0
for i in range(N):
    ans = max(ans, search(i, dp, graph))

print(ans-1)

Submission status: Runtime Error

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

N,M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    G[x].append(y)
#G[i]は頂点iから辺でつながっている頂点のlist
def topological_sort(g):
    topological_list = []
    visited = list()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.append(n)
    
    for i in range(len(g)):
        if i not in visited:
            dfs(i)
        
    return topological_list[::-1]

T = topological_sort(G)
dist = [0]*N
for n in T:
    for v in G[n]:
        dist[v] = max(dist[v],dist[n]+1)       
        
print(max(dist),T)

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, y = x -1, y-1
  g[x].append(y)  

# dp[v]: ノードvを起点にしたときの、Gの有効パスの長さの最大値
dp = [-1]*n
def rec(v):
  if dp[v] != -1:
    return dp[v]
  else:
    res = 0
    for u in g[v]:
      res = max(res, rec(u)+1)
    dp[v] = res
    return dp[v]
  
for i in range(n):
  rec(i)
print(max(dp))

Submission status: Runtime Error

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

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

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

def rec(x):
 if memo[x]!=-1:
  return memo[x]

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

 memo[x]=res
 return res

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

Submission status: Runtime Error

Solution code:
def path(start):
    if dp[start]!=-1:
        return dp[start]
    visited[start]=1
    maxi=-1
    for i in adjacency_list[start]:
        maxi=max(maxi,path(i))
    dp[start]=maxi+1
    return dp[start]
N,M=map(int,input().split())
dp=[-1]*(N+1)
visited=[0]*(N+1)
adjacency_list=[]
for i in range(N+1):
    adjacency_list.append([])
# print(adjacency_list)
for r in range(M):
    u,v=map(int,input().split())
    adjacency_list[u].append(v)
# print(adjacency_list)
for i in range(1,N+1):
    if len(adjacency_list[i])==0:
        dp[i]=0
# print(dp)
for i in range(1,N+1):
    if (visited[i]==0):
        path(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

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

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

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

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=[[]for _ in range(n)]
c=[0]*n
import sys
sys.setrecursionlimit(10**5)
for i in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)
from functools import lru_cache
@lru_cache(maxsize=n)
def l(k):
    return max([l(i)for i in p[k]]+[0])+1
print(max([l(i)for i in range(n)])-1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=[[]for _ in range(n)]
c=[0]*n
import sys
sys.setrecursionlimit(n)
for i in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)
from functools import lru_cache
@lru_cache(maxsize=n)
def l(k):
    return max([l(i)for i in p[k]]+[0])+1
print(max([l(i)for i in range(n)])-1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=[[]for _ in range(n)]
c=[0]*n
for i in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)
from functools import lru_cache
@lru_cache(maxsize=9*n)
def l(k):
    return max([l(i)for i in p[k]]+[0])+1
print(max([l(i)for i in range(n)])-1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=[[]for _ in range(n)]
c=[0]*n
for i in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)
from functools import lru_cache
@lru_cache(maxsize=n)
def l(k):
    return max([l(i)for i in p[k]]+[0])+1
print(max([l(i)for i in range(n)])-1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=[[]for _ in range(n)]
c=[0]*n
for i in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)
from functools import lru_cache
@lru_cache(maxsize = None)
def l(k):
    return max([l(i)for i in p[k]]+[0])+1
print(max([l(i)for i in range(n)])-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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

dp = [-1 for _ in range(n)]
ans = 0
for i in range(n):
    ans = max(ans, rec(i, dp, E))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline  #文字列入力では注意！
from copy import deepcopy
from functools import lru_cache
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
s = set()
for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    s.add(y)
    graph[x].append(y)

@lru_cache(max = None)
def dfs(x):
    print(x,graph[x])
    if not graph[x]:
        return 0
    stack = deepcopy(graph[x])
    ret = 0
    while stack:
        now = stack.pop(0)
        ret = max(ret,dfs(now)+1)
    return ret

ans = 0
for i in range(N):
    if i not in s:
        ans = max(ans,dfs(i))
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
s = set()
for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    s.add(y)
    graph[x].append(y)

def dfs(x):
    if not graph[x]:
        return 1
    stack = graph[x]
    while stack:
        now = stack.pop(0)
        ret = 0
        ret = max(ret,dfs(now)+1)
    return ret

ans = 0
for i in range(N):
    if i not in s:
        ans = max(ans,dfs(i))
print(ans)

Submission status: Runtime Error

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

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

    dp[v] = res

    return res

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

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

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
res ={}
for _ in range(m):
    x,y = map(int,input().split())
    res[x] = res.get(x,[]) + [y]
memo = {} #nodeを始点としたパスの最長長さ
def dfs(node):
    if node in memo:
        return memo[node]
    a = 0
    for n in res.get(node,[]):
        a = max(a,dfs(n)+1)
    memo[node] = a
    return memo[node]

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
res ={}
for _ in range(m):
    x,y = map(int,input().split())
    res[x] = res.get(x,[]) + [y]
memo = {} #nodeを始点としたパスの最長長さ
def dfs(node):
    if node in memo:
        return memo[node]
    a = 0
    for n in res.get(node,[]):
        a = max(a,dfs(n)+1)
    memo[node] = a
    return memo[node]

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
res ={}
for _ in range(m):
    x,y = input().split()
    res[x] = res.get(x,[]) + [y]
memo = {} #nodeを始点としたパスの最長長さ
def dfs(node):
    if node in memo:
        return memo[node]
    a = 0
    for n in res.get(node,[]):
        a = min(a,dfs(n)+1)
    memo[node] = a
    return memo[node]

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

Submission status: Runtime Error

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

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


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

    res = 0
    for child in graph[v]:
        res = max(res, dfs(child) + 1)
    dp[v] = res
    return res


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


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

dp = [-1] * N

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

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

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
t_table = {}
for i in range(M):
	x,y = map(int, input().split())
	if x-1 in t_table: t_table[x-1].append(y-1)
	else: t_table[x-1] = [y-1]
ans = 0
dp = [1 for _ in range(N)]
zerolist = [0 for _ in range(N)]
while True:
	pnode = dp.copy()
	dp = [0 for _ in range(N)]
	for i in range(N):
		if pnode[i] == 1 and i in t_table:
			for j in t_table[i]:
				if dp[j]==0 : dp[j]= 1
	if(dp == zerolist):
	 	print(ans)
	 	break
	ans += 1