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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    i = len(s)
    j = len(t)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:i -= 1
        elif dp[i][j] == dp[i][j-1]:j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)
#G
def G():
    def dfs(x):
        if dp[x] != None:
            return dp[x]
        if len(v[x]) == 0:
            dp[x] = 0
            return 0
        else:
            res = 0
            for y in v[x]:
                res = max(res,dfs(y)+1)
            dp[x] = res
            return dp[x]
    n,m = LI()
    dp = [None for i in range(n)]
    v = [[] for i in range(n)]
    for i in range(m):
        x,y = LI()
        v[x-1].append(y-1)
    for i in range(n):
        dfs(i)
    print(max(dp))

#H
def H():
    h,w = LI()
    s = SR(h)
    dp = [[0 for i in range(w)] for j in range(h)]
    dp[0][0] = 1
    for i in range(h-1):
        for j in range(w-1):
            if s[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
            if s[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
    for j in range(w-1):
        if s[h-1][j+1] == ".":
            dp[h-1][j+1] += dp[h-1][j]
            dp[h-1][j+1] %= mod
    for i in range(h-1):
        if s[i+1][w-1] == ".":
            dp[i+1][w-1] += dp[i][w-1]
            dp[i+1][w-1] %= mod
    print(dp[h-1][w-1])

#I
def J():
    n = I()
    p = list(map(float, input().split()))
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(n+1):
            dp[i+1][j] = p[i]*dp[i][j-1]+(1-p[i])*dp[i][j]

    ans = 0
    m = math.floor(n/2)
    for i in range(m+1,n+1):
        ans += dp[n][i]
    print(ans)

#J
def K():
    n = I()


#Solve
if __name__ == "__main__":
    G()

Submission status: Runtime Error

Solution code:
# coding: utf-8
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

@lru_cache(maxsize = None)
def f(v):
    if not arc[v]:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    arc[x - 1].append(y - 1)
print(max(f(v) for v in range(n)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

@lru_cache(maxsize = None)
def f(v):
    if len(arc[v]) == 0:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    arc[x].append(y)
print(max(f(v + 1) for v in range(n)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

@lru_cache(maxsize = None)
def f(v):
    if len(arc[v]) == 0:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    arc[x].append(y)
print(max(f(v + 1) for v in range(n)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from functools import lru_cache
sys.setrecursionlimit(10000)

import sys
input = sys.stdin.readline

@lru_cache(maxsize = None)
def f(v):
    if len(arc[v]) == 0:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    arc[x].append(y)
print(max(f(v + 1) for v in range(n)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(v):
    if len(arc[v]) == 0:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    arc[x].append(y)
print(max(f(v + 1) for v in range(n)))

Submission status: Runtime Error

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

mem = [-1]*n

def dfs(v):
  if mem[v] != -1:
    return mem[v]
  mem[v] = r = max(dfs(w) for w in g[v]) +1 if g[v] else 0
  return r
print(max(dfs(t) for t in range(n)))

Submission status: Runtime Error

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

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

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    res = 0
    for ne in ad[nodes]:
        option = rec(ne)+1
        if res < option:
            res = option
    dp[nodes] = res
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
dp=[[0]*m for i in range(m)]
#me=[[[]*m] for i in range(m)]
he=[[]*m for i in range(m)]
ta=[[]*m for i in range(m)]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    if dp[a-1][b-1]==0:
        dp[a-1][b-1]=1
        he[a-1]+=[b-1]
        ta[b-1]+=[a-1]
    a=a-1
    b=b-1
    for j in he[b]:
        dp[a][j]=max(dp[a][j],dp[b][j]+1)
        ans=max(ans,dp[a][j])
    for j in ta[a]:
        dp[j][b]=max(dp[j][b],dp[j][a]+1)
        ans=max(ans,dp[j][b])
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 11:58:20 2019
DP_G
@author: maezawa
"""
memo = [-1] * (10**5+100)

def rec(nx):
    if memo[nx] > -1:
        return memo[nx]
    depth = 0
    for edge in edges[nx]:
        nrec = rec(edge) + 1
        if nrec > depth:
            depth = nrec
    memo[nx] = depth
    return depth

n, m = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for i in range(m):
    x, y = list(map(int, input().split()))
    edges[x-1].append(y-1)
    
maxdepth = 0
for node in range(n):
    depth = rec(node)
    if maxdepth < depth:
        maxdepth = depth
        
print(maxdepth)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 11:58:20 2019
DP_G
@author: maezawa
"""
memo = [-1] * (10**5+1)

def rec(nx):
    if memo[nx] > -1:
        return memo[nx]
    depth = 0
    for edge in edges[nx]:
        nrec = rec(edge) + 1
        if nrec > depth:
            depth = nrec
    memo[nx] = depth
    return depth

n, m = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for i in range(m):
    x, y = list(map(int, input().split()))
    edges[x-1].append(y-1)
    
maxdepth = 0
for node in range(n):
    depth = rec(node)
    if maxdepth < depth:
        maxdepth = depth
        
print(maxdepth)

Submission status: Runtime Error

Solution code:
N, M = (int(i) for i in input().split()) 
 
outs = [[] for i in range(N)]
ins = [0] * N
 
for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1
 
q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)
 
last = [0] * N
while q != []:
    qn = q.poplef()
    for v in outs[qn]:
        ins[v] -= 1
        last[v] = max(last[v], last[qn] + 1)
        if ins[v] == 0:
            q.append(v)
 
print(max(last))

Submission status: Runtime Error

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop(0)
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    for v in outs[sq]:
        last[v] = max(last[v], last[sq] + 1)

print(max(last)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/6
Update on 2019/3/6
Solved on 2019/3/  
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np
import sys
sys.setrecursionlimit(10**6)


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype=np.longlong)


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype=np.longlong)


# def getIntLines(n): return [int(input()) for i in range(n)]
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros((n, m))
    dmp(mat)
    for i in range(n):
        mat[i] = getIntList()
    return mat


# def zeros2(n, m): return [zeros(m)]*n # obsoleted zeros((n, m))で代替


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def find(frm, to, path):
    dmp((frm, to, path), 'frm, to, path')
    if frm in path:
        return dmp(-1, 'not found')
    elif frm == to:
        return dmp(0, 'same')
    else:
        path = path + [frm]
        dmp(path)
        longest = -1
        for i in range(M):
            dmp(longest, 'longest')
            if edge[i, 0] == frm:
                if edge[i, 1] == to:
                    longest = max(longest, len(path))
                else:
                    longest = max(longest, find(edge[i, 1], to, path))
        return longest


def prob_G():  # Longest Path
    global N, M, edge
    N, M = getIntList()
    dmp((N, M), 'N, M')
    edge = getIntMat(M, 2)
    dmp(edge, 'edge')
    graph = zeros((N+1, N+1))
    dmp(graph, 'graph')
    for i in range(1, N+1):
        for j in range(1, N+1):
            graph[i][j] = find(i, j, [])
    dmp(graph, 'graph')
    return graph.max()


debug = False  # True False
ans = prob_G()
print(ans)
#for row in ans:
#    print(row)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/6
Update on 2019/3/6
Solved on 2019/3/  
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype=np.longlong)


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype=np.longlong)


# def getIntLines(n): return [int(input()) for i in range(n)]
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros((n, m))
    dmp(mat)
    for i in range(n):
        mat[i] = getIntList()
    return mat


# def zeros2(n, m): return [zeros(m)]*n # obsoleted zeros((n, m))で代替


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def find(frm, to, path):
    dmp((frm, to, path), 'frm, to, path')
    if frm in path:
        return dmp(-1, 'not found')
    elif frm == to:
        return dmp(0, 'same')
    else:
        path = path + [frm]
        dmp(path)
        longest = -1
        for i in range(M):
            dmp(longest, 'longest')
            if edge[i, 0] == frm:
                if edge[i, 1] == to:
                    longest = max(longest, len(path))
                else:
                    longest = max(longest, find(edge[i, 1], to, path))
        return longest


def prob_G():  # Longest Path
    global N, M, edge
    N, M = getIntList()
    dmp((N, M), 'N, M')
    edge = getIntMat(M, 2)
    dmp(edge, 'edge')
    graph = zeros((N+1, N+1))
    dmp(graph, 'graph')
    for i in range(1, N+1):
        for j in range(1, N+1):
            graph[i][j] = find(i, j, [])
    dmp(graph, 'graph')
    return graph.max()


debug = False  # True False
ans = prob_G()
print(ans)
#for row in ans:
#    print(row)

Submission status: Runtime Error

Solution code:
import collections

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]

L_minus = [[] for i in range(N)]
L_plus = [0 for i in range(N)]

dp = [0 for i in range(N)]

for i in range(M) :
    x,y = L[i]
    x -= 1
    y -= 1
    L_plus[y] += 1
    L_minus[x].append(y)

A = []

for i in range(N) :
    if L_plus[i] == 0 :
        A.append(i)

while A :
    x = A.collections.popleft()
    
    for y in L_minus[x] :
        L_plus[y] -= 1
        if L_plus[y] == 0 :
            A.append(y)
        dp[y] = max(dp[y], dp[x]+1)

ans = max(dp)

print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]

L_minus = [[] for i in range(N)]
L_plus = [0 for i in range(N)]

dp = [0 for i in range(N)]

for i in range(M) :
    x,y = L[i]
    x -= 1
    y -= 1
    L_plus[y] += 1
    L_minus[x].append(y)

A = []

for i in range(N) :
    if L_plus[i] == 0 :
        A.append(i)

while A :
    x = A.popleft()
    
    for y in L_minus[x] :
        L_plus[y] -= 1
        if L_plus[y] == 0 :
            A.append(y)
        dp[y] = max(dp[y], dp[x]+1)

ans = max(dp)

print(ans)

Submission status: Runtime Error

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

v = [-1] * (n + 1)
x = [[] for _ in range(n + 1)]

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

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

    rt = 0
    for node in x[i]:
        tmp = dfs(node) + 1
        if rt < tmp:
            rt = tmp

    #メモ化再帰
    v[i] = rt
    return rt

ans = 0

for k in range(1,n+1):
    tmp2 = dfs(k)

    if tmp2 > ans:
        ans = tmp2

print(ans)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for j in range(m)]

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

for a, b in X:
    E[a].append(b)

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

def dfs(i):
    if memo[i] != -1:
        return memo[i] + 1
    if not E[i]:
        return 0

    memo[i] = max(dfs(e) for e in E[i])
    return memo[i] + 1

print(max(dfs(i) for i in range(1, n+1)))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

global score

def dfs(graph, nd, d):
    global score
    max_depth = 0
    if score[nd] != -1:
        return score[nd] + 1
    if len(graph[nd]) == 0:
        score[nd] = 0
        return 1
    for adj in graph[nd]:
        max_depth = max(max_depth, dfs(graph, adj, d + 1))

    #if max_depth > score[nd]:
    score[nd] = max_depth
    return score[nd] + 1


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    global score
    score = {}
    for i in range(1, N+1):
        graph[i] = []
        score[i] = -1
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)

    for i in range(1, N + 1):
        dfs(graph, i, 0)
    max_score = 0
    for i in range(1, N + 1):
        max_score = max(max_score, score[i])
    print max_score
##        q = [i]
##        d = 0
##        while 1:
##            if len(q) <= 0:
##                score[i] = d
##                break
##            nd = q.pop()
##            if score[nd] != -1:
##                score[i] = d + score[nd]
##                break
##            for adj in graph[nd]:
##                if score[nd] + 1 > score[adj]:
##                    q.append(adj)
##                    score[adj] = score[nd] + 1
##                else:







if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

global score

def dfs(graph, nd, d):
    global score
    max_depth = 0
    if score[nd] != -1:
        return score[nd] + d
    if len(graph[nd]) == 0:
        score[nd] = 0
        return 1
    for adj in graph[nd]:
        max_depth = max(max_depth, dfs(graph, adj, d + 1)) - d

    if max_depth > score[nd]:
        score[nd] = max_depth
    return score[nd] + 1


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    global score
    score = {}
    for i in range(1, N+1):
        graph[i] = []
        score[i] = -1
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)

    max_score = 0
    for i in range(1, N + 1):
        max_score = max(max_score, dfs(graph, i, 0))
    print max_score
##        q = [i]
##        d = 0
##        while 1:
##            if len(q) <= 0:
##                score[i] = d
##                break
##            nd = q.pop()
##            if score[nd] != -1:
##                score[i] = d + score[nd]
##                break
##            for adj in graph[nd]:
##                if score[nd] + 1 > score[adj]:
##                    q.append(adj)
##                    score[adj] = score[nd] + 1
##                else:







if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

global score

def dfs(graph, nd, d):
    global score
    max_depth = 0
    if len(graph[nd]) == 0:
        return d
    for adj in graph[nd]:
        max_depth = max(max_depth, dfs(graph, adj, d + 1))

    if max_depth > score[nd]:
        score[nd] = max_depth
    return max_depth


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    global score
    score = {}
    for i in range(1, N+1):
        graph[i] = []
        score[i] = -1
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)

    max_score = 0
    for i in range(1, N + 1):
        if score[i] == -1:
            max_score = max(max_score, dfs(graph, i, 0))
        else:
            max_score = max(max_score, score[i])
    print max_score
