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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G_fix
# CreatedDate:  2020-06-05 21:28:41 +0900
# LastModified: 2020-06-05 21:54:44 +0900
#


import os
import sys
import heapq
#import numpy as np
#import pandas as pd


def main():
    n,m = map(int,input().split())
    path = [[] for _ in range(n+1)]
    to_cnt = [0]*(n+1)
    longest_cnt = [0]*(n+1)
    for _ in range(m):
        x,y = map(int,input().split())
        path[x].append(y)
        to_cnt[y]+=1
#    print(to_cnt)
    
    Q = []
    for i in range(1,n+1):
        if to_cnt[i]==0:
            Q.append(i)

#    longest_cnt[s]=1
    heapq.heapify(Q)
    count=0
    while(Q):
        u = heapq.heappop(Q)
        for v in path[u]:
            to_cnt[v]-=1
            if longest_cnt[u]+1>longest_cnt[v]:
                longest_cnt[v]=longest_cnt[u]+1
            heapq.heappush(Q,v)
    print(max(longest_cnt))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
def main():
    n, m = list(map(int, input().split()))
    out = [[] for _ in range(n)]
    for _ in range(m):
        x, y = list(map(int, input().split()))
        out[x - 1].append(y - 1)
    dp = [-1] * n
    def count(i):
        if dp[i] != -1:
            return dp[i]
        else:
            cnt = 0
            for o in out[i]:
                cnt = max(cnt, count(o) + 1)
            return cnt

    for i in range(n):
        dp[i] = count(i)
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = [-1 for _ in range(N)]

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

#solve DAG and topological sort by recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    return ret
for v in range(N):
    dp[v] = f(v)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = np.ones((N),dtype=int) * -1

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

#solve DAG and topological sort by recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    return ret
for v in range(N):
    dp[v] = f(v)
print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n,m=reads()
link=[[]for i in range(n)]
for i in range(m):
  x,y=reads()
  link[x-1].append(y-1)
def dp(k):
  res=0
  for ele in link[k]:
    res=max(res,dp(ele)+1)
  return res
res=1
for i in range(n)  :
  res=max(res,dp(i))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
from queue import Queue

inp = stdin.readline
out = stdout.write

n,m = map(int,inp().split())
adj = [[] for _ in range(n+1)]

for i in range(m):
    u,v = map(int,inp().split())
    adj[u].append(v)

dp = [1 for i in range(n+1)]
seen = [False for i in range(n+1)]

def bfs(u):
    seen[u] = True
    q = Queue()
    q.put(u)
    while not q.empty():
        u = q.get()
        for v in adj[u]:
            if dp[u]+1 > dp[v]:
                q.put(v)
                dp[v] = dp[u]+1

for u in range(1,n+1): 
    if not seen[u]: bfs(u)

out(str(max(dp)-1))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
from queue import Queue

inp = stdin.readline
out = stdout.write

n,m = map(int,inp().split())
adj = [[] for _ in range(n+1)]

for i in range(m):
    u,v = map(int,inp().split())
    adj[u].append(v)

dp = [1 for i in range(n+1)]
seen = [False for i in range(n+1)]

def bfs(u):
    seen[u] = True
    q = Queue()
    q.put(u)
    while not q.empty():
        u = q.get()
        for v in adj[u]:
            q.put(v)
            dp[v] = max(dp[v], dp[u]+1)

for u in range(1,n+1): 
    if not seen[u]: bfs(u)

out(str(max(dp)-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] = 1
    deg = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while deg:
        i = deg.popleft()
        for j in li[i]:
            dpj = dp[j]
            dpi = dp[i]
            if dpj < dpi + 1:
                dp[j] = dpi + 1
            deg.appendleft(j)
    print(max(dp))
a()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] = 1
    deg = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while deg:
        i = deg.popleft()
        for j in li[i]:
            dpj = dp[j]
            dpi = dp[i]
            if dpj < dpi + 1:
                dp[j] = dpi + 1
            deg.appendleft(j)
    print(max(dp))
a()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

N, M = map(int, rl().split())
li = [[] for _ in range(N)]
deg = [0] * N
for _ in range(M):
    a, b = map(int, rl().split())
    a -= 1
    b -= 1
    li[a].append(b)
    deg[b] = 1
deg = collections.deque([i for i in range(N) if deg[i] == 0])
dp = [0] * N
while deg:
    i = deg.popleft()
    for j in li[i]:
        if dp[j] < dp[i] + 1:
            dp[j] = dp[i] + 1
        deg.appendleft(j)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

