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:
#G
N,M=map(int,input().split())
A=[[] for i in range(N+1)]
dp=[[] for j in range(N)]

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

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

print(result)

Submission status: Runtime Error

Solution code:
def util(adj, curr, dp):
    res = 0
    if dp[curr] != -1:
        return dp[curr]
    for next in adj[curr]:
        res = max(res,1 + util(adj, next, dp))
    dp[curr] = res
    return res
 
n, m = map(int, input().strip().split())
adj = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().strip().split())
    adj[x - 1].append(y - 1)
dp = [-1]*n
lp = 0
for i in range(n):
    lp = max(lp, util(adj, i, dp))
print(lp)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
 
dp = {}
def util(adj, curr):
    res = 0
    if curr in dp:
        return dp[curr]
    for next in adj[curr]:
        res = max(res,1 + util(adj, next))
    dp[curr] = res
    return res
 
n, m = map(int, input().strip().split())
adj = defaultdict(list)
for _ in range(m):
    x, y = map(int, input().strip().split())
    adj[x - 1].append(y - 1)
 
lp = 0
for i in range(n):
    lp = max(lp, util(adj, i))
print(lp)

Submission status: Runtime Error

Solution code:
dp = {}
def util(adj, curr):
    if curr in dp:
        return dp[curr]
    res = 0
    for next in adj[curr]:
        res = max(res, 1 + util(adj, next))
    dp[curr] = res
    return res

n, m = map(int, input().split())
adj = {}
for _ in range(m):
    x, y = map(int, input().split())
    if x in adj:
        adj[x].append(y)
    else:
        adj[x] = [y]

lp = 0
for i in range(1, n + 1):
    lp = max(lp, util(adj, i))
print(lp)

Submission status: Runtime Error

Solution code:
dp = {}
def util(adj, curr):
    if curr in dp:
        return dp[curr]
    res = 0
    for next in adj[curr]:
        res = max(res, 1 + util(adj, next))
    dp[curr] = res
    return res

n, m = map(int, input().strip().split())
adj = {}
for _ in range(m):
    x, y = map(int, input().strip().split())
    if x in adj:
        adj[x].append(y)
    else:
        adj[x] = [y]

lp = 0
for i in range(1, n + 1):
    lp = max(lp, util(adj, i))
print(lp)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

dp = {}
def util(adj, curr):
    res = 0
    if curr in dp:
        return dp[curr]
    for next in adj[curr]:
        res = max(res,1 + util(adj, next))
    dp[curr] = res
    return res

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

lp = 0
for i in range(n):
    lp = max(lp, util(adj, i))
print(lp)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

adj=defaultdict(list)
vis=[0]*(n+1)
ans=[0]*(n+1)

def dfs(root):
    vis[root]=1
    for i in range (len(adj[root])):
        if (vis[adj[root][i]]==0):
            dfs(adj[root][i])
        ans[root]=max(ans[root],ans[adj[root][i]]+1)
    return;

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

for i in range (1,n+1):
    if (vis[i]==0):
        dfs(i)

fa=0
for i in range (1,n+1):
    fa=max(fa,ans[i])

print(fa)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(vis,graph,node,dp):
    vis[node]=True
    for i in range(len(graph[node])):
        if not vis[graph[node][i]]:
            dfs(vis,graph,graph[node][i],dp)
        dp[node]=max(dp[node],1+dp[graph[node][i]])    
    
    


n,m=map(int,input().split())
graph=defaultdict(list)
for i in range(m):
    u,v=map(int,input().split())
    graph[u].append(v)

vis=[False]*(n+1)
dp=[0]*(n+1)
for i in range(n+1):
    if not vis[i]:
        dfs(vis,graph,i,dp)
        
print(max(dp))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

adj=defaultdict(list)
vis=[0]*(n+1)
ans=[0]*(n+1)

def dfs(root):
    vis[root]=1
    for i in range (len(adj[root])):
        if (vis[adj[root][i]]==0):
            dfs(adj[root][i])
        ans[root]=max(ans[root],ans[adj[root][i]]+1)
    return;

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

for i in range (1,n+1):
    if (vis[i]==0):
        dfs(i)

fa=0
for i in range (1,n+1):
    fa=max(fa,ans[i])

print(fa)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
adj=defaultdict(list)
vis=[0]*n
ans=[0]*n

def dfs(root):
    vis[root]=1
    for i in range (len(adj[root])):
        if (vis[adj[root][i]]==0):
            dfs(adj[root][i])
        ans[root]=max(ans[root],ans[adj[root][i]]+1)
    return;

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

