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 sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from collections import deque
N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    if flag[x]:
        return None
    else:
        flag[x] = 1
        if adj[x]:
            for a in adj[x]:
                dfs(a)
        global ans
        ans.appendleft(x)

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

#print(ans)

dp = [0]*N
for a in ans:
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from collections import deque
N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    #if flag[x]:
        #return None
    if flag[x] == 0:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

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

#print(ans)

dp = [0]*N
for a in ans:
    for b in adj[a]:
        dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from collections import deque
N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    if flag[x]:
        return None
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

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

#print(ans)

dp = [0]*N
for a in ans:
    for b in adj[a]:
        dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from collections import deque
N, M = mi()
x = li2(M)

h = [0]*N
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    h[x[i][1]] += 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    if flag[x]:
        return False
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

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

#print(ans)

dp = [0]*N
for a in ans:
    for b in adj[a]:
        dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

#from collections import deque
N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
#ans = deque([])
ans = []

def dfs(x):
    if flag[x]:
        return False
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.append(x)

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

#print(ans)

dp = [0]*N
for a in ans[::-1]:
    for b in adj[a]:
        dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from collections import deque
N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    if flag[x]:
        return False
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

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

#print(ans)

dp = [0]*N
for a in ans:
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from collections import deque
N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    if flag[x]:
        return False
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

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

#print(ans)

dp = [0]*N
for a in ans:
    for b in adj[a]:
        dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Runtime Error

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

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

# xは始点、yは次点
for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    g[x].append(y)
    
dp = [-1]*n
 
def solve(i): # 始点iから行ける場所を探索
    # すでに計算されているなら、後の距離は計算できている
    if dp[i] != -1:
        return dp[i]
    # 初期は長さ0
    tmp = 0
    # 始点iから次点にDFS
    for j in g[i]:
        #今までの距離と比較
        tmp = max(tmp, dfs(j) + 1)
    # dp[i]はiからスタートして最長距離が記録される
    # 空のリスト（もう次点が存在しない）にたどり着いたらDFS終わり
    dp[i] = tmp
    return tmp
 
for i in range(n):
    solve(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
def solve(n, graph, end_at):
    def dp(i):
        if len(graph[i]) == 0:
            return 0
        if dist[i] != 0:
            return dist[i]
        for j in graph[i]:
            dist[i] = max(dist[i], dp(j))
        dist[i] += 1
        return dist[i]

    dist = [0] * n
    for i in range(n):
        if end_at[i]:
            dp(i)

    return max(dist)


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    graph = [[] for _ in range(n)]
    end_at = [True] * n

    for i in range(m):
        x, y = inp()
        x, y = x-1, y-1
        graph[y].append(x)
        end_at[x] = False

    print(solve(n, graph, end_at))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def solve(n, graph, end_at):
    def dp(i):
        if not graph[i]:
            return 0
        if dist[i]:
            return dist[i]
        for j in graph[i]:
            dist[i] = max(dist[i], dp(j))
        dist[i] += 1
        return dist[i]

    dist = [0] * n

    for i in range(n):
        if end_at[i]:
            dp(i)

    return max(dist)


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    graph = [[] for _ in range(n)]
    end_at = [True] * n

    for i in range(m):
        x, y = inp()
        x, y = x-1, y-1
        graph[y].append(x)
        end_at[x] = False
    print(solve(n, graph, end_at))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def solve(n, graph, is_root):
    def dfs(i, graph, dist):
        for j in graph[i]:
            if dist[j] < dist[i] + 1:
                dist[j] = dist[i] + 1
                dfs(j, graph, dist)

    dist = [0] * n
    for i in range(0, n):
        if is_root[i]:
            dfs(i, graph, dist)
    return max(dist)


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    graph = [[] for _ in range(n)]
    is_root = [True] * n

    for i in range(m):
        x, y = inp()
        graph[x-1].append(y-1)
        is_root[y-1] = False
    print(solve(n, graph, is_root))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def solve(n, graph, is_root):
    def dfs(i, graph, dist):
        for j in graph[i]:
            dist[j] = max(dist[j], dist[i] + 1)
            dfs(j, graph, dist)

    dist = [0] * n
    for i in range(0, n):
        if is_root[i]:
            dfs(i, graph, dist)
    return max(dist)


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    graph = [[] for _ in range(n)]
    is_root = [True] * n

    for i in range(m):
        x, y = inp()
        graph[x-1].append(y-1)
        is_root[y-1] = False
    print(solve(n, graph, is_root))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

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

e_list = [[] for i in range(N)]

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

memo = [-1]*N

def DFS(v):
    if memo[v]!=-1:
        return memo[v]
    if len(e_list[v])==0:
        memo[v] = 0
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    memo[v] = res
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    
    if res>ans:
        ans = res
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

e_list = [[] for i in range(N)]

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

@lru_cache(maxsize=500000)
def DFS(v):
    if len(e_list[v])==0:
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    
    if res>ans:
        ans = res
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

e_list = [[] for i in range(N)]

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

@lru_cache(maxsize=200000)
def DFS(v):
    if len(e_list[v])==0:
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    
    if res>ans:
        ans = res
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)