N, M = map(int, rl().split())
li = [[] for _ in range(N)]
deg = [0] * N
for _ in range(M):
    a, b = map(int, rl().split())
    a -= 1
    b -= 1
    li[a].append(b)
    deg[b] = 1
deg = [i for i in range(N) if deg[i] == 0]
dp = [0] * N
for i in deg:
    for j in li[i]:
        if dp[j] < dp[i] + 1:
            dp[j] = dp[i] + 1
        deg.append(j)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        tree[a - 1].append([b - 1, 1])
        tree[b - 1].append([a - 1, -1])

    def bfs(v):
        q = deque()
        q.append(v)
        while q:
            u = q.popleft()
            for nv, d in tree[u]:
                if d == 1:
                    dist[nv] = max(dist[nv], dist[u] + d)
                    q.append(nv)

    dist = [0 for _ in range(n)]
    for i in range(n):
        if dist[i] == 0:
            bfs(i)

    print(max(dist))


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M = map(int, input().split())
    # G[x]:xから直接行ける町リスト
    G = [[] for i in range(N)]
    for i in range(M):
        x,y = map(lambda x:x-1, map(int, input().split()))
        G[x].append(y)
    # DFS(深さ優先探索)をDP
    # dp[i] := iを始点とした最長パスの長さ
    dp = [0]*N
    for i in range(N):
        dest = G[i]
        maxd = 0
        depth = 0
        while dest!=[]:
            tmp = []
            for d in dest:
                if d<i:
                    maxd = max(maxd, depth+1+dp[d])
                else:
                    tmp.extend(G[d])
            dest = tmp
            depth += 1
        dp[i] = max(maxd,depth)

    print(max(dp))
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M = map(int, input().split())
    # G[x]:xから直接行ける町リスト
    G = [[] for i in range(N)]
    for i in range(M):
        x,y = map(lambda x:x-1, map(int, input().split()))
        G[x].append(y)
    # DFS(深さ優先探索)をDP
    # dp[i] := iを始点とした最長パスの長さ
    dp = [0]*N
    for i in range(N):
        dest = G[i]
        depth = 0
        while dest!=[]:
            tmp = []
            for d in dest:
                tmp.extend(G[d])
            dest = tmp
            depth += 1
        dp[i] = depth

    print(max(dp))
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(vertices, start):      
    q = deque()
    q.append(start)
    while q:
        u = q.popleft()                          
        for v in vertices[u]:
            if vis[v]==0 or (vis[u]+1>vis[v]) :
                vis[v]=vis[u]+1
                q.append(v)
    return max(vis)
n,m=map(int,input().split())
v=[[] for i in range(n+1)]
for i in range(m):
	x,y=map(int,input().split())
	v[x].append(y)
vis = [0]*(n+1) 
vis[0]=1
m=0
while 0 in vis:
	i=vis.index(0)
	vis[i]=1
	m=max(m,bfs(v,i))
print(m-1)

Submission status: Time Limit Exceeded

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


def dfs(v):
    global dp
    if v in dp:
        return dp[v]
    res = 0
    for next_v in e[v]:
        res = max(dfs(next_v) + 1, res)
    dp[v] = res
    return res


