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:
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
to = [False]*N
for i in range(M):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  to[b-1] = True

import sys
sys.setrecursionlimit(10**8)

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

ans = 0
for r in range(N):
  if to[r]==False:
    ans = max(ans, dfs(r)-1)
print(ans)

Submission status: Time Limit Exceeded

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

# If the element is already present in the list,

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

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

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

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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


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

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


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

mod = 1000000007


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


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


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


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


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


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


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


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


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


from collections import defaultdict, deque


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

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

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

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


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

    return count


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



import sys
sys.setrecursionlimit(10**6)



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

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

    for v in range(n):
        dfs(v)

    print(max(dp))


solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [-1]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    #    x.append(x_in)
    #    y.append(y_in)
    d.append((x_in, y_in))

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


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in, y_in in d:
            if x_in == i:
                tmp = dp(y_in) + 1
                if tmp > ret:
                    ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [-1]

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

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


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in, y_in in d:
            if x_in == i:
                tmp = dp(y_in) + 1
                if tmp > ret:
                    ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [-1]

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

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


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in, y_in in d:
            if x_in == i:
                tmp = dp(y_in) + 1
                ret = max(tmp, ret)
        memo[i] = ret
        ans = max(ret, ans)
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [-1]

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

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


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in, y_in in d:
            if x_in == i:
                tmp = dp(y_in) + 1
                ret = max(tmp, ret)
        memo[i] = ret
        ans = max(ret, ans)
        return ret
    else:
        return memo[i]


for i, _ in d:
    tmp = dp(i)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [-1]

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

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


def dp(i):
    if memo[i] == -1:
        ret = 0
        for x_in, y_in in d:
            if x_in == i:
                tmp = dp(y_in) + 1
                ret = max(tmp, ret)
        memo[i] = ret
        return ret
    else:
        return memo[i]


for i in x[1:]:
    tmp = dp(i)
    ans = max(tmp, ans)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import setrecursionlimit
setrecursionlimit(1000000)
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

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

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


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


for i in x[1:]:
    tmp = dp(i)
    ans = max(tmp, ans)

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

Submission status: Time Limit Exceeded

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

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

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

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


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


for i in x[1:]:
    tmp = dp(i)
    ans = max(tmp, ans)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dp = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
parents = [[] for _ in range(N + 1)]
children = [[] for _ in range(N + 1)]

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

    parents[y].append(x)
    children[x].append(y)

    dp[i] = dp[i - 1]
    dp[i][x] = max(dp[i - 1][x], dp[i - 1][y] + 1)

    ancient = deque([])
    ancient.append(x)

    while ancient:
        v = ancient.popleft()
        for w in parents[v]:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][v] + 1)
            ancient.append(w)    

ans = max(dp[M])

print(ans)

Submission status: Time Limit Exceeded

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)  # 別にlengthの情報をもたせちゃってもいいんだけどね

dp = [0] * N
while q:  # トポロジカル順序でdpテーブルを埋めていく
    u = q.popleft()
    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: Time Limit Exceeded

