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:
from sys import setrecursionlimit
setrecursionlimit(10 ** 5 + 10)

from functools import lru_cache

N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

@lru_cache(maxsize=None)
def dp(p):
    return max((1 + dp(c) for c in E[p]), default=0)

print(max(dp(p) for p in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 5 + 10)

from functools import lru_cache

N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

@lru_cache
def dp(p):
    return max((1 + dp(c) for c in E[p]), default=0)

print(max(dp(p) for p in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

memo = {}
def dp(p):
    if p not in memo:
        memo[p] = max((1 + dp(c) for c in E[p]), default=0)
    return memo[p]

print(max(dp(p) for p in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 5 + 10)

N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

memo = {}
def dp(p):
    return memo.get(p, max((1 + dp(c) for c in E[p]), default=0))

print(max(dp(p) for p in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 5 + 10)

N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

memo = {}
def dp(p):
    memo[p] = max((1 + memo.get(c, dp(c)) for c in E[p]), default=0)
    return memo[p]

print(max(dp(p) for p in range(1, N + 1)))

Submission status: Runtime Error

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

G=[[] for _ in range(N+1)]  #G[0]はダミー
for edge in range(M):
    x,y=map(int,input().split())
    G[x].append(y)

DP=[-1]*(N+1)   #DP[0]はダミー

def rec(now):
    global G
    global DP

    if DP[now]!=-1:
        return DP[now]

    else:
        res=0
        for next in G[now]:
            res=max(res,rec(next)+1)
        DP[now]=res
        return DP[now]  #resは不可

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

print(ans)

Submission status: Runtime Error

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

G=[[] for _ in range(N+1)]  #G[0]はダミー
for edge in range(M):
    x,y=map(int,input().split())
    G[x].append(y)

DP=[-1]*(N+1)   #DP[0]はダミー

def rec(now):
    global G

    if DP[now]!=-1:
        return DP[now]

    else:
        res=0
        for next in G[now]:
            res=max(res,rec(next)+1)
        DP[now]=res
        return DP[now]

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

print(ans)

Submission status: Runtime Error

Solution code:
import collections
n,m = map(int,input().split())
d = {}
indegree = [0]*n
for _ in range(m):
    x,y = map(int,input().split())
    d[x-1] = d.get(x-1,[]) + [y-1]
    indegree[y-1] += 1
dp = [0]
q = collections.deque([i for i in range(n) if indegree[i] == 0])
while q:
    node = q.popleft()
    for nei in d.get(node,[]):
        indegree[nei] -= 1
        dp[nei] = max(dp[nei],dp[node]+1)
        if indegree[nei] == 0:
            q.append(nei)
return max(dp)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
d = {}
for _ in range(m):
    x,y = map(int,input().split())
    d[x-1] = d.get(x-1,[]) + [y-1]
memo = {}
def dp(i):
    if i not in d:
        return 0
    if i not in memo:
        memo[i] = 0
        for nei in d.get(i,[]):
            memo[i] = max(memo[i],dp(nei)+1)
    return memo[i]
ans = 0
for i in range(n):
    ans = max(ans,dp(i))
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
d = {}
for _ in range(m):
    x,y = map(int,input().split())
    d[x-1] = d.get(x-1,[]) + [y-1]
memo = {}
def dp(i):
    if i not in d:
        return 0
    if i not in memo:
        memo[i] = 0
        for nei in d[i]:
            memo[i] = max(memo[i],dp(nei)+1)
    return memo[i]
ans = 0
for i in range(n):
    ans = max(ans,dp(i))
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

from collections import defaultdict

# from typing import Dict, List, Optional, Set, Tuple

# def dfs(vertex: int, succ: Dict[int, List[int]], dp: Dict[int, int]) -> int:
def dfs(vertex, succ, dp):
    if vertex in dp:
        return dp[vertex]
    length = 0
    for s in succ[vertex]:
        length = max(length, 1 + dfs(s, succ, dp))
    dp[vertex] = length
    return length


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, _nb_edges) -> int:
    succ = defaultdict(list)
    for s, d in values:
        succ[s].append(d)
    # all edges have a 0 length path starting at the edge
    dp = defaultdict(lambda: -1)
    for vertex in frozenset(succ.keys()):
        if vertex in dp:
            dp[vertex] = max(dp[vertex], dfs(vertex, succ, dp))
        else:
            dp[vertex] = dfs(vertex, succ, dp)
    return max(dp.values())


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


if __name__ == "__main__":
    do_job()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
    succ = defaultdict(set)
    for s, d in values:
        succ[s].add(d)
    # all edges have a 0 length path starting at the edge
    dp = [True] * nb_vertices
    max_length_path = 0
    for length in range(1, nb_edges + 1):
        prev = dp.copy()
        dp = [False] * nb_vertices
        # vertices are indexed from 1
        for vertex in range(1, nb_vertices + 1):
            for d in succ[vertex]:
                if prev[d - 1]:
                    dp[vertex - 1] = True
                    max_length_path = length
                    break
    return max_length_path


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log(log_file: Optional[str] = None) -> None:
    "Configure the log output"
    log_formatter = logging.Formatter(
        "%(asctime)s - %(filename)s:%(lineno)d - " "%(levelname)s - %(message)s"
    )
    if log_file:
        handler = logging.FileHandler(filename=log_file)
    else:
        handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter

def solve(num):
    #base case:
    if(dic[num]==0):
        return 0

    mx = 0
    for el in dic[num]:
        if(dp[el]==-1):
            temp1 = solve(el)
            mx = max(mx, 1 + temp1)
            dp[el] = temp1
        else:
            mx = max(mx, 1 + dp[el])

    return mx

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

for _ in range(m):
    xtemp, ytemp = map(int, input().split())
    if(xtemp not in dic):
        dic[xtemp] = []
        dic[xtemp].append(ytemp)
    else:
        dic[xtemp].append(ytemp)
#init dp:
dp = [-1]*(n+1)

mxGl = 0
keys = list(dic.keys())
for node in keys:
    if(dp[node]==-1):
        temp = solve(node)
        dp[node] = temp
        mxGl = max(mxGl, temp)
    else:
        mxGl = max(mxGl, dp[node])
print(mxGl)

Submission status: Runtime Error

Solution code:
node_num, path_num = map(int, input().split())
graph = [[] for _ in range(node_num)]

for i in range(path_num):
    from_node, to_node = map(int, input().split())
    graph[from_node - 1].append(to_node - 1)
#print(graph)

#dp[i]はiを始点としたときの経路長の最大値
dp = [-1] * node_num

def rec(v):
    #print(v)
    #print(dp)
    if dp[v] > -1:
        return dp[v]
    else:
        dp[v] = 0
        for nv in graph[v]:
            dp[v] = max(dp[v], rec(nv) + 1)
        return dp[v]

ans = 0
for node in range(node_num):
    ans = max(ans, rec(node))
print(ans)

Submission status: Runtime Error

Solution code:
def dfs(root,adj):
    if dp[root]!=-1: 
        return dp[root]
    if adj.get(root)!=None:
        res=0
        for i in adj[root]:
            res=max(res,dfs(i,adj)+1)
        dp[root]=res
        return res
    dp[root]=0
    return 0

n,m=map(int,input().split())
adj={}
for i in range(m):
    a,b=map(int,input().split())
    if adj.get(a)!=None:
        adj[a].append(b)
    else:
        adj[a]=[b]
maxx=0
dp=[-1 for i in range(110000)]
for i in adj.keys():
    maxx=max(maxx,dfs(i,adj))
print(maxx)

Submission status: Runtime Error

Solution code:
def dfs(root,adj):
    if adj.get(root)!=None:
        if dp[root]!=-1: 
            return dp[root]
        res=0
        for i in adj[root]:
            res=max(res,dfs(i,adj)+1)
        dp[root]=res
        return res
    return 0

n,m=map(int,input().split())
adj={}
for i in range(m):
    a,b=map(int,input().split())
    if adj.get(a)!=None:
        adj[a].append(b)
    else:
        adj[a]=[b]
maxx=0
dp=[-1 for i in range(n+1)]
for i in adj.keys():
    maxx=max(maxx,dfs(i,adj))
print(maxx)

Submission status: Runtime Error

Solution code:
from collections import deque

class Graph:
    def __init__(self,size):
        self.graph = [ {
            'idx' : i,
            'to': [],
            'inputs' : 0,
        } for i in range(size) ]

    def add_node(self,start,end):
        self.graph[start]['to'].append(end)
        self.graph[end]['inputs'] += 1

    def topological_sort(self):
        inputs = [i['inputs'] for i in self.graph]
        no_inputs = deque([ i['idx'] for i in self.graph if i['inputs'] == 0])
        ans = []
        while no_inputs:
            vertex1 = no_inputs.popleft()
            ans.append(vertex1)
            for vertex2 in self.graph[vertex1]['to']:
                inputs[vertex2] -= 1
                if inputs[vertex2] == 0:
                    no_inputs.append(vertex2)
        return ans

def main():
    n,m = map(int, input().split())
    G = Graph(m)
    for _ in range(n):
        x,y = map(int, input().split())
        G.add_node(x-1,y-1)
    tp = G.topological_sort()
    dist = [0] * n
    for v in tp[::-1]:
        for t in G.graph[v]['to']:
            if dist[v] <= dist[t]:
                dist[v] = dist[t] + 1
    print(max(dist))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


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


n, m = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x].add(y)

dp = [-1] * (n + 1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


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


n, m = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x].add(y)

dp = [-1] * (n + 1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
    print(v, dp)

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


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


n, m = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x].add(y)

dp = [-1] * (n + 1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
    print(v, dp)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
v=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  v[a-1].append(b-1)

memo=[-1]*n
def dp(x):
  if memo[x]!=-1:return memo[x]
  r=0
  for i in v[x]:
    r=max(r,dp(i)+1)
  memo[x]=r
  return r
print(max(dp(i) for i in range(n)))

Submission status: Runtime Error

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


def memoize(f):
    memo = dict()

    def memoized(*args):
        if args in memo.keys():
            return memo[args]
        else:
            memo[args] = f(*args)
            return memo[args]
    return memoized

@memoize
def longest_path(v):
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    return retval


ans = 0
for i in range(n):
    ans = max(ans, longest_path(i))
print(ans)

Submission status: Runtime Error

Solution code:
def solve(n, graph):
    def dfs(u):
        if vis[u]:
            return dist[u]
        vis[u] = True
        best = 0
        for v in graph[u]:
             best = max(best, dfs(v) + 1)
        dist[u] = best
        return dist[u]
    
    dist = [0] * n
    vis = [False] * n
    best = 0
    for i in range(n):
        best = max(best, dfs(i))
    return best


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    graph = [[] for _ in range(n)]
 
    for i in range(m):
        x, y = inp()
        x, y = x-1, y-1
        graph[x].append(y)
 
    print(solve(n, graph))
 
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def solve(n, graph, root):
    def dfs(u):
        if len(graph[u]) == 0:
            return 0
        if dist[u] != 0:
            return dist[u]
        for v in graph[u]:
            dist[u] = max(dist[u], dfs(v))
        dist[u] += 1
        return dist[u]
    
    dist = [0] * n
    for i in range(n):
        if root[i]:
            dfs(i)
    return max(dist)


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    graph = [[] for _ in range(n)]
    root = [True] * n
 
    for i in range(m):
        x, y = inp()
        x, y = x-1, y-1
        graph[x].append(y)
        root[y] = False
 
    print(solve(n, graph, root))
 
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

dp = [-1 for i in range(N)] #node[i]からの最長経路長を記す -1で未決定を示す

def memo(i):
    if dp[i] != -1:
        return dp[i]
    a=0
    for j in to[i]:
        a=max(a, memo(j)+1)
    dp[i] = a
    return a
    
lp = 0
for i in range(N):
    lp = max(lp,memo(i))
print(lp)

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split(" ")))
d={}
f=[0]*n
def dfs(i,v):
	v[i]=1
	for j in d[i]:
		if(v[j]==0):
			dfs(j,v)
		f[i]=max(f[i],f[j]+1)


for i in range(n):
	d[i]=[]
	# f[i]=0
for i in range(m):
	x,y=list(map(int,input().split(" ")))
	d[x-1].append(y-1)
v=[0]*n
for i in range(n):
	if(v[i]==0):
		dfs(i,v)
		# print(v)
# print(f)
print(max(f))

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split(" ")))
d={}
f=[0]*n
def dfs(i):
	v[i]=1
	for j in d[i]:
		if(v[j]==0):
			dfs(j)
		f[i]=max(f[i],f[j]+1)


