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:
import pdb
import networkx as nx

## グラフの作成
graph = nx.DiGraph()

Submission status: Runtime Error

Solution code:
import pdb
import networkx as nx

## グラフの作成
graph = nx.DiGraph()

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

## ノードを追加する
for i in range(N):
  graph.add_node(i)

## ノード間をエッジでつなぐ
for i,j in pairs:
  graph.add_edge(i, j, weight=-1)

bell_list = list(nx.all_pairs_bellman_ford_path_length(graph))
min_length = 0
for i in range(1,N+1):
  for bell in bell_list[i][1].values():
    min_length = min(min_length, bell)

print(-min_length)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10000000)
def calc(dp,adj,i):
    if(len(adj[i])==0):
        dp[i]=0
    elif dp[i]<0:
        for j in adj[i]:
            dp[i]=max(dp[i],calc(dp,adj,j))
        dp[i]+=1
    return dp[i]
n,m=map(int,input().split())
adj=[]
for i in range(n+1):
    adj.append([])
for i in range (m):
    x,y=map(int,input().split())
    adj[x].append(y)
dp=[-1]*(n+1);
for i in range(1,n+1):
    calc(dp,adj,i)
print(max(dp))

Submission status: Runtime Error

Solution code:
def calc(dp,adj,i):
    if(len(adj[i])==0):
        dp[i]=0
    elif dp[i]<0:
        for j in adj[i]:
            dp[i]=max(dp[i],calc(dp,adj,j))
        dp[i]+=1
    return dp[i]
n,m=map(int,input().split())
adj=[]
for i in range(n+1):
    adj.append([])
for i in range (m):
    x,y=map(int,input().split())
    adj[x].append(y)
dp=[-1]*(n+1);
for i in range(1,n+1):
    calc(dp,adj,i)
print(max(dp))

Submission status: Runtime Error

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

_map = {}
for i in range(n):
    _map[i+1] = []

for i in range(m):
    [x1, y1] = map(int, input().split())

    _map[y1].append(x1)

_memo = {}

def lpath(vertex):
    if vertex in _memo:
        return _memo[vertex]

    if len(_map[vertex]) == 0:
        return 0
    else:
        _max = 0
        for nv in _map[vertex]:
            # print(nv)
            x = lpath(nv)
            if (x > _max):
                _max = x

        _memo[vertex] = _max + 1
        return _max + 1

global_longest_path = 0
for i in range(n):
    longest_path_to_cur_node = lpath(i + 1)
    if global_longest_path < longest_path_to_cur_node:
        global_longest_path = longest_path_to_cur_node

print(global_longest_path)

Submission status: Runtime Error

Solution code:

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

_map = {}
for i in range(n):
    _map[i+1] = []

for i in range(m):
    [x1, y1] = map(int, input().split())

    _map[y1].append(x1)

_memo = {}

def lpath(vertex):
    if vertex in _memo:
        return _memo[vertex]

    if len(_map[vertex]) == 0:
        return 0
    else:
        _max = 0
        for nv in _map[vertex]:
            # print(nv)
            x = lpath(nv)
            if (x > _max):
                _max = x

        _memo[vertex] = _max + 1
        return _max + 1

global_longest_path = 0
for i in range(n):
    longest_path_to_cur_node = lpath(i + 1)
    if global_longest_path < longest_path_to_cur_node:
        global_longest_path = longest_path_to_cur_node

print(global_longest_path)

Submission status: Runtime Error

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

dp = [-1 for k in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)

Submission status: Runtime Error

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

dp = [-1 for i in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)

Submission status: Runtime Error

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