##        q = [i]
##        d = 0
##        while 1:
##            if len(q) <= 0:
##                score[i] = d
##                break
##            nd = q.pop()
##            if score[nd] != -1:
##                score[i] = d + score[nd]
##                break
##            for adj in graph[nd]:
##                if score[nd] + 1 > score[adj]:
##                    q.append(adj)
##                    score[adj] = score[nd] + 1
##                else:







if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit as lim

lim(100001)

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()

g1 = ([] for i in xrange(n + 1))
g2 = ([] for i in xrange(n + 1))
ans1 = [0 for i in xrange(n + 1)]
ans2 = [0 for i in xrange(n + 1)]

for line in inp:
    u, v = map(int, line.strip().split())
    g1[u].append(v)
    g2[v].append(u)

def dfs1(u):
    if ans1[u] != 0: return ans1[u]
    ret = 0
    for v in g1[u]:
        if ans1[v] != 0: ret = max(ret, ans1[v])
        else: ret = max(ret, dfs1(v))
    ret += 1
    ans1[u] = ret
    return ans1[u]

def dfs2(u):
    if ans2[u] != 0: return ans2[u]
    ret = 0
    for v in g2[u]:
        if ans2[v] != 0: ret = max(ret, ans2[v])
        else: ret = max(ret, dfs2(v))
    ret += 1
    ans2[u] = ret
    return ans2[u]