for i in range(n):
	d[i]=[]
	# f[i]=0
for i in range(m):
	x,y=list(map(int,input().split(" ")))
	d[x-1].append(y-1)
v=[0]*n
for i in range(n):
	if(v[i]==0):
		dfs(i)
		# print(v)
print(max(f))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <functional>
#include <map>
#include <set>
#include <cmath>
using namespace std;

#define INT_MAX 2147483647
#define ll long long

ll max(ll a, ll b) { return (a < b) ? b : a; }


vector<int> lp;

void top_sort_util(int i, unordered_map<int, vector<int>>& edges, vector<bool>& visited, list<int>& stack) {
    visited[i] = true;

    for (int n : edges[i]) {
        if (!visited[n]) {
            top_sort_util(n, edges, visited, stack);
        }
    }
    stack.push_back(i);
}

list<int> top_sort(unordered_map<int, vector<int>>& edges, int n) {
    vector<bool> visited(n + 1);
    list<int> stack;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            top_sort_util(i, edges, visited, stack);
        }
    }
    return stack;
}

void solve(unordered_map<int, vector<int>>& edges, int n) {
    list<int> stack = top_sort(edges, n);
    lp[stack.back()] = 0;

    for (auto it = stack.rbegin(); it != stack.rend(); it++) {
        int u = *it;

        if (lp[u] != -1) {
            for (int nei : edges[u]) {
                lp[nei] = max(lp[nei], lp[u] + 1);
            }
        }
    }

    int best = -1;
    for (int dist : lp) {
        best = max(dist, best);
    }

    cout << best << endl;
}

