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:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


def ifvalid(i):
    if i < 0:
        return False
    return True





def solve():
    n,m=sep()
    g=[[] for i in range(n+5)]
    for i in range(m):
        a,b=sep()
        a-=1
        b-=1
        g[a].append(b)
    dp=[-1 for i in range(n+5)]

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

    for v in range(n):
        if dp[v]==-1:
            dfs(v)

    print(max(dp))


solve()

Submission status: Runtime Error

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


def ifvalid(i):
    if i < 0:
        return False
    return True





def solve():
    n,m=sep()
    g=[[] for i in range(n+5)]
    for i in range(m):
        a,b=sep()
        a-=1
        b-=1
        g[a].append(b)
    dp=[-1 for i in range(n+5)]

    def dfs(v):
        if g[v] == []:
            dp[v] = 0
        for c in g[v]:
            dfs(c)
            dp[v] = max(dp[v], 1 + dp[c])

    for v in range(n):
        if dp[v]==-1:
            dfs(v)

    print(max(dp))


solve()

Submission status: Runtime Error

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


def ifvalid(i):
    if i < 0:
        return False
    return True







def solve():
    n,m=sep()
    g=[[] for i in range(n+5)]
    for i in range(m):
        a,b=sep()
        a-=1
        b-=1
        g[a].append(b)
    dp=[-1 for i in range(n+5)]

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

    for v in range(n):
        dfs(v)
    
    print(max(dp))


solve()

Submission status: Runtime Error

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

# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

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

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


def dp(i):
    if memo[i] == -1:
        ret = 0
        for j in range(m + 1)[1:]:
            if x[j] == i:
                tmp = dp(y[j]) + 1
                ret = max(tmp, ret)
        memo[i] = ret
        return ret
    else:
        return memo[i]


ans = -1
for i in range(n + 1)[1:]:
    tmp = dp(i)
    ans = max(tmp, ans)

print("{}".format(ans))

Submission status: Runtime Error

Solution code:
def f(x, children, ans):
    if ans[x] >= 0:
        return ans[x]
    else:
        fans = 0
        for y in children[x]:
            fans = max(fans, f(y, children, ans) + 1)

        ans[x] = fans

        return fans

    return 0

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

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

for i in range(M):
    x, y = [int(x) for x in input().split()]
    children[x].append(y)

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

longest = 0

for x in range(1, N + 1):
    longest = max(longest, f(x, children, ans))

print(longest)

Submission status: Runtime Error

Solution code:
def f(x, children, ans):
    if ans[x] >= 0:
        return ans[x]
    else:
        fans = 0
        for y in children[x]:
            fans = max(fans, f(y, children, ans) + 1)
        ans[x] = fans

        return fans

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

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

for i in range(M):
    x, y = [int(x) for x in input().split()]
    children[x].append(y)

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

longest = 0

for x in range(1, N + 1):
    longest = max(longest, f(x, children, ans))

print(longest)

Submission status: Runtime Error

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

def dfs(node):
	ans=0
	if(vis[node]):
		return dp[node]
	vis[node]=1
	for child in graph[node]:
		ans=max(ans,1+dfs(child))
	dp[node]=ans
	return ans
vis=[0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
ans=0
for i in range(1,n+1):
	if(not vis[n]):
		a=dfs(i)
		ans=max(ans,a)
print(ans)
print(dp)

Submission status: Runtime Error

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

def dfs(node):
	ans=0
	if(vis[node]):
		return dp[node]
	vis[node]=1
	for child in graph[node]:
		ans=max(ans,1+dfs(child))
	dp[node]=ans
	return ans
vis=[0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
ans=float('-inf')
for i in range(1,n+1):
    dp[i]=dfs(i)
print(max(dp))

Submission status: Runtime Error

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

def dfs(node):
	ans=0
	if(vis[node]):
		return dp[node]
	vis[node]=1
	for child in graph[node]:
		ans=max(ans,1+dfs(child))
	dp[node]=ans
	return ans
vis=[0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
ans=float('-inf')
for i in range(1,n+1):
	if(not vis[n]):
		a=dfs(i)
		ans=max(ans,a)
print(ans)

Submission status: Runtime Error

Solution code:
path=[]
def solve(r,g,n):
    if len(g[r])==0:
        path.append(n)
        return
    for i in g[r]:
        solve(i,g,n+1)

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)
for i in range(n):
    solve(i,g,0)
print(max(path))

Submission status: Runtime Error

Solution code:
def solve(r,g,n):
    if len(g[r])==0:
        return n
    mx=0
    for i in g[r]:
        mx=max(mx,solve(i,g,n+1))
    return mx

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)
mx=0
for i in range(n):
    mx=max(mx,solve(i,g,0))
print(mx)

Submission status: Runtime Error

Solution code:
path=[0]*100001
visited=[0]*100001
def solve(r,g):
    visited[r]=True
    for i in g[r]:
        path[i]=max(path[i],path[r]+1)
        solve(i,g)

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)
for i in range(n):
    if not visited[i]:
        solve(i,g)
print(max(path[:n]))

Submission status: Runtime Error