ans = 0
for i in xrange(1, n + 1):
    if ans1[i] == 0: ans = max(ans, dfs1(i))
for i in xrange(1, n + 1):
    if ans2[i] == 0: ans = max(ans, dfs2(i))

print ans - 1

Submission status: Runtime Error

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

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


DP = [-1] * N
def From(i):
    if DP[i] != -1: return DP[i]
    else:
        maxLength = 0
        if not EdgeTo[i]:
            DP[i] = maxLength
        else:
            for node in EdgeTo[i]:
                maxLength = max(maxLength, 1 + From(node))
            DP[i] = maxLength
        return maxLength

Ans = 0
for i in range(N):
    Ans = max(Ans, From(i))
print(Ans)

Submission status: Runtime Error

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

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


DP = [-1] * N
def From(i):
    if DP[i] != -1: return DP[i]
    else:
        maxLength = 0
        if not EdgeTo[i]:
            DP[i] = maxLength
        else:
            for node in EdgeTo[i]:
                maxLength = max(maxLength, 1 + From(node))
        DP[i] = maxLength
        return maxLength

Ans = 0
for i in range(N):
    Ans = max(Ans, From(i))
print(Ans)

Submission status: Runtime Error

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

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


DP = [-1] * N
def From(i, EdgeTo, DP):
    if DP[i] >= 0: return DP[i]
    else:
        maxLength = 0
        if not EdgeTo[i]:
            DP[i] = maxLength
        else:
            for node in EdgeTo[i]:
                maxLength = max(maxLength, From(node, EdgeTo, DP))
            maxLength += 1
        DP[i] = maxLength
        return maxLength