// DP !!
int main() {
    int n, m;
    cin >> n >> m;

    unordered_map<int,vector<int>> edges;
    lp.resize(n + 1, -1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
    }

    solve(edges, n);
    
    return 0;
}

Submission status: Runtime Error

Solution code:
def solve(g):
    dp = [-1]*len(g)
    def _solve(f):
        if dp[f] == -1:
            dp[f] = 0
            for c in g[f]:
                dp[f] = max(dp[f], 1 + _solve(c))
        return dp[f]
    for f in range(len(g)):
        _solve(f)
    # print(dp)
    return max(dp)

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    f, t = map(int, input().split())
    g[f-1].append(t-1)

print(solve(g))

Submission status: Runtime Error

Solution code:
def solve(g):
    dp = [-1]*len(g)
    def _solve(f):
        if dp[f] == -1:
            sol = 0
            for c in g[f]:
                sol = max(sol, 1 + _solve(c))
            dp[f] = sol
        return dp[f]
    for f in range(len(g)):
        _solve(f)
    return max(dp)

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    f, t = map(int, input().split())
    g[f-1].append(t-1)

print(solve(g))

Submission status: Runtime Error

Solution code:
def solve(g):
    dp = [-1]*len(g)
    def _solve(f):
        if dp[f] == -1:
            for c in g[f]:
                dp[f] = max(dp[f], 1 + _solve(c))
            dp[f] = max(dp[f], 0)
        return dp[f]
    for f in range(len(g)):
        _solve(f)
    # print(dp)
    return max(dp)

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    f, t = map(int, input().split())
    g[f-1].append(t-1)