def main():
    N, M = map(int, input().split())
    global e
    e = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
    global dp
    dp = [-1]*N
    ans = -1
    for v in range(N):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def dfs(v, e, visited, dp):
    if v not in visited:
        if not e[v]:
            dp[v] = 0
        for next_v in e[v]:
            yield from dfs(next_v, e, visited, dp)
        visited.add(v)
        yield v


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    e_ = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        e_[v].append(u)
    topological_sorted = []
    visited = set()
    dp = [-1]*N
    for v in range(N):
        topological_sorted += list(dfs(v, e, visited, dp))
    for v in topological_sorted:
        for other_side in e_[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def dfs(v, e, visited, dp):
    if v in visited:
        return []
    ret = []
    if not e[v]:
        dp[v] = 0
    for next_v in e[v]:
        ret += dfs(next_v, e, visited, dp)
    ret.append(v)
    visited.add(v)
    return ret


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    e_ = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        e_[v].append(u)
    topological_sorted = []
    visited = set()
    dp = [-1]*N
    for v in range(N):
        topological_sorted += dfs(v, e, visited, dp)
    for v in topological_sorted:
        for other_side in e_[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
dit = [0]*N
st = [[] for _ in range(N)]
re = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    st[x].append(y)
    re[y].append(x)
def dfs(u):
    if len(re[u]) == 0:
        return
    li = re[u]
    for j in li:
        if dit[j] < dit[u]+1:
            dit[j] = dit[u]+1
            dfs(j)
for i in range(N):
    if len(st[i]) != 0:
        continue
    else:
        dfs(i)
print(max(dit))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
dit = [0]*N
st = [[] for _ in range(N)]
re = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    st[x].append(y)
    re[y].append(x)
def dfs(u):
    if len(re[u]) == 0:
        return
    li = re[u]
    for j in li:
        dit[j] = max(dit[j],dit[u]+1)
        dfs(j)
for i in range(N):
    if len(st[i]) != 0:
        continue
    else:
        dfs(i)
print(max(dit))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
dit = [0]*N
st = [[] for _ in range(N)]
re = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    st[x].append(y)
    re[y].append(x)
def dfs(u):
    if len(re[u]) == 0:
        return
    li = re[u]
    for j in li:
        dit[j] = max(dit[j],dit[u]+1)
        dfs(j)
for i in range(N):
    if len(st[i]) != 0:
        continue
    else:
        dfs(i)
print(max(dit))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# メモ化関数定義
def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func
@memoize
def rec(v):
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache
sys.setrecursionlimit(10**6)
@lru_cache(maxsize=None)
def rec(v):
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase
 
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")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
####################################################
import threading
sys.setrecursionlimit(10**5)
threading.stack_size(10**8)
def dfs(x):
    global l,adj,v
    v[x]=1
    for i in adj[x]:
        l[i]=max(l[i],l[x]+1)
        dfs(i)
def main():
    global l,adj,v
    n,m=map(int,input().split())
    l=[0]*(n+1)
    v=[0]*(n+1)
    adj=[]
    for i in range(n+1):
        adj.append([])
    for i in range(m):
        x,y=map(int,input().split())
        adj[x].append(y)
    for i in range(1,n+1):
        if not v[i]:
            dfs(i)
    print(max(l))
t=threading.Thread(target=main)
t.start()
t.join()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase
 
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")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
####################################################
import threading
sys.setrecursionlimit(10**5)
threading.stack_size(10**8)
def dfs(x):
    global l,adj
    v[x]=1
    for i in adj[x]:
        l[i]=max(l[i],l[x]+1)
        dfs(i)
def main():
    global l,adj,v
    n,m=map(int,input().split())
    l=[0]*(n+1)
    v=[0]*(n+1)
    adj=[]
    for i in range(n+1):
        adj.append([])
    for i in range(m):
        x,y=map(int,input().split())
        adj[x].append(y)
    for i in range(1,n+1):
        if not v[i]:
            dfs(i)
    print(max(l))
t=threading.Thread(target=main)
t.start()
t.join()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase
 
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")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
####################################################
import threading
sys.setrecursionlimit(10**5)
threading.stack_size(10**8)
def dfs(x):
    global l,adj,v,ans
    v[x]=1
    for i in adj[x]:
        l[i]=max(l[i],l[x]+1)
        ans=max(ans,l[i])
        dfs(i)
def main():
    global l,adj,v,ans
    ans=0
    n,m=map(int,input().split())
    l=[0]*(n+1)
    v=[0]*(n+1)
    adj=[]
    for i in range(n+1):
        adj.append([])
    for i in range(m):
        x,y=map(int,input().split())
        adj[x].append(y)
    for i in range(1,n+1):
        if not v[i]:
            dfs(i)
    print(ans)
t=threading.Thread(target=main)
t.start()
t.join()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M = geta(int)
    g = defaultdict(lambda: [])
    for _ in range(M):
        x, y = geta(int)
        g[x].append(y)

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

    def dfs(i):
        if dp[i] != -1:
            return dp[i]
        else:
            dist = 0
            for j in g[i]:
                dist_j = 1 + dfs(j)
                if dist_j > dist: dist = dist_j
            return dist

    ans = 0
    for i in range(1, N + 1):
        tmp = dfs(i)
        if tmp > ans: ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**9)


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

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

    return memo[v]


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

    memo = {}

    print(max(dfs(i, graph, memo) for i in range(N)))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**9)


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

    memo = {}

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

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

        return memo[v]

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**9)


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

    memo = {}

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

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

        return memo[v]

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()