Ans = 0
for i in range(N):
    Ans = max(Ans, From(i, EdgeTo, DP))
print(Ans)

Submission status: Runtime Error

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

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


DP = [0] * N
def From(i, EdgeTo, memo):
    if not EdgeTo[i]: return 0
    try:
        return memo[i]
    except KeyError:
        maxLength = 0
        for node in EdgeTo[i]:
            maxLength = max(maxLength, From(node, EdgeTo, memo))
        memo[i] = maxLength + 1
        return maxLength + 1

memo = {}
Ans = 0
for i in range(N):
    DP[i] = From(i, EdgeTo, memo)
    Ans = max(DP[i], Ans)
print(Ans)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit; setrecursionlimit(10**9)
N, M = map(int, input().split())
edge = {i:[] for i in range(1, M+1)}
starts = set(i for i in range(1, N+1))
for _ in range(M):
    x, y = map(int, input().split())
    edge[x].append(y)
    starts -= {y}

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

def rec(e):
    if memo[e] != -1:
        return memo[e]
    ret = 0
    for f in edge[e]:
        ret = max(ret, rec(f) + 1)
    memo[e] = ret
    return ret

max_d = 0
for s in starts:
    max_d = max(max_d, rec(s))
print(max_d)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
edge = {}
starts = set(i for i in range(1, N+1))
for _ in range(M):
    x, y = map(int, input().split())
    if x not in edge:
        edge[x] = [y]
    else:
        edge[x].append(y)
    starts -= {y}