for i in range (n):
    if (vis[i]==0):
        dfs(i)

fa=0
for i in range (n):
    fa=max(fa,ans[i])

print(fa)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
adj=defaultdict(list)
vis=[0]*n
ans=[0]*n

def dfs(root):
    vis[root]=1

    for i in adj[root]:
        if (vis[i]==0):
            dfs(i)
        ans[root]=max(ans[root],ans[i]+1)
    return;

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

for i in range (n):
    if (vis[i]==0):
        dfs(i)

fa=0
for i in range (n):
    fa=max(fa,ans[i])

print(fa)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
adj=defaultdict(list)
vis=[0]*n
ans=[0]*n

def dfs(root):
    vis[root]=1
    for i in adj[root]:
        if vis[i]==0:
            dfs(i)
        ans[root]=max(ans[root],ans[i]+1)
    return;

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

for i in range (n):
    if vis[i]==0:
        dfs(i)

fa=0
for i in range (n):
    fa=max(fa,ans[i])

print(fa)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
adj=defaultdict(list)
vis=[0]*n
ans=[0]*n

def dfs(root):
    vis[root]=1
    for i in adj[root]:
        if vis[i]==0:
            dfs(i)
        ans[root]=max(ans[root],ans[i]+1)

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

for i in range (n):
    if vis[i]==0:
        dfs(i)

fa=0
for i in range (n):
    fa=max(fa,ans[i])

print(fa)

Submission status: Runtime Error

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

def dfs(root):
    vis[root]=1
    for i in adj[root]:
        if vis[i]==0:
            dfs(i)
        ans[root]=max(ans[root],ans[i]+1)

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

for i in range (n):
    if vis[i]==0:
        dfs(i)

fa=0
for i in range (n):
    fa=max(fa,ans[i])

print(fa)

Submission status: Runtime Error

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

def dfs(root):
    vis[root]=1
    for i in adj[root]:
        if vis[i]==0:
            dfs(i)
        ans[root]=max(ans[root],ans[i]+1)

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

for i in range (1,n+1):
    if vis[i]==0:
        dfs(i)

fa=0
for i in range (1,n+1):
    fa=max(fa,ans[i])

print(fa)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def dfs(node, graph, dist, visited):
    if visited[node] == True:
        return dist[node]
    visited[node] = True
    for child in graph[node]:
        dist[node] = max(dist[node], 1+dfs(child, graph, dist, visited))
    return dist[node]


def main():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
    dist = [0]*(n+1)
    visited = [False]*(n+1)
    for node in range(1, n+1):
        if not visited[node]:
            dfs(node, graph, dist, visited)
    print(max(dist))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
dp = [-1]*(n+1)
path = [[] for i in range(n)]
X = []; Y = []
for i in range(m):
    x, y = map(int, input().split())
    X.append(x-1); Y.append(y-1)
    path[x-1].append(y-1)

def dfs(i):
    if dp[i]>0: return dp[i]
    res = 0
    if path[i]:
        for k in path[i]:
            res = max(res, dfs(k)+1)
    dp[i] = res
    return res

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())
dp = [-1]*n
path = [[] for i in range(n)]
X = []; Y = []
for i in range(m):
    x, y = map(int, input().split())
    X.append(x-1); Y.append(y-1)
    path[x-1].append(y-1)

def dfs(i):
    if dp[i]>0: return dp[i]
    res = 0
    for k in path[i]:
        res = max(res, dfs(k)+1)
    dp[i] = res
    return res

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())
d={}

for _ in range(m):
	a,b=map(int,input().split())
	if a in d:
		d[a].append(b)
	else:
		d[a]=[b]

c=[0]*(n+1)

def dfs(visited,u):
	visited.add(u)
	if u in d:
		for i in d[u]:
			if i not in visited:
				dfs(visited,i)
				#visited.add(i)
			c[u]=max(c[u],c[i]+1)

	#print(c)



v=set()
for i in range(1,n+1):
	#print(v)
	if i not in v:
		#v.add(i)
		dfs(v,i)
		#print(v)
#print(c)
print(max(c))

Submission status: Runtime Error

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

for _ in range(m):
	a,b=map(int,input().split())
	if a in d:
		d[a].append(b)
	else:
		d[a]=[b]