print(solve(g))

Submission status: Runtime Error

Solution code:
from collections import deque

N,M = [int(v) for v in input().split()]
ad_list = [[] for _ in range (N+1)]
ad_num = [0 for _ in range(N)]
topo = []

for _ in range(M):
    l,r = [int(v) for v in input().split()]
    ad_list[l].append(r)
    ad_num[r-1] += 1

for i in range(1,N+1):
    if ad_num[i-1] == 0:
        topo.append(i)
queue = deque(topo[:])
while queue:
    n1 = queue.popleft()
    for n2 in ad_list[n1]:
        ad_num[n2-1] -= 1
        if ad_num[n2-1] == 0:
            topo.append(n2)
            queue.append(n2)

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

ans = 0
def dfs(node,cnt=0):
    global ans
    ans = max(ans,cnt)
    if visited[node]: return 0
    visited[node] = True
    for n in ad_list[node]:
        dfs(n,cnt+1)

for n in topo:
    dfs(n)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

N,M = [int(v) for v in input().split()]
ad_list = [[] for _ in range (N+1)]
ad_num = [0 for _ in range(N)]
topo = []

for _ in range(M):
    l,r = [int(v) for v in input().split()]
    ad_list[l].append(r)
    ad_num[r-1] += 1

for i in range(1,N+1):
    if ad_num[i-1] == 0:
        topo.append(i)
queue = deque(topo[:])
while queue:
    n1 = queue.popleft()
    for n2 in ad_list[n1]:
        ad_num[n2-1] -= 1
        if ad_num[n2-1] == 0:
            topo.append(n2)
            queue.append(n2)
visited = [False for _ in range(N+1)]

