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: Accepted

Solution code:
# DAGの最長経路...トポロジカルソートもどきか？
# 普通にDAGに沿ったdpをすればいいのでは?
# 再帰だと実装楽そうだけどどうしよう
# 問題は終了と最初がわからんこと
# いや最初は全部長さ0をセットすればいいだろ
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N, M = ints()
dag = defaultdict(lambda: [])
indeg = [0] * N
for _ in ra(M):
    x, y = mina(*ints())
    indeg[y] += 1
    dag[x].append(y)

q = deque()
for u, inn in enu(indeg):  # 多点DFS初期化
    if inn == 0:
        q.append((u, 0))

dp = [0] * N
while q:  # トポロジカル順序でdpテーブルを埋めていく
    u, l = q.popleft()
    # dp[u] = max(dp[u], l)
    dp[u] = max(dp[u], l)
    for nx in dag[u]:
        indeg[nx] -= 1
        if indeg[nx] == 0:
            q.append((nx, l + 1))
print(max(dp))

Submission status: Accepted

Solution code:
# DAGの最長経路...トポロジカルソートもどきか？
# 普通にDAGに沿ったdpをすればいいのでは?
# 再帰だと実装楽そうだけどどうしよう
# 問題は終了と最初がわからんこと
# いや最初は全部長さ0をセットすればいいだろ
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N, M = ints()
dag = defaultdict(lambda: [])
indeg = [0] * N
for _ in ra(M):
    x, y = mina(*ints())
    indeg[y] += 1
    dag[x].append(y)

q = deque()
for u, inn in enu(indeg):  # 多点DFS初期化
    if inn == 0:
        q.append(u)

dp = [0] * N
while q:  # トポロジカル順序でdpテーブルを埋めていく
    u = q.popleft()
    # dp[u] = max(dp[u], l)
    for nx in dag[u]:
        dp[nx] = max(dp[nx], dp[u] + 1)
        indeg[nx] -= 1
        if indeg[nx] == 0:
            q.append(nx)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
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: Accepted

Solution code:
import collections
import sys 
sys.setrecursionlimit(10**9)
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: Accepted

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

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

dp=[0]*(N+1)

def f(x):
    if dp[x]!=0:
        return dp[x]
    num=0
    for i in edge[x]:
        if i==[]:
            num=max(num,0)
        else:
            num=max(num,f(i)+1)
    dp[x]=num
    return dp[x]

for i in range(1,N+1):
    f(i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
 
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: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


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)

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

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

m=0
for i in range(n):
    if f[i]!=-1:
        continue
    m=max(m,calc(i))
print(m)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100007)

def main():
    n, m = map(int, input().split())
    
    grid = [[] for _ in range(n)]
    
    for _ in range(m):
        x, y = map(int, input().split())
        grid[x-1].append(y-1)
    
    memo = [-1]*n
    
    def dp(n):
        if memo[n] != -1:
            return memo[n]
        res = 0
        for v in grid[n]:
            res = max(res, dp(v)+1)
        memo[n] = res
        return res
    
    ans = 0
    for i in range(n):
        sub = dp(i)
        if ans < sub:
            ans = sub
        
    print(ans)
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# デフォルトだと再帰の上限が設定されている(1000)、足りない場合があるので上げる
import sys
sys.setrecursionlimit(10**9)


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: Accepted

Solution code:
from collections import deque

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

in_node = [0 for i in range(N+1)]
G = [[] for i in range(N+1)]

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

que = deque()

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

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

while que:
    x = que.popleft()
    for child_node in G[x]:
        dp[child_node] = max(dp[child_node], dp[x]+1)
        in_node[child_node] -= 1
        if in_node[child_node] == 0:
            que.append(child_node)

ans = max(dp)

print(ans)

Submission status: Accepted

Solution code:
import sys
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)]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000)

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

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


def f(n):
    if dp[n] != -1:
        return dp[n]
    res = 0
    for m in G[n]:
        res = max(res, f(m) + 1)
    dp[n] = res
    return res


for i in range(1, N + 1):
    f(i)
print(max(dp))

Submission status: Accepted

Solution code:
import collections
import sys
from functools import lru_cache
sys.setrecursionlimit(int(10**9))
n, m  = [int(i) for i in input().strip().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().strip().split(' ')]
    edges[s-1].append(d-1) 
# dp = [-1]*n
maxPath = 0 
@lru_cache(None)
def dfs(node): 
    ans = 0 
    for i in edges[node]:
        ans = max(ans,dfs(i)+1)
    return ans
 
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Submission status: Accepted

Solution code:


INF = float('inf')


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

    vis = [False] * (n + 1)
    done = [False] * (n + 1)

    stack = list(range(1, n + 1))
    topsort = []
    while stack:
        u = stack[-1]
        if done[u]:
            stack.pop()
            continue
        vis[u] = True

        leaf = True
        for v in g[u]:
            if not vis[v]:
                leaf = False
                stack.append(v)

        if leaf:
            topsort.append(u)
            done[u] = True
            stack.pop()  # if no vs, pop u

    # topsort.reverse() # topsort more useful backwards here
    dp = [0] * (n + 1)
    for u in topsort:
        if g[u]:
            dp[u] = max(dp[v] for v in g[u]) + 1

    print(max(dp))