c=[0]*(n+1)
def dfs(visited,u):
	mx=0
	if u not in visited and u in d:
		for i in d[u]:
			if i not in visited:
				dfs(visited,i)
				visited.add(i)
				mx=max(mx,c[i]+1)
	c[u]=max(mx,c[u])

v=set()
for i in range(1,n+1):
	#print(v)
	if i not in v:
		#v.add(i)
		dfs(v,i)
#print(c)
print(max(c))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
d={}
for _ in range(m):
	a,b=map(int,input().split())
	if a in d:
		d[a].append(b)
	else:
		d[a]=[b]

c=[0]*(n+1)
def dfs(visited,u):
	mx=0
	if u not in visited and u in d:
		for i in d[u]:
			if i not in visited:
				dfs(visited,i)
				visited.add(i)
				mx=max(mx,c[i]+1)
	c[u]=max(mx,c[u])

for i in range(1,n+1):
	v=set()
	if i not in v:
		dfs(v,i)
#print(c)
print(max(c))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
d={}
for _ in range(m):
	a,b=map(int,input().split())
	if a in d:
		d[a].append(b)
	else:
		d[a]=[b]

c=[0]*(n+1)
def dfs(visited,u):
	mx=0
	if u not in visited and u in d:
		for i in d[u]:
			if i not in visited():
				dfs(visited,i)
				visited.add(i)
				mx=max(mx,c[i]+1)
	c[u]=max(mx,c[u])

for i in range(1,n+1):
	v=set()
	if i not in v:
		dfs(v,i)
#print(c)
print(max(c))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
d={}
for _ in range(m):
	a,b=map(int,input().split())
	if a in d:
		d[a].append(b)
	else:
		d[a]=[b]

c=[0]*(n+1)
def dfs(visited,u):
	mx=0
	if u not in visited and u in d:
		for i in d[u]:
			dfs(visited,i)
			visited.add(i)
			mx=max(mx,c[i]+1)
	c[u]=max(mx,c[u])

for i in range(1,n+1):
	v=set()
	if i not in v:
		dfs(v,i)
#print(c)
print(max(c))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
e = [list(map(int, input().split())) for _ in range(m)]
g = defaultdict(list)

for dep, dest in e:
    g[dep].append(dest)

memo = dict()

def f(i):
    if not i in memo:
        if not i in g:
            memo[i] = 0
        else:
            res = 0
            for dest in g[i]:
                res = max(res, f(dest) + 1)
            memo[i] = res
    return memo[i]

res = 1
for i in range(1, n+1):
    res = max(f(i), res) 
print(res)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as graph
n,m = map(int,input().split())
G = graph(list)
for i in range(m):
    start,end = map(int,input().split())
    G[start].append(end)
dp = [-1 for x 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 dp[v]

res = 0
for i in range(1,n+1):
    res = max(res,rec(i))
print(res)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
    Far[x] = r
    return r


for i in range(N):
    long(i)
print(max(Far))

Submission status: Runtime Error

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


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
    Far[x] = r
    return r


for i in range(N):
    long(i)
print(max(Far))

Submission status: Runtime Error

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


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
    Far[x] = r
    return r



for i in range(N):
    long(i)
print(max(Far))

Submission status: Runtime Error

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


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
        Far[x] = r
    return r



for i in range(N):
    long(i)
print(max(Far))

Submission status: Runtime Error

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

def Long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = Long(i) + 1
        r = max(r, l)
    return r
ans = 0
for i in range(N):
    ans = max(ans, Long(i))
print(ans)

Submission status: Runtime Error

Solution code:
def longdist(p, dp_l, out_l):
    if len(out_l[p]) == 0:
        return 0
    for q in out_l[p]:
        if dp_l[q] == -1:
            dp_l[q] = longdist(q, dp_l, out_l)
        dp_l[p] = max(dp_l[p], dp_l[q]+1)
    return dp_l[p]

n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

input, output = [[] for _ in range(n)], [[] for _ in range(n)]
for x, y in xy:
    input[y - 1].append(x - 1)
    output[x - 1].append(y - 1)

dp = [-1] * n
for i in range(n):
    if dp[i] == -1:
        dp[i] = longdist(i, dp, output)

print(max(dp))

Submission status: Runtime Error

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


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

    memo = {}

    def dfs(v):
        if v in memo:
            return memo[v]

        if graph[v]:
            res = max(dfs(child) for child in graph[v])
            memo[v] = res + 1
        else:
            res = 0
            memo[v] = 0

        return memo[v]

    print(max(dfs(i) for i in range(N)))


# 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:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, m = na()
xy = nan(m)

g = [[] for _ in range(n)]
for i in range(m):
    x, y = xy[i]
    x -= 1
    y -= 1
    g[x].append(y)

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache

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

dp = [-1]*N


@lru_cache(maxsize=None)
def rec(v):
    if len(E[v]) == 0:
        dp[v] = 0
        return dp[v]

    for to in E[v]:
        dp[v] = max(dp[v], rec(to)+1)
    return dp[v]


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

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache

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

dp = [-1]*N


@lru_cache(maxsize=10**5)
def rec(v):
    if len(E[v]) == 0:
        dp[v] = 0
        return dp[v]

    for to in E[v]:
        dp[v] = max(dp[v], rec(to)+1)
    return dp[v]


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

Submission status: Runtime Error

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

dp = [-1]*N


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

    for to in E[v]:
        dp[v] = max(dp[v], rec(to)+1)
    return dp[v]


for i in range(N):
    dp[i] = rec(i)
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())
    E[x-1].append(y-1)

