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:

Solution (Python):
from collections import defaultdict, deque
N,M=map(int, input().split())
G = {i: [] for i in range(1, N+1)}
deg = [0]*(N+1)
for _ in range(M):
    x,y=map(int,input().split())
    G[x].append(y)
    deg[y] += 1

from collections import deque, defaultdict
S = [i for i in range(1, N+1) if deg[i]==0]
dp = [0]*(N+1)

def topological_sort(adj, indeg):
    """
    幅優先探索によるトポロジカルソート
    O(|V|+|E|)

    adj: 隣接リスト
    indeg: 各ノード入次数を管理するリスト

    ret: トポロジカルソートされたリスト
    """
    is_visited = [0]*(N+1)
    ret = []
    def bfs():
        """
        sからBFSする
        """
        queue = deque(S)
        while queue:
            u = queue.popleft()
            
            

            for v in adj[u]: 
                indeg[v] -= 1 
                if (indeg[v] == 0):
                    
                    queue.append(v)
                    dp[v] = max(dp[v], dp[u]+1)
                    is_visited[v] = 1
    
    bfs()
    
    

topological_sort(G, deg)
print(max(dp))

Solution (Python):
def main():
    from collections import deque
    N, M = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    deg = [0]*N
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        deg[b-1] += 1

    dist = [10**6]*(N)

    def topological_sort():
        """
        deg[i] := 頂点iの入次数
        グラフ入力時に計算
        """
        que = deque()
        for i in range(N):
            if deg[i] == 0:
                que.append(i)
                dist[i] = 0

        while que:
            u = que.popleft()
            for v in G[u]:
                deg[v] -= 1
                if deg[v] == 0:
                    que.append(v)
                    dist[v] = dist[u] + 1

    topological_sort()

    print(max(dist))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10**9)
INF=float('inf')

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

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

ans=-INF  
for i in range(1,n+1):
  ans=max(ans,f(i))

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())
G=[[] for i in range(N)]
a,b=0,0
for i in range(M):
  a,b=map(int,input().split())
  G[b-1].append(a-1)
DP=[-1]*N
def f(x):
  if DP[x]!=-1:
    return DP[x]
  DP[x]=0
  for i in range(len(G[x])):
    DP[x]=max(DP[x],f(G[x][i])+1)
  return DP[x]

for i in range(N):
  f(i)
print(max(DP))

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

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

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

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

print(max(dp))

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

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

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

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

print(max(dp))

Solution (Python):
from collections import deque
N,M = map(int,input().split())
list_edge = [[] for _ in range(N)]
deg = [0]*N
for _ in range(M):
    a,b = map(int,input().split())
    list_edge[a-1].append(b-1)
    deg[b-1] += 1
que = deque()
for v in range(N):
    if deg[v]==0:
        que.append(v)
dp = [0]*N
while que:
    v = que.popleft()
    list_nv = list_edge[v]
    for nv in list_nv:
        deg[nv] -= 1
        if deg[nv]==0:
            que.append(nv)
            dp[nv] = max(dp[v],dp[v]+1)
print(max(dp))

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

def longest_path(s):
    global dp
    if dp[s-1]<1:
        if edge[s]:
            dp[s-1]=max((longest_path(t)+1)for t in edge[s])
        else:
            dp[s-1]=0
    return dp[s-1]

N,M=map(int,input().split())
edge={}
for i in range(1,N+1):
    edge.setdefault(i,[])
for _ in range(M):
    x,y=map(int,input().split())
    edge[x].append(y)
dp=[0]*N
for i in range(1,N+1):
    if dp[i-1]==0:
        longest_path(i)

print(max(dp))

Solution (Python):
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 lis[v]>=0:
    return lis[v]
  if len(edge[v])==0:
    lis[v] = 1
    return 1
  ans = 0
  for u in edge[v]:
    ans = max(ans, dfs(u))
  lis[v] = ans+1
  return ans+1

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

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

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

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

def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    res = 0
    for nx in G[cur]:
        res = max(res,dfs(nx)+1)
    dp[cur] = res
    return res
    
for i in range(n):
    dp[i] = max(dp[i],dfs(i))

print(max(dp))

Solution (Python):

from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