tc()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def topological_sort(N, dag):

    degree = [0] * N
    for i in range(N):
        for v in dag[i]:
            degree[v] += 1

    ret = [v for v in range(N) if degree[v] == 0]
    q = deque(ret)

    while q:
        v = q.popleft()
        for nv in dag[v]:
            degree[nv] -= 1
            if degree[nv] == 0:
                q.append(nv)
                ret.append(nv)

    return ret


def main():

    N, M = in_nn()

    edge = [[] for _ in range(N)]
    for i in range(M):
        x, y = in_nn()
        x, y = x - 1, y - 1
        edge[x].append(y)

    dp = [0] * N
    vs = topological_sort(N, edge)
    for v in vs:
        for nv in edge[v]:
            dp[nv] = max(dp[nv], dp[v] + 1)

    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

dp = [-1]*(N)

def f(v):
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for nv in G[v]:
        ans = max(ans, f(nv) + 1)
    dp[v] = ans
    return ans

ans = 0
for i in range(N):
    ans = max(ans, f(i))

print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a-1]+=[b-1]



dp = [-1] * n

def f(x):
    if dp[x] != -1:
        return dp[x]
    ret = 0
    for y in G[x]:
        ret = max(f(y) + 1, ret)
    dp[x] = ret
    return ret

for i in range(n):
    f(i)

print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a-1]+=[b-1]



dp = [-1] * n

def f(x):
    if dp[x] != -1:
        return dp[x]
    ret = 0
    for y in G[x]:
        ret = max(f(y) + 1, ret)
    dp[x] = ret
    return ret

for i in range(n):
    f(i)

print(max(dp))

Submission status: Accepted

Solution code:
import sys

try:
    import solve
except:
    from distutils.core import setup
    from distutils.extension import Extension
    from Cython.Distutils import build_ext
    from Cython.Build import cythonize

    if len(sys.argv) < 2:
        sys.argv.append("build_ext")
    else:
        sys.argv[1] = "build_ext"
    sys.argv.append("--inplace")

    with open(__file__) as f:
        with open('solve.pyx', 'w') as fw:
            while c := f.readline():
                if c.strip() == '"""':
                    nc = f.readline()
                    if nc.strip() == "solve.pyx":
                        while cc := f.readline():
                            if cc.strip() == '"""':
                                break
                            fw.write(cc)
    setup(
        name="my_module",
        ext_modules=cythonize(
            Extension("solve",
                      sources=["solve.pyx"],
                      extra_compile_args=["-O3"],
                      language="c++",
                      ),
            compiler_directives={'language_level': "3"}
        ),
        cmdclass={'build_ext': build_ext},
    )
    exit(0)

solve.main()

"""
solve.pyx
# distutils: language = c++
# cython: language_level=3, boundscheck=True
 
import sys
 
from libcpp.vector cimport vector
 
DEF MAX_N = 100100
DEF MAX_M = 100100
cdef vector[long] *g
cdef long memo[MAX_N]
 
 
cdef long f(long x):
    cdef long ret
    if memo[x] == -1:
        ret = 0
        for y in g[x]:
            ret = max(ret, f(y) + 1)
        memo[x] = ret
    return memo[x]
 
 
def resolve(in_):
    cdef long i
    global g
    cdef vector[long] _g[MAX_M]
    g = _g
    for i in range(MAX_N):
        memo[i] = -1
 
    _n, _m = next(in_).split()
    cdef int n, m
    n = int(_n)
    m = int(_m)
    for line in in_:
        _x, _y = line.split()
        g[int(_x) - 1].push_back(int(_y) - 1)
 
    cdef long ret = 0
    for i in range(n):
        ret = max(f(i), ret)
    return ret
 
 
def main():
    ans = resolve(sys.stdin.buffer)
    print(ans)
"""

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10**9)
cache,edge={},collections.defaultdict(list)
def dp(node):
  if node in cache:
    return cache[node]
  lcl_max=0
  for child in edge[node]:
    
    lcl_max=max(lcl_max,1+dp(child))
  cache[node]=lcl_max
  return lcl_max
 
max_dis=0

n,m=map(int,input().split())
for _ in range(m):
  a,b=map(int,input().split())
  edge[a].append(b)
for node in range(1,n+1):
  max_dis=max(max_dis,dp(node))
print(max_dis)

Submission status: Accepted

Solution code:
import collections
import sys
from functools import lru_cache
sys.setrecursionlimit(int(10**9))
n, m  = [int(i) for i in input().strip().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().strip().split(' ')]
    edges[s-1].append(d-1) 
# dp = [-1]*n
maxPath = 0 
@lru_cache(None)
def dfs(node): 
    ans = 0 
    for i in edges[node]:
        ans = max(ans,dfs(i)+1)
    return ans

for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def topological_sort(graph):
  N = len(graph)
  in_cnt = [0 for i in range(N)]
  for x in range(N):
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in range(N) if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in range(N) if in_cnt[i]]:
    return None
  return ret

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  
L = topological_sort(graph)