dp = [-1 for i in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
        
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    dp = [-1 for _ in range(10 ** 5 + 10)]

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

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#g-%E5%95%8F%E9%A1%8C---longest-path
    def rec(v):
        if dp[v] != -1:
            return dp[v]

        result = 0

        for next_v in graph[v]:
            result = max(result, rec(next_v) + 1)

        dp[v] = result

        return dp[v]

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


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

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

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#g-%E5%95%8F%E9%A1%8C---longest-path
    def rec(v):
        if dp[v] != -1:
            return dp[v]

        result = 0

        for next_v in graph[v]:
            result = max(result, rec(next_v) + 1)

        dp[v] = result

        return dp[v]

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    dp = dict()

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

        dp[(xi, yi)] = 0

    def dfs(v, parent=-1, count=0):
        count += 1

        for u in graph[v]:
            if u == parent:
                continue

            dp[(v, u)] = max(dp[(v, u)], count)
            dfs(u, v, dp[(v, u)])

    for i in range(n):
        if len(graph[i]) == 0:
            continue

        dfs(i)

    print(max(dp.values()))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    dp = dict()

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

        dp[(xi, yi)] = 0

    def dfs(v, parent=-1, count=0):
        count += 1

        for u in graph[v]:
            if u == parent:
                continue

            dp[(v, u)] = max(dp[(v, u)], count)
            dfs(u, v, dp[(v, u)])

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

    print(max(dp.values()))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

dp = [-1] * N
def dist(v):
  if dp[v] != -1: return dp[v]
  
  res = 0
  for to in edge[v]:
    res = max(res, dist(to) + 1)
  
  dp[v] = res
  return res

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

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


class Graph:
    def __init__(self, N):
        self.in_degree = [0] * (N+1)
        self.dist = [0] * (N+1)
        self.visited = [False] * (N+1)
        self.edges = defaultdict(list)
        self.N = N

    def add_edge(self, x, y):
        self.edges[x].append(y)
        self.in_degree[y] += 1

    def dfs(self, x):
        self.visited[x] = True
        for y in self.edges[x]:
            self.dist[y] = max(self.dist[y], self.dist[x] + 1)
            self.in_degree[y] -= 1
            if self.in_degree[y] == 0:
                self.dfs(y)

    def longest_path(self):
        for i in range(1, self.N+1):
            if not self.visited[i] and self.in_degree[i] == 0:
                self.dfs(i)

        ans = 0
        for i in range(1, self.N+1):
            ans = max(ans, self.dist[i])

        return ans


def main():
    N, M = map(int, input().split())
    graph = Graph(N)
    for _ in range(M):
        x, y = map(int, input().split())
        graph.add_edge(x, y)

    ans = graph.longest_path()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict


class Graph:

    def __init__(self, N):
        self.graph = defaultdict(list)
        self.N = N
        self.memo = [-1] * (N+1)
        self.tovisit = set(range(1, N+1))

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

    def _longest_path(self, node):
        if self.memo[node] == -1:
            res = 0
            for y in self.graph[node]:
                res = max(res, 1 + self._longest_path(y))

            self.memo[node] = res
            self.tovisit.discard(node)

        return self.memo[node]

    def longest_path(self):
        while self.tovisit:
            self._longest_path(self.tovisit.pop())

        res = 0
        for i in range(1, self.N+1):
            res = max(res, self.memo[i])

        return res


def main():

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

    ans = graph.longest_path()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
root_cand = set(list(range(1, n+1))) - not_root
root_cand = deque(root_cand)
dp = [0] * (n+1)
def dfs(node, count):
    dp[node] = max(dp[node], count + 1)
    if len(adjacent_list[node]) != 0:
        for i in adjacent_list[node]:
            dfs(i, dp[node])

while len(root_cand) != 0:
    root = root_cand.pop()
    dfs(root, -1)
print(max(dp))

Submission status: Runtime Error

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

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

dist = [0] * N
q = [x for x in range(N) if in_G[x] == 0]

while q:
    v = q.pop

    for g in G[v]:
        dist[g] = max(dist[g], dist[v] + 1)
        in_G[g] -= 1
        if in_G[g] == 0:
            q.append(g)

print(max(dist))

Submission status: Runtime Error

Solution code:
def dfs(cur, visited, dis):
    visited[cur] = 1
    if cur in adj_list:
        for item in adj_list[cur]:
            if not visited[item]:
                dfs(item, visited, dis)
            dis[cur] = max(dis[cur], 1+dis[item])


v, e = map(int, input().split())
adj_list = {}
for _ in range(e):
    x, y = map(int, input().split())
    adj_list.setdefault(x, []).append(y)
visited = [0] * (v + 1)
dis = [0] * (v + 1)
for i in range(v + 1):
    if not visited[i]:
        dfs(i, visited, dis)
print(max(dis))

Submission status: Runtime Error

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

# node iを起点とした時の有効パスの最大値
def rec(i):
    if dp[i] != -1:
        return dp[i]
    res = 0
    for v in G[i]:
        res = max(res, rec(v)+1)
    dp[i] = res
    return res

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

Submission status: Runtime Error

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

# node iを起点とした時の有効パスの最大値
def rec(i):
    if dp[i] != -1:
        return dp[i]
    res = 0
    for v in G[i]:
        res = max(res, rec(v)+1)
    return res

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())
dp = [-1] * (10 ** 5 + 7)

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
def recursion_g(eges, length, f):
    if length[f] != -1:
        return length[f]
    if not eges[f]:
        length[f] = 0
        return 0
    memo = []
    for t in eges[f]:
        memo.append(recursion_g(eges, length, t) + 1)
    length[f] = max(memo)
    return length[f]


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