dp = [-1]*N


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

    for to in E[v]:
        dp[v] = max(dp[v], rec(to)+1)
    return dp[v]


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

Submission status: Runtime Error

Solution code:
def f(x):
  if z[x]==-1:
  	z[x]=max([f(i) for i in v[x]]+[-1])+1
  return z[x]
n,m=map(int,raw_input().split())
v=[[] for _ in xrange(n)]
for x,y in [map(int,raw_input().split()) for _ in xrange(m)]:
  v[x-1].append(y-1)
z=[-1]*n
for i in xrange(n):
  if z[i]==-1:
    f(i)
print max(z)

Submission status: Runtime Error

Solution code:
def dfs(node,paths,dp,vis):
    vis[node]=True
    for i in range(0, len(paths[node])):
        if not vis[paths[node][i]]:
            dfs(paths[node][i],paths,dp,vis)
        dp[node]=max(dp[node],1+dp[paths[node][i]])
n,m=map(int,input().split())
paths=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    paths[a].append(b)
dp,vis=[0]*(n+1),[False]*(n+1)
for i in range(1,n+1):
    if not vis[i]:
        dfs(i,paths,dp,vis)
print(max(dp))

Submission status: Runtime Error

Solution code:
def dfs(node,paths,dp,vis):
    vis[node]=True
    for i in range(0, len(paths[node])):
        if not vis[paths[node][i]]:
            dfs(paths[node][i],paths,dp,vis)
        dp[node]=max(dp[node],1+dp[paths[node][i]])
n,m=map(int,input().split())
paths=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    paths[a].append(b)
dp,vis=[0]*(n+1),[False]*(n+1)
for i in range(1,n+1):
    if not vis[i]:
        dfs(i,paths,dp,vis)
print(max(dp))

Submission status: Runtime Error

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

dp = [-1]*n

def DFS(node):
    ma = -1
    for c_node in graph[node]:
        if dp[c_node]>=0:
            tmp = dp[c_node]
        else:
            tmp = DFS(c_node)
        if tmp > ma:
            ma = tmp
    dp[node] = ma+1
    return ma+1

sys.setrecursionlimit(2*n)