Solution code:
def get(i, value, vis):
    if vis[i]:
        return value[i]
    vis[i] = True
    ans = 0
    for j in adj[i]:
        ans = max(ans, 1+get(j, value, vis))
    value[i] = ans
    return ans


n, m = map(int, input().split())
adj = {}
for i in range(n):
    adj[i] = []
for i in range(m):
    x, y = map(int,input().split())
    adj[x-1].append(y-1)
vis = [False for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    value[i] = get(i, value, vis)
x = 0
for i in value:
    x = max(x, i)
print(x)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N , M = map(int,input().split())
X = [list(map(int,input().split())) for i in range(M)]
Y = [[] for i in range(N+1)]
for i in range(M):
  Y[X[i][0]].append(X[i][1])
@lru_cache(maxsize = None)
def f(x):
  global Y
  if len(Y[x]) == 0:
    return(0)
  else:
    return max([f(j) for j in Y[x]]) + 1
M = max([f(i) for i in range(N+1)])
print(M)

Submission status: Runtime Error

Solution code:
N , M = map(int,input().split())
X = [list(map(int,input().split())) for i in range(M)]
Y = [[] for i in range(N+1)]
for i in range(M):
  Y[X[i][0]].append(X[i][1])
def f(x):
  global Y
  if len(Y[x]) == 0:
    return(0)
  else:
    return max([f(j) for j in Y[x]]) + 1
M = max([f(i) for i in range(N+1)])
print(M)

Submission status: Runtime Error

Solution code:
N , M = map(int,input().split())
X = [list(map(int,input().split())) for i in range(M)]
Y = [[] for i in range(N)]
for i in range(M):
  Y[X[i][0] - 1].append(X[i][1] - 1)
def f(x):
  global Y
  if len(Y[x]) == 0:
    return(0)
  else:
    return max([f(j) for j in Y[x]]) + 1
M = max([f(i) for i in range(N)])
print(M)

Submission status: Runtime Error

Solution code:
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)
dp = [0]*N
def f(v):
    if dp[v] != 0:
        return dp[v]
    res = 0
    for i in edge[v]:
        res = max(res, f(i)+1)
    dp[v] = res
    return res