for i in range(N):
    recursion_g(edges, length, i)
print(max(length))

Submission status: Runtime Error

Solution code:
def recursion_g(eges, length, f):
    if length[f] != -1:
        return length[f]
    if not eges[f]:
        length[f] = 0
        return 0
    memo = []
    for t in eges[f]:
        memo.append(recursion_g(eges, length, t) + 1)
    length[f] = max(memo)
    return length[f]


def p_g():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    length = [-1] * N
    for _ in range(M):
        x, y = map(int, input().split())
        edges[x - 1].append(y - 1)

    for i in range(N):
        recursion_g(edges, length, i)
    print(max(length))


if __name__ == '__main__':
    p_g()

Submission status: Runtime Error

Solution code:
import numpy as np
mod = 10**9+7
def MatPower(A, k):
    B = np.identity(len(A), dtype = object)
    while k:
        if k&1:
            B = np.dot(A, B)%mod
        A = np.dot(A, A)%mod
        k//=2
    return B
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype = object)
v = np.array([1]*N, dtype = object).T
An = MatPower(a, K)
v = np.dot(An, v)%mod
ans = 0
for i in range(N):
    ans+=v[i]
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:

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

indegree = [0] * N  # 入次数
for i in range(M):
    a, b = [int(_) - 1 for _ in input().split()]
    E[a].append(b)
    indegree[b] += 1

sorted_nodes = []
dp = [0] * N


def rep(v):
    """初めて呼ばれたときに, そのノードからの最長ノード数を数えるイメージ"""
    if dp[v] != 0: return dp[v]
    for n in E[v]:
        dp[v] = max(dp[v], rep(n) + 1)
    return dp[v]

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

Submission status: Runtime Error

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 6)

def alg_memoization_recursion(f, d):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    d = collections.defaultdict(list)
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i, d))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
import collections
from functools import lru_cache

sys.setrecursionlimit(10 ** 10)
xy = []
d = collections.defaultdict(list)

@lru_cache(maxsize=None)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
import collections
from functools import lru_cache

xy = []
d = collections.defaultdict(list)

@lru_cache(maxsize=None)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
import collections
from functools import lru_cache

sys.setrecursionlimit(10 ** 5 + 1)
xy = []
d = collections.defaultdict(list)

@lru_cache(maxsize=10 ** 5 + 1)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
import collections
from functools import lru_cache

sys.setrecursionlimit(10 ** 5 + 1)
xy = []
d = collections.defaultdict(list)

@lru_cache(maxsize=None)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import numpy as np

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

def depth(now,score,d):
    global dp
    if dp[now]==0 or not(dp[now]):
        if d[now]:
            _score=[]
            for i in d[now]:
                _score.append(depth(i,score+1,d)-score)
            dp[now]=max(_score)
        else:
            return score

        return dp[now]+score

    else:
        return dp[now]+score



Max=0
for i in range(N):
    m=depth(i,0,d)
    if  m>Max:            
        Max=m
print(Max)

Submission status: Runtime Error