d = [0 for i in range(N)]
for x in L:
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
print(max(d))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
v,e=map(int,input().split())
m=defaultdict(list)

for i in range(e):
    x,y=map(int,input().split())
    m[x].append(y)
dp=defaultdict(lambda:-1)
def longestPath():
    
    def findLongestPath(vtx):
        if(dp[vtx]!=-1):
            return dp[vtx]
        res=0
        for i in m[vtx]:
            res=max(res,1+findLongestPath(i))
        dp[vtx]=res
        return res
        
        
    
    ans=0
    for i in range(1,v+1):
        ans=max(ans,findLongestPath(i))
    
    return ans;

print(longestPath())

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])


G = defaultdict(list)
first = 1 #  if node starts from 1

def addEdge(a,b):
    G[a].append(b)
	
def DFSutil(node,vis,size):
    vis[node] = True
    for child in G.get(node,[]):
        if vis[child] ==  False:
            DFSutil(child,vis,size)
        size[node] = max(size[node],1 + size[child])
    
def findsubtree(first,N):
    vis = [False] * (N+1)
    size = [0]* (N+1)
    for i in range(1,N+1):
        if vis[i] == False:
            DFSutil(i,vis,size)
    return max(size)
        
N,M = ilele()
G = defaultdict(list)
for i in range(M):
    u,v =ilele()
    addEdge(u,v)
print(findsubtree(first,N)) #returns size of each node in the array

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

## a, bを無向辺として，隣接リストを作成
n, m = list(map(int, input().split()))
al = [[] for i in range(n)]

for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1

    al[a].append(b)

@functools.lru_cache(None)
def depth(u):
    if len(al[u]) == 0:
        return 0
    else:
        max_d = 0
        for v in al[u]:
            max_d = max(max_d, depth(v) + 1)
        return max_d

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

Submission status: Accepted

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

N,M = map(int,input().split())
G = {}
for node in range(1,N+1):
	G[node] = set()
for _ in range(M):
	x,y = map(int,input().split())
	G[x].add(y)

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

def maxpa(G,source,maxpath):
	if maxpath[source] != -1:
		return maxpath[source]
	else:	
		if len(G[source]) == 0:
			maxpath[source] = 0
			return maxpath[source]
		else:	
			for ngbr in G[source]:
				maxpath[source] = max(maxpath[source],1+maxpa(G,ngbr,maxpath))
			return maxpath[source]

for i in range(1,N+1):
	if maxpath[i]==-1:
		maxpa(G,i,maxpath)

print(max(maxpath))

Submission status: Accepted

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 01/08/2020

from sys import stdin, stdout
import sys
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007
sys.setrecursionlimit(100000)
n, m = iia()
dp = [-1] * (n + 1)
d = {}
for i in range(m):
    a, b = iia()
    d.setdefault(a, []).append(b)

def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    t = 0
    for i in d.get(cur, []):
        t = max(1 + dfs(i), t)
    dp[cur] = t
    return dp[cur]

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

Submission status: Accepted

Solution code:
#解説AC

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

dp=[-1]*n

def memo(v):
    if dp[v]+1: #更新済 dp[v]!=-1
        return dp[v]
    a=0
    for i in es[v]:
        a=max(a,memo(i)+1)
    dp[v]=a
    return a

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

print(ans)

Submission status: Accepted

Solution code:
# 根付き木に対して根から最大でどれだけかかるかを使う方法

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(m):
    a, b = map(int, input().split())    
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: #更新済
        return dp[v]

    for i in co[v]:
        x = memo(i) + 1
        if x > dp[v]:
            parent[v] = i + 1
            dp[v] = x

    return max(dp[v], 0)
# 経路復元
parent = [0] * n


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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def f(v):
    if dp[v] != 0:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res,f(i)+1)
    dp[v] = res
    return res
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1)
dp = [0]*N
for i in range(N):
    f(i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def f(v):
    if dp[v] != 0:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res,f(i)+1)
    dp[v] = res
    return res
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1)
dp = [0]*N
ans = 0
for i in range(N):
    ans = max(ans,f(i))
print(ans)

Submission status: Accepted

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

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

def dfs(v):
  if len(edge[v])==0:
    return 0
  ans = 0
  for u in edge[v]:
    if longest[u]==-1:
      longest[u]=dfs(u)
    ans = max(ans,longest[u]+1)
  return ans

longest = [-1]*N
for i in range(N):
  if longest[i]==-1:
    longest[i] = dfs(i)
ans = max(longest)
print(ans)

Submission status: Accepted

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

#import math
#import numpy as np
#= int(input())
#= input()
#= map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]
def dfs(num):
    if dp[num] != -1:
        return dp[num]

    res = 0
    for obj in G[num]:
        res = max(res, dfs(obj) + 1)

    dp[num] = res
    return res


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

dp = [-1] * N
G = {i:[] for i in range(N)}

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

res = 0
for i in range(N):
    res = max(res, dfs(i))

print(res)