def func(x, graph, flag, dp):
    if (flag[x]):
        return dp[x]

    flag[x] = 1
    check = 0
    for i in graph[x]:
        check = max(check, func(i, graph, flag, dp) + 1)

    dp[x] = check

    return dp[x]

N, M = [int(i) for i in input().split()]
flag = [0] * (N + 1)
dp = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    temp_x, temp_y = [int(i) for i in input().split()]
    graph[temp_x].append(temp_y)


ans = 0
for i in range(1, N + 1):
    ans = max(ans, func(i, graph, flag, dp))

print(ans)

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







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)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


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")  


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


from sys import setrecursionlimit
setrecursionlimit(1000000)



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

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

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

    print(max(dp))


solve()

Solution (Python):

from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")


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


d = deque()
d_tmp = deque()
x = [-1]
y = [[-1] for _ in range((n + 1))]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    
    y[x_in].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 in y[i][1:]:
            tmp = dp(x_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))

Solution (Python):
from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

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


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

Solution (Python):
from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

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


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

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
XY = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
indeg = [0] * N
for x,y in XY:
    x,y = x-1,y-1
    es[x].append(y)
    indeg[y] += 1

from collections import deque
q = deque()
for i in range(N):
    if indeg[i] == 0:
        q.append(i)

dp = [0] * N
while q:
    v = q.popleft()
    for to in es[v]:
        indeg[to] -= 1
        if indeg[to] == 0: q.append(to)
        dp[to] = max(dp[to], dp[v] + 1)

print(max(dp))

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

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

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

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

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

xy = [[] for i in range(n)]

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

chk = [0]*n
dp = [0]*n



def f(x):
    
    if chk[x] == 1:
        return dp[x]
    fans = 0
    chk[x] = 1
    for i in range(len(xy[x])):
        fans = max(fans,f(xy[x][i])+1)
    dp[x] = fans
    
    return dp[x]

ans = 0

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

print(ans)

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

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

xy = [[] for i in range(n)]

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

chk = [0]*n
dp = [0]*n



def f(x):
    
    if chk[x] == 1:
        return dp[x]
    fans = 0
    chk[x] = 1
    for i in range(len(xy[x])):
        fans = max(fans,f(xy[x][i])+1)
    dp[x] = fans
    
    return dp[x]

ans = 0

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

print(ans)

Solution (Python):
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time

starttime = time.time()

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    
except:
    pass


n,m=L()
A=[L() for i in range(m)]
g=[[] for i in range(n+1)]
for x,y in A:
    g[x].append(y)

vis=[0 for i in range(n+1)]
dp=[-1 for i in range(n+1)]
def rec(v):
    if vis[v]:
        return dp[v]
    best=0
    vis[v]=1
    for neigh in g[v]:
        best=max(best,rec(neigh)+1)
    dp[v]=best
    return best
best=0
for i in range(1,n+1):
    best=max(best,rec(i))
print(best)




endtime = time.time()

Solution (Python):





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



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  

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  
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):  
    if inn == 0:
        q.append((u, 0))

dp = [0] * N
while q:  
    u, l = q.popleft()
    
    dp[u] = l
    for nx in dag[u]:
        indeg[nx] -= 1
        if indeg[nx] == 0:
            q.append((nx, l + 1))
print(max(dp))

Solution (Python):





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



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  

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  
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):  
    if inn == 0:
        q.append((u, 0))

dp = [0] * N
while q:  
    u, l = q.popleft()
    
    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))

Solution (Python):





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



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  

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  
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):  
    if inn == 0:
        q.append(u)

dp = [0] * N
while q:  
    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))

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):

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

Solution (Python):
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()

Solution (Python):
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):
    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)

Solution (Python):
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]

 
dp = [-1] * (N + 1)
 
 
def func(n):
    if dp[n] != -1:
        return dp[n]
    cnt = 0
	
	
    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(max(dp))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):

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]


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


def func(n):
    if dp[n] != -1:
        return dp[n]
    cnt = 0
	
	
    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(max(dp))

Solution (Python):
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)

Solution (Python):
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)]))

Solution (Python):
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))

Solution (Python):
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) 

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)

Solution (Python):


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()  

    
    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()

Solution (Python):
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()