Solution code:
scores=[]
stamp=[]
N,M=map(int,input().split())
dp=[0 for i in range(N)]
d=[[] for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    d[x-1].append(y-1)

def depth(now,score):
    global scores,stamp,dp
    stamp.append(now)
    if d[now]:
        for i in d[now]:
             if dp[i]==0 or not(dp[i]):
                dp[i]=depth(i,score+1)
             else :
                 scores.append(score+dp[i])
    else:
        scores.append(score)
        return score


Max=0
for i in range(N):
    if not(i in stamp):
        depth(i,0)
        dp[i]=max(scores)
        if scores and dp[i]>Max:
            Max=max(scores)
        scores=[]
print(Max)

Submission status: Runtime Error

Solution code:
scores=[]
stamp=[]
def depth(now,score,d):
    global scores,stamp
    stamp.append(now)
    if d[now]:
        for i in d[now]:
            depth(i,score+1,d)
        return 
    else:
        scores.append(score)
        return 


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

Max=0
for i in range(N):
    if not(i in stamp):
        depth(i,0,d)
        if scores and max(scores)>Max:
            Max=max(scores)
        scores=[]
print(Max)

Submission status: Runtime Error

Solution code:
scores=[]
def depth(now,score,d):
    global scores
    if d[now]:
        for i in d[now]:
            depth(i,score+1,d)
        return 
    else:
        scores.append(score)
        return 


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

Max=0
for i in range(N):
    depth(i,0,d)
    if scores and max(scores)>Max:
        Max=max(scores)
    scores=[]
print(Max)

Submission status: Runtime Error

Solution code:
scores=[]
def depth(now,score,d):
    global scores
    if d[now]:
        for i in d[now]:
            depth(i,score+1,d)
    else:
        scores.append(score)
        return 


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

Max=0
for i in range(N):
    depth(i,0,d)
    if scores and max(scores)>Max:
        Max=max(scores)
    scores=[]
print(Max)

Submission status: Runtime Error

Solution code:
scores=[]
def depth(now,score,d):
    global scores
    if d[now]:
        for i in d[now]:
            depth(i,score+1,d)
    else:
        scores.append(score)


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

Max=0
for i in range(N):
    depth(i,0,d)
    if scores and max(scores)>Max:
        Max=max(scores)
    scores=[]
print(Max)

Submission status: Runtime Error

Solution code:
scores=[]
def depth(now,score,d):
    global scores
    if d[now]:
        for i in d[now]:
            depth(i,score+1,d)
    else:
        scores.append(score)


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

Max=0
for i in range(N):
    depth(i,0,d)
    if scores and max(scores)>Max:
        Max=max(scores)
    scores.clear()
print(Max)

Submission status: Runtime Error

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

scores=[]
def depth(now,score):
    global scores
    if d[now]:
        for i in d[now]:
            depth(i,score+1)
    else:
        scores.append(score)
Max=0
for i in range(N):
    depth(i,0)
    if max(scores)>Max:
        Max=max(scores)
    scores.clear()
print(Max)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)
def main():
    N, M = map(int, input().split())
    d = {}
    for _ in range(M):
        x, y = map(int, input().split())
        if x in d:
            d[x].append(y)
        else:
            d[x] = [y]
    l = {}
    m = 0
    for i in d:
        m = max(m, dfs(i, d, l))
    print(m)
def dfs(node, d, l):
    if node in l:
        return l[node]
    if node not in d:
        return 0
    a = 1 + max(dfs(i, d, l) for i in d[node])
    l[node] = a
    return a

main()

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
edges = {j : [] for j in range(N + 1)}
for i in range(M):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    edges[x].append(y)
for i in range(N):
    edges[N].append(i)

memo_ls = [None for i in range(N + 1)]


def dfs(last):
    if memo_ls[last] is not None:
        return memo_ls[last]
    if len(edges[last]) == 0:
        return 0
    cnt = max([dfs(_next) + 1 for _next in edges[last]])
    memo_ls[last] = cnt
    return cnt


print(dfs(N) - 1)

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
edges = {j : [] for j in range(N + 1)}
for i in range(M):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    edges[x].append(y)
for i in range(N):
    edges[N].append(i)

memo_ls = [None for i in range(N + 1)]


def dfs(last):
    if memo_ls[last] is not None:
        return memo_ls[last]
    if len(edges[last]) == 0:
        return 0
    cnt = max([dfs(next) + 1 for next in edges[last]])
    memo_ls[last] = cnt
    return cnt


print(dfs(N) - 1)

Submission status: Runtime Error

Solution code:
def toposort(grafo, nodo, stack, visitados):
    visitados[nodo] = True

    for i in grafo[nodo]:
        if visitados[i] == False:
            toposort(grafo, i, stack, visitados)

    stack.insert(0, nodo)


def longestPath(n, grafo, inicios):
    
    visitados = {i:False for i in grafo}
    dist = [-float('inf')] * (n+1)
    stack = []
    
    
    for i in grafo:
       if visitados[i] == False:
            toposort(grafo, i, stack, visitados)
    
    for i,v in enumerate(inicios):
        if v:
            dist[i] = 0

    while stack:
        u = stack.pop(0)
            
        for i in grafo[u]:
            dist[i] = max(dist[u] + grafo[u][i], dist[i])
    
    return max(dist)
    

n,m = [int(i) for i in input().split()]