def rec(d, e, dp):
    dp[e] = max(dp[e], d)
    if e not in edge:
        return 0
    for f in edge[e]:
        rec(d+1, f, dp)
    return max(dp)

depth = []
for s in starts:
    depth.append(rec(0, s, [0]*(N+1)))
print(max(depth))

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

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


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

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


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N)))

Submission status: Runtime Error

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

N,M=map(int, sys.stdin.readline()..split())

nl=[ [] for i in range(N+1) ] 
f=[ 0 for i in range(N+1) ]
dp=[ 0 for i in range(N+1) ]

for i in range(M):
	x,y=map(int, sys.stdin.readline()..split())
	nl[x].append(y)
	f[y]=1

start=[]
for i in range(1,N+1):
	if f[i]==0:
		start.append(i)


def dfs(v):
	for u in nl[v]:
		dp[u]=max( dp[u], dp[v]+1)
		dfs(u)


for s in start:
	dfs(s)

print max(dp)

Submission status: Runtime Error

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

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

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(1, n+1):
    longest_path(u)

print(max(dp))

Submission status: Runtime Error

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

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

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(n+1):
    longest_path(u)

print(max(dp))

Submission status: Runtime Error

Solution code:
 # -*- coding: utf-8 -*-
"""
Created on Sat Jan 19 16:05:26 2019
DP_G
@author: maezawa
"""

n, m = list(map(int, input().split()))
v = [-1]*(n+1)
adj = [[] for _ in range(n+1)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    adj[i].append(j)
    
def dfs(vi):
    if v[vi] != -1:
        return v[vi]
    res = 0
    for nb in adj[vi]:
        res0 = dfs(nb) +1
        if res < res0:
            res = res0
    v[vi] = res
    return res

ans = 0
for node in range(1, n+1):
    current = dfs(node)
    if current > ans:
        ans = current
print(ans)

Submission status: Runtime Error

Solution code:
def inpl(): map(int, input().split())
N, M = inpl()
DP = [0]*(N+1)
for _ in range(M):
    x, y = inpl()
    DP[y] = max(DP[y], DP[x]+1)
print(max(DP))