Submission status: Runtime Error

Solution code:
def abc(x,e):
    try:
        c=e[x]
    except:
        return 0
    try:
        return d[x]
    except:
        pass
    c=0
    for j in e[x]:
        c=max(c,1+abc(j,e))
    d[x]=c
    return c
        
        
n,k=map(int,input().split())
d={}
e={}
for i in range(k):
    a,b=map(int,input().split())
    try:
        e[a].append(b)
    except:
        e[a]=[b]
for i in range(1,n+1):
    abc(i,e)

print(max(d.values()))

Submission status: Runtime Error

Solution code:
def abc(x,e):
    try:
        c=e[x]
    except:
        return 0
    try:
        return d[x]
    except:
        pass
    c=0
    for j in e[x]:
        c=max(c,1+abc(j,e))
    d[x]=c
    return c
        
        
n,k=map(int,input().split())
d={}
e={}
for i in range(k):
    a,b=map(int,input().split())
    try:
        e[a].append(b)
    except:
        e[a]=[b]


print(max(d.values()))

Submission status: Runtime Error

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

dp=[-1]*(N+1) #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

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())
G=[[] for _ in range(N)]
for _ in  range(M):
    xi,yi=map(int,input().split())
    G[xi-1].append(yi-1)

dp=[-1]*N #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

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

G=[[] for _ in range(N)]
for _ in  range(M):
    xi,yi=map(int,input().split())
    G[xi-1].appedn(yi-1)

dp=[-1]*N #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

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())
G = dict([[i, []] for i in range(N)])
for _ in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)

dp = [-1] * N


def rec(v):
    if dp[v] >= 0:
        return dp[v]
    if len(G[v]) == 0:
        return 0

    ret = -1
    for nv in G[v]:
        ret = max(ret, rec(nv) + 1)

    return ret


print(max([rec(v) for v in range(N)]))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x,y = map(int,input().split())
        edge[x-1].append(y-1)
        
    dist = [-1 for _ in range(N)]
            
    def dfs(s):
        if dist[s] != -1:
            return dist[s]
        else:
            ret = 0
            for fol in edge[s]:
                ret = max(ret,dfs(fol)+1)
            dist[s] = ret
            return ret
    
    ans = 0    
    for i in range(N):
        ans = max(ans,dfs(i))
        
    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 10**9 +7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]


def dfs(root):
    global ans,g
    if ans[root]:return 

    temp = 0
    for j in g[root]:dfs(j)
    if len(g[root]):temp = max(ans[j] for j in g[root])
    ans[root] = 1 + temp

n,m = li()
g = defaultdict(set)
for i in range(m):
    a,b = li()
    g[a].add(b)

ans = [0]*(n + 1)

for j in range(1,n + 1):
    if not ans[j]:dfs(j)

print(max(ans) - 1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 10**9 +7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]


def dfs(root):
    global ans,g
    if ans[root]:return ans[root]

    temp = 0
    if len(g[root]):temp = max(dfs(j) for j in g[root])
    ans[root] = 1 + temp
    return ans[root]

n,m = li()
g = defaultdict(set)
for i in range(m):
    a,b = li()
    g[a].add(b)

ans = [0]*(n + 1)

for j in range(1,n + 1):
    if not ans[j]:dfs(j)
print(max(ans) - 1)

Submission status: Runtime Error

Solution code:
#dpg
#根になってるものからsearch
#1.行き先にいくための現時点での最長経路と根から来た場合の経路を比較
#2.その枝はもう見なくて良いので削除(行き先に入る枝のカウントを1減らす)
#入る枝がなくなったら根として考えてそっからまたsearch
#計算量はsearchの回数分(m+n)
n, m = map(int, input().split())
dest = [[] for _ in range(n)]
comein = [0 for _ in range(n)]
ro = [True for _ in range(n)]
dp = [0 for _ in range(n)]
for _ in range(m):
	x, y = map(int, input().split())
	dest[x-1].append(y-1)
	comein[y-1] += 1
	ro[y-1] = False

def search(leaf):
	global dp
	for i in dest[leaf]:
		comein[i] -= 1
		dp[i] = max(dp[i], dp[leaf] + 1)
		if comein[i] == 0:
			search(i)
	return