Solution code:
import collections
N,M = map(int,input().split())
road = [[] for i in range(N+1)]
rev_road = [[] for i in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
    rev_road[y].append(x)

dep = []
for i in range(1,N+1):
    if len(rev_road[i]) == 0:
        dep.append(i)

def largest_distance(i):
    q = collections.deque([i])
    dp =[0]*(N+1) #地点iからの最長経路
    dp_max = 0
    while q:
        now = q.popleft()
        for direct in road[now]:
            if dp[direct]<=dp[now]:
                dp[direct] = dp[now]+1
                q.append(direct)
                dp_max = max(dp_max,dp[direct])
    return dp_max
ans = 0
for de in dep:
    ans = max(ans,largest_distance(de))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N,M = map(int,input().split())
road = [[] for i in range(N+1)]
rev_road = [[] for i in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
    rev_road[y].append(x)

dep = []
for i in range(1,N+1):
    if len(rev_road[i]) == 0:
        dep.append(i)

def largest_distance(i):
    q = collections.deque([i])
    dp =[0]*(N+1) #地点iからの最長経路
    while q:
        now = q.popleft()
        for direct in road[now]:
            if dp[direct]<=dp[now]:
                dp[direct] = dp[now]+1
                q.append(direct)
    return max(dp)

ans = 0
for de in dep:
    ans = max(ans,largest_distance(de))
print(ans)

Submission status: Time Limit Exceeded

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

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

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

def g(x):
    q=deque([x])
    move=[[1,0],[-1,0],[0,1],[0,-1]]
    num=-1
    s=False
    while q:
        #print(q)
        for i in range(len(q)):
            b=q.popleft()
            if edge[b]==[]:
                #print(num)
                #print(H*W-kuro-num-1)
                num=num
            else:
                for i in edge[b]:
                    q.append(i)
        num+=1
    return num        
m=0
for i in range(N):
    m=max(m,g(i+1))
print(m)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
memo =  [-1] * N  #入力がない頂点を-1で探す
dp = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append((x, y))
    memo[y] = 0

q = deque()
for i in range(N): #入力がない頂点からスタート
    if memo[i] == -1:
        q.append(G[i])

while q:
    moves = q.pop()
    for move in moves:
        x, y = move
        dp[y] = max(dp[y], dp[x]+1)
        q.append(G[y])
    
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
memo =  [-1] * N  #入力がない頂点を-1で探す
dp = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append((x, y))
    memo[y] = 0

q = deque()
for i in range(N):
    if memo[i] == -1:
        q.append(G[i])

while q:
    moves = q.pop()
    for move in moves:
        x, y = move
        dp[y] = max(dp[y], dp[x]+1)
        q.append(G[y])
    
print(max(dp))

Submission status: Time Limit Exceeded

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

Solution code:
from collections import deque

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

q = deque()

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

q = deque()

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit = 1000000

input  = stdin.readline

n,m = list(map(int,input().split()))
par = [[] for _ in range(n+1)]
dis = [0]*(n+1)
vis = dis[:]

def dfs(n):
	sta = []
	sta.append(n)
	while(sta):
		n = sta.pop(-1)
		for i in par[n]:
			dis[i] = max(dis[i], dis[n]+1)
			sta.append(i)

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

for i in range(1,n+1):
	if not vis[i]:
		dfs(i)

print(max(dis))

Submission status: Time Limit Exceeded

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 bfs(N, v0, edge):

    d = [-1] * N
    d[v0] = 0
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        for nv in edge[v]:
            q.append(nv)
            d[nv] = max(d[nv], d[v] + 1)

    return max(d)


def v_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]

    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)

    vs = v_sort(N, edge)
    ans = 0
    for v in vs:
        ans = max(ans, bfs(N, v, edge))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
    return ans

for i in range(N):
    dp[i] = f(i)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#0-indexに注意
n,m=MI()
al=[0]*n
lis=[[] for i in range(n)]
for i in range(m):
    a,b=MI()
    a-=1
    b-=1
    al[b]=-1
    lis[a].append(b)
starts=[]
for i in range(n):
    if al[i]==0:
        starts.append(i)
#print(starts)
#print(lis)
dp=[0 for i in range(n)]
def dfsdp(x):
    for y in lis[x]:
        dp[y]=max(dp[y],dp[x]+1)
        dfsdp(y)
for x in starts:
    dfsdp(x)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
  
memo = [0] * n
edges = []

for i in range(m):
  xi, yi = map(int, input().split())
  xi, yi = xi - 1, yi - 1
  edges.append([xi, yi])

while True:
  changed = False
  for x, y in edges:
    if memo[y] < memo[x] + 1:
      changed = True
      memo[y] = memo[x] + 1
  if not changed:
    break
  
print(max(memo))

Submission status: Time Limit Exceeded

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

from sys import stdin,stdout
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

def bfs(node, d):
    queue = [node, None]
    count = 0
    while len(queue):
        cur = queue.pop(0)
        if not cur:
            if len(queue):
                queue.append(None)
            count += 1
        else:
            for neigh in d.get(cur, []):
                queue.append(neigh)
    return count - 1

n, m = iia()
d = {}
indegree = [0] * (n + 1)
for i in range(m):
    a, b = iia()
    d.setdefault(a, []).append(b)
    indegree[b] += 1

res = 0
for i in range(1, n + 1):
    if indegree[i] == 0:
        res = max(res, bfs(i, d))
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G_fix_3
# CreatedDate:  2020-07-28 22:54:01 +0900
# LastModified: 2020-07-28 23:31:55 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import deque


class Graph():
    def __init__(self, vertex):
        self.V = vertex
        self.path = [[] for _ in range(self.V+1)]
        self.Q = deque()
        self.distance = [0] * (self.V+1)

    def addedge(self, s, t):
        self.path[s].append(t)

    def bfs(self, init):
        self.Q.append(init)
        while self.Q:
            u = self.Q.popleft()
            for v in self.path[u]:
                if self.distance[v] < self.distance[u]+1:
                    self.distance[v] = self.distance[u]+1
                    self.Q.append(v)
        return max(self.distance)

    def clear(self):
        self.distance = [0] * (self.V+1)