ans = 0
path_len = 0
def dfs(node,cnt=0):
    global ans
    if visited[node]: return 0
    visited[node] = True
    ans = max(ans,cnt)
    for n in ad_list[node]:
        dfs(n,cnt+1)
    visited[node] = False

for n in topo:
    dfs(n)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

N,M = [int(v) for v in input().split()]
ad_list = [[] for _ in range (N+1)]
ad_num = [0 for _ in range(N)]
topo = []

for _ in range(N-1+M):
    l,r = [int(v) for v in input().split()]
    ad_list[l].append(r)
    ad_num[r-1] += 1

for i in range(1,N+1):
    if ad_num[i-1] == 0:
        topo.append(i)
queue = deque(topo[:])
topo = [[0,topo[0]]]
while queue:
    n1 = queue.popleft()
    for n2 in ad_list[n1]:
        ad_num[n2-1] -= 1
        if ad_num[n2-1] == 0:
            topo.append([n1,n2])
            queue.append(n2)
topo.sort(key=lambda x:x[1])
for i,v in topo:
    print(i)
#  visited = [False for _ in range(N)]

#  ans = 0
#  path_len = 0
#  def dfs(node,cnt=1):
    #  global ans
    #  if visited[node-1]: return 0
    #  visited[node-1] = True
    #  ans = max(ans,cnt)
    #  for n in ad_list[node]:
        #  dfs(n,cnt+1)

#  for n in range(1,N+1):
    #  dfs(n)
#  print(ans)

Submission status: Runtime Error

Solution code:
N,M = [int(v) for v in input().split()]
ad_list = [[] for _ in range (N+1)]
ad_num = [0 for _ in range(N)]
topo = []

for _ in range(M):
    l,r = [int(v) for v in input().split()]
    ad_list[l].append(r)
    ad_num[r-1] += 1
for i in range(1,N+1):
    if ad_num[i-1] == 0:
        topo.append(i)

queue = topo[:]
while queue:
    n1 = queue.pop(0)
    for n2 in ad_list[n1]:
        ad_num[n2-1] -= 1
        if ad_num[n2-1] == 0:
            topo.append(n2)
            queue.append(n2)

visited = [False for _ in range(N)]

ans = 0
path_len = 0
def dfs(node,cnt=1):
    global ans
    if visited[node-1]: return 0
    visited[node-1] = True
    ans = max(ans,cnt)
    for n in ad_list[node]:
        dfs(n,cnt+1)

for n in range(1,N+1):
    dfs(n)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)
dp = [-1] * N
def solve(n):
    if dp[n] != -1:
        return dp[n]
    res = 0
    for nn in E[n]:
        res = max(res, solve(nn)+1)
    dp[n] = res
    return dp[n]
ans = 0
for i in range(N):
    ans = max(ans, solve(i))
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)
dp = [-1] * N
def solve(n):
    if dp[n] != -1:
        return dp[n]
    dp[n] = 0
    for nn in E[n]:
        dp[n] = max(dp[n], solve(nn)+1)
    return dp[n]
ans = 0
for i in range(N):
    ans = max(ans, solve(i))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
E = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)
dp = [-1] * N
def solve(n):
    if dp[n] != -1:
        return dp[n]
    dp[n] = 0
    for nn in E[n]:
        dp[n] = max(dp[n], solve(nn)+1)
    return dp[n]
ans = 0
for i in range(N):
    ans = max(ans, solve(i))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
E = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    E[x].append(y)
dp = [-1] * N
def solve(n):
    if dp[n-1] != -1:
        return dp[n-1]
    dp[n-1] = 0
    for nn in E[n]:
        dp[n-1] = max(dp[n-1], solve(nn)+1)
    return dp[n-1]
ans = 0
for i in range(N):
    ans = max(ans, solve(i+1))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
E = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    E[x].append(y)
dp = [-1] * N
def solve(n):
    global dp, E
    if dp[n-1] != -1:
        return dp[n-1]
    dp[n-1] = 0
    for nn in E[n]:
        dp[n-1] = max(dp[n-1], solve(nn)+1)
    return dp[n-1]
ans = 0
for i in range(N):
    ans = max(ans, solve(i+1))
print(ans)

Submission status: Runtime Error

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

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

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

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

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

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

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

print(max(dp))

Submission status: Runtime Error

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

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

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

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

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

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

print(ans)

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

print(max(dp))

Submission status: Runtime Error

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

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

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

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

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

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

#print(ans)

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

print(max(dp))