for i in range(N):
    f(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
def findLongest(n):
    if n not in graph:
        dp[n]=0
        return dp[n]
    if n in dp:
        return dp[n]
    dp[n] = 0
    for to in graph[n]:
        dp[n] = max(dp[n],1+findLongest(to))
    return dp[n]


n,m = [int(x) for x in input().split()]
graph = {}
for i in range(m):
    s,d = [int(x) for x in input().split()]
    if s not in graph:
        graph[s] = []
    graph[s].append(d)

dp = {}

for node in range(1,n+1):
    findLongest(node)
ans = 0
for i in range(1,n+1):
    ans = max(ans,dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
import collections

def dfs(v):
    if cache.get(v):
        return cache[v]
    path=0
    for adj in g[v]:
        path=max(path,1+dfs(adj))
    cache[v]=path
    return path


n,m=map(int,input().split())
g=collections.defaultdict(list)
cache={}
path=0
for _ in range(m):
    u,v=map(int,input().split())
    g[u].append(v)
for v in range(1,n+1):
    path=max(path,dfs(v))
print(path)

Submission status: Runtime Error

Solution code:
def main():
    n, m = [int(x) for x in input().split()]
    global dp
    dp = [-1]*n
    grafo = [[] for _ in range(n)]

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

        grafo[x].append(y)

    resp = 0
    for u in range(n):
        resp = max(dfs(u, grafo), resp)

    print(resp)
        

def dfs(u, grafo):
    global dp

    if len(grafo[u]) == 0:
        dp[u] = 0
        return dp[u]

    if dp[u] != -1:
        return dp[u]


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

    return dp[u]
        
main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
flag = [0]*(N+1)
dist = [0]*(N+1)
def distance(i):#地点iから終点までの最長距離
    if flag[i] == 1:
        return dist[i]
    
    if road[i] == []:#行き先がない
        return 0
    else:#行き先がある
        long_dist = 0
        tmp = 0
        for dirct in road[i]:
            tmp = 1 + distance(dirct)
            long_dist = max(long_dist,tmp)
        flag[i]=1
        dist[i] = long_dist
        return long_dist

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
flag = [0]*(N+1)
dist = [0]*(N+1)
def distance(i):#地点iから終点までの最長距離
    if flag[i] == 1:
        return dist[i]
    
    if road[i] == []:#行き先がない
        return 0
    else:#行き先がある
        long_dist = 0
        for dirct in road[i]:
            tmp = 1 + distance(dirct)
            long_dist = max(long_dist,tmp)
        flag[i]=1
        dist[i] = long_dist
        return long_dist

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
flag = [0]*(N+1)
dist = [0]*(N+1)
def distance(i):#地点iから終点までの最長距離
    if flag[i] == 1:
        return dist[i]
    
    if road[i] == []:#行き先がない
        return 0
    else:#行き先がある
        long_dist = 0
        for dirct in road[i]:
            tmp = 1 + distance(dirct)
            long_dist = max(long_dist,tmp)
    flag[i]=1
    dist[i] = long_dist
    return long_dist

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
 
G = [[] for _ in range(N + 1)]
for i in range(M):
    x, y = map(int, input().split())
    G[x] += [y]
# print(G)
 
dp = [-1] * (N + 1)
 
 
def func(n):
    if dp[n] != -1:
        return dp[n]
    cnt = 0
	# 先にノードが存在する場合
	# ノードが存在しない場合は、cnt=0のままforをすっ飛ばす
    for m in G[n]:
        cnt = max(cnt, func(m) + 1)
    dp[n] = cnt
    return cnt
 
 
for i in range(1, N + 1):
    func(i)
 
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
 
G = [[] for _ in range(N + 1)]
for i in range(M):
    x, y = map(int, input().split())
    G[x] += [y]
# print(G)
 
dp = [-1] * (N + 1)
 
 
def func(n):
    if dp[n] != -1:
        return dp[n]
    cnt = 0
	# 先にノードが存在する場合
	# ノードが存在しない場合は、cnt=0のままforをすっ飛ばす
    for m in G[n]:
        cnt = max(cnt, func(m) + 1)
    dp[n] = cnt
    return cnt
 
 
for i in range(1, N + 1):
    func(i)
 # print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
edge=[[] for j in range(N+1)]
x = [0] * M
y = [0] * M

#N,M=4,5
#x=[1, 1, 3, 2, 3]
#y=[2, 3, 2, 4, 4]
#edge=[[], [2, 3], [4], [2, 4], []]  

for i in range(M):
    x[i], y[i] = map(int, input().split())
    edge[x[i]].append(y[i])
dp=[-1]*(N+1)
def f(x):
    if dp[x]!=-1:
        return dp[x]
    num=0
   
    for i in edge[x]:
        num=max(num,f(i)+1)
    
    dp[x]=num
    return dp[x]
m=0
for i in range(1,N+1):
    m=max(m,f(i))
print(m)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
edge=[[] for j in range(N+1)]
x = [0] * M
y = [0] * M

#N,M=4,5
#x=[1, 1, 3, 2, 3]
#y=[2, 3, 2, 4, 4]
#edge=[[], [2, 3], [4], [2, 4], []]  

for i in range(M):
    x[i], y[i] = map(int, input().split())
    edge[x[i]].append(y[i])
dp=[-1]*(N+1)
def f(x):
    if dp[x]!=-1:
        return dp[x]
    num=0
   
    for i in edge[x]:
        num=max(num,f(i)+1)
    
    dp[x]=num
    return dp[x]
for i in range(1,N+1):
    i,f(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
edge=[[] for j in range(N+1)]
x = [0] * M
y = [0] * M

#N,M=4,5
#x=[1, 1, 3, 2, 3]
#y=[2, 3, 2, 4, 4]
#edge=[[], [2, 3], [4], [2, 4], []]  

for i in range(M):
    x[i], y[i] = map(int, input().split())
    edge[x[i]].append(y[i])
dp=[0]*(N+1)
def f(x):
    if edge[x]==[]:
        return dp[x]
    #num=0
    if edge[x]!=[]:
        num=0
        for i in edge[x]:
            num=max(num,f(i)+1)
        #del edge[x][0]
        dp[x]=max(dp[x],num)
        dp[x]=num
        return dp[x]
for i in range(N):
    f(i+1)
print(max(dp))

Submission status: Runtime Error

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

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

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



def calc(x):
    if len(p[x])==0:
        return 0
    return max([calc(i) for i in p[x]])+1

m=0
for i in range(n):
    j=calc(i)
    if m<j:
        m=j
print(m)

Submission status: Runtime Error

Solution code:
from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
# memo =  [[0] * N for _ in range(N)] #矢印が入ってきている数字を-1でフラグ立てる
dp = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append((x, y))
    memo[y][x] = 1

q = deque()

for i in range(N):
    q.append(G[i])
    while q:
        moves = q.pop()
        for move in moves:
            x, y = move
            dp[y] = max(dp[y], dp[x]+1)
            # memo[y][x] = 0
            q.append(G[y])

print(max(dp))

Submission status: Runtime Error

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

G = [[] for _ in range(N + 1)]
for i in range(M):
    x, y = map(int, input().split())
    G[x] += [y]
# print(G)

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


def func(n):
    if dp[n] != -1:
        return dp[n]
    cnt = 0
	# 先にノードが存在する場合
	# ノードが存在しない場合は、cnt=0のままforをすっ飛ばす
    for m in G[n]:
        cnt = max(cnt, func(m) + 1)
    dp[n] = cnt
    return cnt


for i in range(1, N + 1):
    func(i)

# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
sys.setrecursionlimit(10**9)

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

paths = [[] for i in range(N)]
longest_paths = [-1 for i in range(N)]

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

def get_longest(node):
    if longest_paths[node] != -1:
        return longest_paths[node]
    if paths[node] == []:
        longest_paths[node] = 0
        return 0
    else:
        result = max([get_longest(nd) for nd in paths[node]]) + 1
        longest_paths[node] = result
        return result

print(max([get_longest(i) for i in range(N)]))