for j in range(n):
	if ro[j] == True:
		search(j)

print(max(dp))

Submission status: Runtime Error

Solution code:
#dpg
#根になってるものからsearch
#1.行き先にいくための現時点での最長経路と根から来た場合の経路を比較
#2.その枝はもう見なくて良いので削除(行き先に入る枝のカウントを1減らす)
#入る枝がなくなったら根として考えてそっからまたsearch
#計算量はsearchの回数分(m+n)
n, m = map(int, input().split())
dest = [[] for _ in range(n)]
comein = [0 for _ in range(n)]
for _ in range(m):
	x, y = map(int, input().split())
	dest[x-1].append(y-1)
	comein[y-1] += 1
dp = [0 for _ in range(n)]

def search(leaf):
	global dp
	for i in dest[leaf]:
		comein[i] -= 1
		dp[i] = max(dp[i], dp[leaf] + 1)
		if comein[i] == 0:
			search(i)
	return
ro = []
for i in range(n):
	if comein[i] == 0:
		ro.append(i)
if ro != []:
	for j in ro:
		search(j)

print(max(dp))

Submission status: Runtime Error

Solution code:
#dpg
#根になってるものからsearch
#1.行き先にいくための現時点での最長経路と根から来た場合の経路を比較
#2.その枝はもう見なくて良いので削除(行き先に入る枝のカウントを1減らす)
#入る枝がなくなったら根として考えてそっからまたsearch
#計算量はsearchの回数分(m+n)
n, m = map(int, input().split())
dest = [[] for _ in range(n)]
comein = [0 for _ in range(n)]
for _ in range(m):
	x, y = map(int, input().split())
	dest[x-1].append(y-1)
	comein[y-1] += 1
dp = [0 for _ in range(n)]

def search(leaf):
	global dp
	for i in dest[leaf]:
		comein[i] -= 1
		dp[i] = max(dp[i], dp[leaf] + 1)
		if comein[i] == 0:
			search(i)
	return
ro = []
for i in range(n):
	if comein[i] == 0:
		ro.append(i)
for j in ro:
	search(j)

print(max(dp))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
in_path = defaultdict(lambda: [])
out_path = defaultdict(lambda: [])

for m in range(M):
    x, y = map(int, input().split())
    in_path[y].append(x)
    out_path[x].append(y)

check = [False]*(N+1)
memo = [0]*(N+1)

def dp(i):
    if check[i] == True:
        return memo[i]
    else:
        check[i] = True
        if not out_path[i]:
            memo[i] = 0
            return 0
        else:
            max_path = 0
            for node in out_path[i]:
                max_path = max(dp(node), max_path)
            max_path += 1
            memo[i] = max_path
            return max_path


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

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int dfs(vector<int> graph[], int vertex, int N);
// template<class T>
void printvector(vector<int> &toprint)
{   
    for(int i = 0; i < toprint.size(); i++) cout << toprint[i] << " ";
    cout << endl;
}
// USING ADJENCY LIST TO STORE vertices 
int N, M; // Vertices, Edges
int main()
{
    cin >> N >> M;
    vector<int>graph[N+1];
    int x1, y1;
    for(int i = 1; i <= M; i++)
    {
        cin >> x1 >> y1;
        graph[x1].push_back(y1);
    }
    // cout << endl;
    
    // for(int v = 1; v <= N; v++)
    // {
    //     printvector(graph[v]);
    // }
    int finalmax = INT_MIN;
    for(int i = 1; i <= N; i++)
    {
        finalmax = max(finalmax, dfs(graph, i, N));
    }

    cout << finalmax << endl;

    return 0;

}

int dfs(vector<int> graph[], int vertex, int N)
{
    if (graph[vertex].size() == 0)
    {
        return 0;
    }
    int maximum = INT_MIN;
    for(auto v : graph[vertex])
    {
        maximum = max(maximum , 1 + dfs(graph, v, N));
    }

    return maximum;
}

Submission status: Runtime Error

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

l = [[] for _ in range(n)]

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

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

def seer(cx):
  
  if dp[cx] >= 0:
    return dp[cx]
  else:
    tmp = 0
    nx = l[cx]
    if len(nx) == 0 :
      dp[cx] = 0 
    else:
      for j in nx:
        tmp = max(seer(j),tmp)
    
      dp[cx] = tmp + 1
    return dp[cx]


for i in range(n):
  seer(i)
  
print(max(dp))

Submission status: Runtime Error

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

l = [[] for _ in range(n)]

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

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