for i in range(n):
    if dp[i]>=0:
        continue
    DFS(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
import numpy as np

n, m = map(int, input().split())
XY = np.array([input().split() for _ in range(m)], np.int16)
dp = np.zeros((n, n), np.int16)
for x, y in XY:
    dp[x - 1][y - 1] = 1
for i in range(n):
    for j in range(n):
        dp[i][j] = max(dp[i][k] + dp[k][j] if dp[i][k] and dp[k][j] else dp[i][j] for k in range(n))
# print(dp)
print(np.max(dp))

Submission status: Runtime Error

Solution code:
import collections
N, M = map(int, input().split())
G = [set() for i in range(N)]
L = [-1]*N


def solve(x, r):
    if L[x] >= 0:
        return(L[x])
    res = 0
    for z in G[x]:
        if r[z]:
            r[z] = False
            res = max(res, solve(z, r) + 1)
        else:
            res = max(res, L[z]+1)
    L[x] = res
    return(res)


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

    G[x].add(y)

r = [True]*N

for i in range(N):
    # print(L)
    if r[i]:
        L[i] = solve(i, r)
print(max(L))

# print(L)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
G = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
DP = [None for i in range(n)]
def dp(i):
    if DP[i] != None:
        return DP[i]
    ret = 0
    for j in G[i]:
        ret = max(ret, dp(j)+1)
    DP[i] = ret
    return ret
print(max([dp(i) for i in range(n)]))

Submission status: Runtime Error

Solution code:
N, M = map(int,raw_input().split())
gra = [set() for n in range(N)]

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  start.discard(y-1)

def dfs(cur, par=-1) : 
  
  d = [0]
  for nxt in gra[cur] :
    if nxt == par : continue
    d.append(dfs(nxt, cur))

  return max(d) + int(par!=-1)

res = []
while start :
  res.append(dfs(start.pop()))

print max(res)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    # print(dpv)
    return ans
print(solve(edge))

Submission status: Runtime Error

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

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    # print(dpv)
    return ans
print(solve(edge))

Submission status: Runtime Error

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

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    print(dpv)
    return ans
print(solve(edge))

Submission status: Runtime Error

Solution code:
V, M = map(int,input().split())
L = [[] for _ in range(V+1)]
DP = [-1 for _ in range (V + 2)]
for _ in range(M):
    x,y = map(int,input().split())
    L[x-1].append(y-1)

def rec(v):
    if DP[v] != -1: return DP[v]
    ret = 0
    for x in L[v]:
        ret = max(ret,rec(x)+1)
    DP[v] = ret
    return DP[v]
ans = 0
for i in range(V):
    ans = max(ans, rec(i))
print(ans)

Submission status: Runtime Error

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

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    return ans
print(solve(edge))

Submission status: Runtime Error

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

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    return ans
print(solve(edge))

Submission status: Runtime Error

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

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(edge[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    return ans
print(solve(edge))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
p = [list(map(int,input().split())) for _ in range(M)]
dp = [-1]*N
ip = [[] for _ in range(N)]
for i in range(M):
  ip[p[i][1]-1].append(p[i][0]-1)

#閉路がないため同じ頂点は通らない
#i番目の頂点に到達するまでの最長手数をメモ化再帰で求める

def maxpath(i):
  if dp[i] != -1:
    return dp[i]
  a = 0
  for el in ip[i]:
    a = max(a,maxpath(el)+1)
  dp[i] = a
  return a
  
for i in range(N):
  maxpath(i)

print(max(dp))

Submission status: Runtime Error

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

#output
#便宜的にすべての点を-1しておく。
#dp[i]を頂点iから始まるpathで最長の長さとする。
#dp[i] = max(dp[v]+1)(vは頂点iから到達できる任意の頂点)

visited = [False] * N
memo = [0] * N

def dp(v):
    if visited[v]:
        return memo[v]
    else:
        res = 0
        for u in z[v]:
            res = max(res, dp(u)+1)
        memo[v] = res
        visited[v] = True
        return res
for i in range(N):
    dp(i)

print(max(memo))

Submission status: Runtime Error

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

#output
#便宜的にすべての点を-1しておく。
#dp[i]を頂点iから始まるpathで最長の長さとする。
#dp[i] = max(dp[v]+1)(vは頂点iから到達できる任意の頂点)

visited = [False] * N
memo = [0] * N
dp = [0] * N

def dp(v):
    if visited[v]:
        return memo[v]
    else:
        res = 0
        for u in z[v]:
            res = max(res, dp(u)+1)
        memo[v] = res
        visited[v] = True
        return res
for i in range(N):
    dp(i)

print(max(memo))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
      x,y=map(int,input().split())
      g[x-1].append(y-1)
memo = [0]*n
visited = [False]*n
# dp(i):i=0,1,..,n-1:頂点iを始点とした最長のパスを返す
def dp(v):
      if visited[v]:
            return memo[v]
      else:
            res=0
            for u in g[v]:
                  res=max(res,dp(u)+1)
            memo[v]=res
            visited[v]=True
            return res
for i in range(n):
      dp(i)
print(max(memo))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(m)]
# dp[j][k]:頂点iからはじまり頂点jで終わる最長のもの
dp=np.full((n,n),-1,np.int64)
for i in range(n):
      dp[i][i]=0
for _ in xy:
      x_=_[0]-1
      y_=_[1]-1
      dp[x_,y_]=1
      x0=np.where(dp[:,x_] >= 0)[0]
      y0=np.where(dp[y_,:] >= 0)[0]
      for j in x0:
            for k in y0:
                  dp[j,k]=max(dp[j,k],dp[j,x_]+dp[y_,k]+1)
print(np.max(dp))