def main():
    N, M = map(int, input().split())
    graph = Graph(N)
    init_recommend = [0] * (N+1)
    for _ in range(M):
        s, t = map(int, input().split())
        graph.addedge(s, t)
        init_recommend[t] += 1
    ans = 0
    for init in range(1, N+1):
        if init_recommend[init] == 0:
            ans = max(ans, graph.bfs(init))
            graph.clear()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G_fix_3
# CreatedDate:  2020-07-28 22:54:01 +0900
# LastModified: 2020-07-28 23:09:02 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import deque


class Graph():
    def __init__(self, vertex):
        self.V = vertex
        self.path = [[] for _ in range(self.V+1)]
        self.Q = deque()
        self.distance = [0] * (self.V+1)

    def addedge(self, s, t):
        self.path[s].append(t)

    def bfs(self, init):
        self.Q.append(init)
        while self.Q:
            u = self.Q.popleft()
            for v in self.path[u]:
                if self.distance[v] < self.distance[u]+1:
                    self.distance[v] = self.distance[u]+1
                    self.Q.append(v)
        return max(self.distance)

    def clear(self):
        self.distance = [0] * (self.V+1)


def main():
    N, M = map(int, input().split())
    graph = Graph(N)
    for _ in range(M):
        s, t = map(int, input().split())
        graph.addedge(s, t)
    ans = 0
    for init in range(1, N+1):
        ans = max(ans, graph.bfs(init))
        graph.clear()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 14:22:54 2020

@author: Maruthi Srinivas
"""
import sys
sys.setrecursionlimit(1000000)
def dfs(node,graph,dp):
    temp=0
    if dp[node]!=-1:
        return dp[node]
    for i in graph[node]:
        temp=max(temp,dfs(i,graph,dp)+1)
    dp[node]=temp
    return temp
            
v,e=map(int,input().split())
adj={x:[] for x in range(v+1)}
for i in range(e):
    x,y=map(int,input().split())
    adj[x].append(y)
m=-1
dp=[-1]*(v+1)
for i in range(1,v+1):
    visited=[False]*(v+1)
    x=dfs(i,adj,dp)
    #print(i,x)
    m=max(m,x)
print(m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 14:22:54 2020

@author: Maruthi Srinivas
"""
import sys
sys.setrecursionlimit(10000000)
def dfs(node,graph):
    temp=0
    for i in graph[node]:
        temp=max(temp,dfs(i,graph)+1)
    return temp
            
v,e=map(int,input().split())
adj={x:[] for x in range(v+1)}
for i in range(e):
    x,y=map(int,input().split())
    adj[x].append(y)
m=-1
for i in range(1,v+1):
    visited=[False]*(v+1)
    x=dfs(i,adj)
    m=max(m,x)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from functools import lru_cache


g = None


@lru_cache(maxsize=100000)
def f(x):
    return max((f(y) + 1 for y in g[x]), default=0)


def resolve(in_):
    global g
    n, m = map(int, next(in_).split())
    _g = defaultdict(list)
    for line in in_:
        x, y = map(int, line.split())
        _g[x - 1].append(y - 1)
    g = _g
    f.cache_clear()
    return max(f(i) for i in range(n))


def main():
    sys.setrecursionlimit(200000)
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def LPP():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        temp = list(map(int, input().split()))
        edges.append(temp)
    edges.sort(key=lambda x: x[0])
    paths = []
    i = 0
    maxi = 0
    while i < len(edges):
        temp_edge = edges[i].copy()
        j = 0
        while j < len(edges):
            if edges[j][0] == temp_edge[-1]:
                temp_edge.append(edges[j][1])
                j = 0
            else:
                j += 1
        i += 1
        maxi = max(maxi, len(temp_edge))
        paths.append(temp_edge.copy())
        temp_edge.clear()
    print(maxi-1, end="")

LPP()

Submission status: Time Limit Exceeded

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

for i in range(M):
    Start_Point,Stop_Point =  map(int,input().split())
    Max_Number = max([x[Start_Point - 1] for x in dp])
    dp[Start_Point - 1][Stop_Point - 1] = Max_Number + 1

print(max(map(lambda x:max(x),dp)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = map(int,input().split())
dp = np.array([[0] * N for i in range(N)])

for i in range(M):
    Start_Point,Stop_Point =  map(int,input().split())
    Max_Number = max([x[Start_Point - 1] for x in dp])
    dp[Start_Point - 1][Stop_Point - 1] = Max_Number + 1

print(dp.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = map(int,input().split())
dp = [[0] * N for i in range(N)]

for i in range(M):
    Start_Point,Stop_Point =  map(int,input().split())
    Max_List = np.amax(dp, axis=0)
    dp[Start_Point - 1][Stop_Point - 1] = Max_List[Start_Point - 1] + 1

print(max(np.amax(dp, axis=0)))