def seer(cx):
  if dp[cx] >= 0:
    return dp[cx]
  else:
    nx = l[cx]
    if len(nx) == 0 :
      dp[cx] = 0 
    else:
      for j in nx:
        tmp = max(seer(j),tmp)
    
      dp[cx] = tmp + 1
    return dp[cx]


for i in range(n):
  seer(i)
  
print(max(dp))

Submission status: Runtime Error

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

l = [[] for _ in range(n)]

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

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

def seer(cx):
  if dp[cx] >= 0:
    return dp[cx]
  else:
    nx = l[cx]
    if len(nx) == 0 :
      dp[cx] = 0 
    else:
      tmp = 0
      for j in nx:
        tmp = max(seer(j),tmp)
    
      dp[cx] = tmp + 1
    return dp[cx]


for i in range(n):
  seer(i)
  
print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = []
    for b in xy[a]:
      num = cal(b)
      dp[b] = num
      ans.append(num+1)
    return max(ans)
  return 0

if __name__ == "__main__":
  sys.setrecursionlimit(100000)
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()

Submission status: Runtime Error

Solution code:
def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = []
    for b in xy[a]:
      num = cal(b)
      dp[b] = num
      ans.append(num+1)
    return max(ans)
  return 0

if __name__ == "__main__":
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()

Submission status: Runtime Error

Solution code:
def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
      out = max(out, dp[i])
    else:
      out = max(out, cal(i))
  print(out)

def cal(a):
  if xy[a]:
    ans = []
    for b in xy[a]:
      num = cal(b)
      dp[b] = num
      ans.append(num+1)
    return max(ans)
  return 0

if __name__ == "__main__":
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()

Submission status: Runtime Error

Solution code:
N,M=map(int, input().split())
A=[list(map(int, input().split())) for i in range(M)]
G=[[]for i in range(N)]
for a,b in A:
  G[a-1].append(b-1)
def chmax(a,b):
  if a>=b:
    return a
  else:
    return b
dp=[-1]*N
def rec(v):
  if dp[v]!=-1:
    return dp[v]
  ans=0
  for i in G[v]:
    ans=chmax(ans,rec(i)+1)
  dp[v]=ans
  return dp[v]
    
ans=0
for i in range(N):
  ans=chmax(ans,rec(i))
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int, input().split())
A=[list(map(int, input().split())) for i in range(M)]
G=[[]for i in range(N)]
for a,b in A:
  G[a-1].append(b-1)

dp=[-1]*N
def rec(v):
  if dp[v]!=-1:
    return dp[v]
  ans=0
  for i in G[v]:
    ans=max(ans,rec(i)+1)
  dp[v]=ans
  return dp[v]
    
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())
A=[list(map(int, input().split())) for i in range(M)]
G=[[]for i in range(N)]
for a,b in A:
  G[a-1].append(b-1)
print(G)

dp=[-1]*N
def rec(v):
  if dp[v]!=-1:
    return dp[v]
  ans=0
  for i in G[v]:
    ans=max(ans,rec(i)+1)
  dp[v]=ans
  return dp[v]
    
ans=0
for i in range(N):
  ans=max(ans,rec(i))
print(ans)

Submission status: Runtime Error

Solution code:
import math

dp = [-1]*(100*1000+1)
tab = [[] for x in range(100*1000+1)]

def get_max(root):
    if(dp[root] > -1): return dp[root]
    
    mi = 0
    for nei in tab[root]:
        mi = max(mi,get_max(nei)+1)
    dp[root] = mi
    return dp[root]
def main():
    n,m = map(int,input().split())
    
    for x in range(m):
        a,b = map(int,input().split())
        a-=1;b-=1
        tab[a].append(b)
    
    for x in range(n):
        get_max(x) 
    
    print(max(dp))
main()

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
sys.setrecursionlimit(10000)

N, M = input_nums()

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

for i in range(M):
    x, y = input_nums()
    x -= 1
    y -= 1
    G[x].append(y)

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

def rec(v: int):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in G[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
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
sys.setrecursionlimit(5000)

N, M = input_nums()

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

for i in range(M):
    x, y = input_nums()
    x -= 1
    y -= 1
    G[x].append(y)

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

def rec(v: int):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in G[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
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
sys.setrecursionlimit(3000)

N, M = input_nums()

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

for i in range(M):
    x, y = input_nums()
    x -= 1
    y -= 1
    G[x].append(y)

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

def rec(v: int):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in G[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
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
sys.setrecursionlimit(2000)

N, M = input_nums()

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

for i in range(M):
    x, y = input_nums()
    x -= 1
    y -= 1
    G[x].append(y)

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

def rec(v: int):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in G[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)