grafo = {i:{} for i in range(1,n+1)}
inicios = [True for i in range(n+1)]
inicios[0] = False

for i in range(m):
    a,b = [int(x) for x in input().split()]
    grafo[a][b] = 1
    inicios[b] = 0

print(longestPath(n, grafo, inicios))

Submission status: Runtime Error

Solution code:
def dfs(node,adj,dp, vis):
    vis[node]=True
    for i in range(0,len(adj[node])):
        if not vis[adj[node][i]]:
            dfs(adj[node][i],adj,dp,vis)
        dp[node]=max(dp[node],1+dp[adj[node][i]])
        #print(dp)
def adde(adj,u,v):
    adj[u].append(v)
def findlongestpath(adj ,n):
    
    dp=[0]*(n+1)
    vis=[False]*(n+1)
    for g in range(n+1):
        if not vis[g]:
            dfs(g,adj,dp,vis)
    ans=0
    for i in range(1,n+1):
        ans=max(ans,dp[i])
    print(ans)
if __name__=="__main__":
    n,m=map(int,input().split())
    adj=[[] for j in range(n+1)]
    for i in range(m):
        x,y=map(int,input().split())
        adde(adj,x,y)
    #print(adj)
    findlongestpath(adj,n)

Submission status: Runtime Error

Solution code:
import sys

N, M = [int(s) for s in input().split()]
sys.setrecursionlimit(N)
dp = [-1] * (N+1)
neighbors = [[] for _ in range(N+1)]

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

def LP(v):
    if dp[v] != -1:
        return dp[v]
    else:
        res = 0
        lp = [-1]
        for nv in neighbors[v]:
            lp.append(LP(nv))
        res = max(res, max(lp) + 1)
        dp[v] = res
        return res

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

print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(s) for s in input().split()]

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

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

def LP(v):
    if dp[v] != -1:
        return dp[v]
    else:
        res = 0
        lp = [-1]
        for nv in neighbors[v]:
            lp.append(LP(nv))
        res = max(res, max(lp) + 1)
        dp[v] = res
        return res

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

print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(s) for s in input().split()]

dp = [-1] * (N+1)
neighbors = [[] for _ in range(1,N+1)]

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

def LP(v):
    if dp[v] != -1:
        return dp[v]
    else:
        res = 0
        lp = []
        for nv in neighbors[v]:
            lp.append(LP(nv))
        res = max(res, max(lp) + 1)
        dp[v] = res
        return res

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

print(ans)

Submission status: Runtime Error

Solution code:
def lp(node,memo,graph):
    if memo[node] != -1:
        return memo[node]
    cand = [0]
    if graph[node]:
        for neighbor in graph[node]:
            cand.append(lp(neighbor,memo,graph))
        maximam = max(cand)+1
    else:
        maximam = 0
    memo[node]=maximam
    return maximam

import sys
sys.setrecursionlimit(10**10)
N,M = map(int, input().split())
graph = {}
for i in range(N+1):
    graph[i] = []
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
ans = 0
memo = [-1]*(N+1)
for i in range(1,N+1):
    ans = max(ans, lp(i,memo,graph))
print(ans)

Submission status: Runtime Error

Solution code:
def lp(node,memo,graph):
    if memo[node] != -1:
        return memo[node]
    cand = [0]
    if graph[node]:
        for neighbor in graph[node]:
            cand.append(lp(neighbor,memo,graph))
        maximam = max(cand)+1
    else:
        maximam = 0
    memo[node]=maximam
    return maximam

N,M = map(int, input().split())
graph = {}
for i in range(N+1):
    graph[i] = []
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
ans = 0
memo = [-1]*(N+1)
for i in range(1,N+1):
    ans = max(ans, lp(i,memo,graph))
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
dp=[0]*(N+1)
path = [[] for _ in range[N]]
for i in range(M):
  x,y = map(int,input().split())
  path[x].append(y)
  dp[y]=-1
  
cur = []
for i in range(1,N+1):
  if dp[i]==0:
    cur.append(i)

while(cur):
  nxt = set()
  for x in cur:
    for y in path[x]:
      dp[y] = max(dp[y],dp[x]+1)
      nxt.add(y)
  cur = []
  for x in nxt:
    cur.append(y)
print(max(dp))

Submission status: Runtime Error

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

# dp[i]:頂点iを始点とする最長パスの長さ
dp = [-1 for _ in range(N)]

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

for i in range(N):
  rec(i)
print(max(dp))