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):
import sys
sys.setrecursionlimit(11000)
def util(adj, curr, dp):
    res = 0
    if dp[curr] != -1:
        return dp[curr]
    for next in adj[curr]:
        res = max(res,1 + util(adj, next, dp))
    dp[curr] = res
    return res
 
n, m = map(int, input().strip().split())
adj = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().strip().split())
    adj[x - 1].append(y - 1)
dp = [-1]*n
lp = 0
for i in range(n):
    lp = max(lp, util(adj, i, dp))
print(lp)

Solution (Python):
from collections import deque

def solve(N, M, graph):

	indegree = {n: 0 for n in range(1, N + 1)}
	for node in graph:
		for nei in graph[node]:
			indegree[nei] += 1

	queue = deque()
	for node in graph:
		if indegree[node] == 0:
			queue.append(node)

	lengths = [0] * (N + 1)

	while queue:
		node = queue.popleft()

		for nei in graph[node]:
			indegree[nei] -= 1

			if indegree[nei] == 0:
				queue.append(nei)

			lengths[nei] = max(lengths[nei], lengths[node] + 1)

	return max(lengths)


N, M = [int(s) for s in input().split()]
graph = {}
for n in range(1, N + 1):
	graph[n] = []
for _ in range(M):
	x, y = [int(s) for s in input().split()]
	graph[x].append(y)

print(solve(N, M, graph))

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10000000)


def dfs(node, graph, dist, visited):
    if visited[node] == True:
        return dist[node]
    visited[node] = True
    for child in graph[node]:
        dist[node] = max(dist[node], 1+dfs(child, graph, dist, visited))
    return dist[node]


def main():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
    dist = [0]*(n+1)
    visited = [False]*(n+1)
    for node in range(1, n+1):
        if not visited[node]:
            dfs(node, graph, dist, visited)
    print(max(dist))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
dp = [-1]*(n+1)
path = [[] for i in range(n)]
X = []; Y = []
for i in range(m):
    x, y = map(int, input().split())
    X.append(x-1); Y.append(y-1)
    path[x-1].append(y-1)

def dfs(i):
    if dp[i]>0: return dp[i]
    res = 0
    for k in path[i]:
        res = max(res, dfs(k)+1)
    dp[i] = res
    return res

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

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007



def main():
	
	n, m = IN()
	
	nokori = [0]*n
	max_path_from = [0]*n
	path = []
	tl = [[] for _ in range(n)]
	for _ in range(m):
		f, t = IN()
		f,t=f-1, t-1
		path.append((f,t))
		nokori[t] += 1
		tl[f].append(t)
	sl=[i for i, v in enumerate(nokori) if v == 0]
	mp=0
	while len(sl) > 0:
		next_l = []
		for v in sl:
			for t in tl[v]:
				nokori[t] -= 1
				if nokori[t] == 0:
					next_l.append(t)
		sl = next_l
		mp+=1
	print(mp-1)
		
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m = map(int, input().split())
    E = [[] for _ in range(n)]
    indeg = [0] * n
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        E[u].append(v)
        indeg[v] += 1

    
    stack = [v for v in range(n) if indeg[v] == 0]
    order = []
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in E[v]:
            indeg[nv] -= 1
            if indeg[nv] == 0:
                stack.append(nv)

    dp = [0] * n
    for v in order[::-1]:
        for nv in E[v]:
            dp[v] = max(dp[v], 1 + dp[nv])

    print(max(dp))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  graph[x-1].append(y-1)
dp = [-1]*(n)
 
def dfs(i):
    if dp[i] != -1:
        return dp[i]
    else:
        res = 0
        for j in graph[i]:
            res = max(res,dfs(j)+1)
        dp[i] = res
        return dp[i]
 
for i in range(n):  
    dfs(i)
print(max(dp))

Solution (Python):
from collections import deque


class TPSort:
    """
    トポロジカルソート
    

    
    """

    def __init__(self, N):
        self.N = N
        self.indegree = [0] * N  
        self.length = [0] * N
        self.edges = [[] for _ in range(N)]

    def add_edge(self, a, b):
        self.edges[a].append(b)
        self.indegree[b] += 1

    def sort(self):
        que = deque([i for i in range(self.N) if self.indegree[i] == 0])

        res = []
        while que:
            n = que.popleft()
            res.append(n)
            for next_n in self.edges[n]:
                self.length[next_n] = max(self.length[next_n], self.length[n] + 1)
                self.indegree[next_n] = self.indegree[next_n] - 1  
                if self.indegree[next_n] == 0:  
                    que.append(next_n)
        return res


if __name__ == '__main__':
    n, m = [int(_) for _ in input().split()]
    tp = TPSort(n + 1)

    for i in range(m):
        tp.add_edge(*[int(_) for _ in input().split()])

    tp.sort()
    print(max(tp.length))

Solution (Python):
import sys
sys.setrecursionlimit(100000)

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


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
    Far[x] = r
    return r


for i in range(N):
    long(i)
print(max(Far))

Solution (Python):
N,M=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(M)]
def tsort(N,E):
    c=[[] for i in range(N)]
    t=[0]*N
    for i,j in E:
        c[i].append(j)
        t[j]+=1
    A,B=zip(*E)
    s=set(range(N))-set(B)
    l=[]
    while s:
        n=s.pop()
        l.append(n)
        for i in c[n]:
            t[i]-=1
            if t[i]==0:
                s.add(i)
    return c,l
c,l=tsort(N,[(x-1,y-1) for x,y in XY])
d=[0]*N
for i in l:
    for n in c[i]:
        d[n]=max(d[n],d[i]+1)
print(max(d))

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


def longdist(p, dp_l, out_l):
    if len(out_l[p]) == 0:
        return 0
    for q in out_l[p]:
        if dp_l[q] == -1:
            dp_l[q] = longdist(q, dp_l, out_l)
        dp_l[p] = max(dp_l[p], dp_l[q]+1)
    return dp_l[p]


n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

input, output = [[] for _ in range(n)], [[] for _ in range(n)]
for x, y in xy:
    input[y - 1].append(x - 1)
    output[x - 1].append(y - 1)

dp = [-1] * n
for i in range(n):
    if dp[i] == -1:
        dp[i] = longdist(i, dp, output)

print(max(dp))

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


def longdist(p, dp_l, out_l):
    if len(out_l[p]) == 0:
        return 0
    for q in out_l[p]:
        if dp_l[q] == -1:
            dp_l[q] = longdist(q, dp_l, out_l)
        dp_l[p] = max(dp_l[p], dp_l[q]+1)
    return dp_l[p]


n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

input, output = [[] for _ in range(n)], [[] for _ in range(n)]
for x, y in xy:
    input[y - 1].append(x - 1)
    output[x - 1].append(y - 1)

dp = [-1] * n
for i in range(n):
    if dp[i] == -1:
        dp[i] = longdist(i, dp, output)

print(max(dp))

Solution (Python):

"""
Created on Mon May  4 14:09:04 2020

@author: Kanaru Sato
"""

import sys
sys.setrecursionlimit(10**9)

n,m = list(map(int, input().split()))
thisconnected = [[] for i in range(n+1)]
thismemo = [-1 for i in range(n+1)]

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

def lp(k,memo,connected):
    if memo[k] != -1:
        return memo[k]
    elif not connected[k]:
        memo[k] = 0
        return 0
    else:
        res = -1
        for point in connected[k]:
            if res < lp(point,memo,connected):
                res = lp(point,memo,connected)
        memo[k] = res+1
        return res+1

for i in range(1,n+1):
    if thismemo[i] == -1:
        thismemo[i] = lp(i,thismemo,thisconnected)

print(max(thismemo))

Solution (Python):
'''
N頂点M辺の有向グラフGの有向パスのうち最長のものを求めよ。
terms:
    2<=N<=10**5
    1<=M<=10**5
    (x_i,y_i)はすべて相異なる
    Gは有向閉路を含まない

input:
    4 5
    1 2
    1 3
    3 2
    2 4
    3 4
output:
    3
'''


from collections import defaultdict,deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, m = inpl()
v = [[] for _ in range(n)]
for i in range(m):
    a, b = inpl()
    v[a - 1].append(b - 1)
'''
v[0]=[1,2]
v[1]=[3]
v[2]=[1,3]
'''

from functools import lru_cache
@lru_cache(maxsize=None)
def dp(x):
    r = 0
    for i in v[x]:
        r = max(r, dp(i) + 1)
    return r

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

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

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

memo = [-1] * n

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

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

Solution (Python):
n,m=map(int,input().split())
edge=[[] for i in range(n)]
kara=[]
to=[0]*n
for i in range(m):
  x,y=map(int,input().split())
  edge[x-1].append(y-1)
  to[y-1]+=1
for j in range(n):
  if to[j]==0:
    kara.append(j)
dp=[0]*n
while len(kara):
  go=kara.pop()
  for e in edge[go]:
    to[e]-=1
    if to[e]==0:
      kara.append(e)
    dp[e]=max(dp[e],dp[go]+1)
print(max(dp))

Solution (Python):
from collections import defaultdict, deque
n, m = map(int, input().split())
outs = defaultdict(list)
rv = defaultdict(list)
ins = defaultdict(int)
for i in range(m):
    x, y = map(int, input().split())
    outs[x].append(y)
    rv[y].append(x)
    ins[y] += 1
q = deque(i for i in range(1, n + 1) if ins[i] == 0)
ans = []
while q:
    st = q.popleft()
    ans.append(st)
    for to in outs[st]:
        ins[to] -= 1
        if ins[to] == 0:
            q.append(to)

dp = [0] * (n + 1)
for value in ans:
    dp[value] += max([0]+[dp[i]+1 for i in rv[value]])
print(max(dp))

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

sys.setrecursionlimit(10 ** 6)

n, m = na()
xy = nan(m)

g = [[] for _ in range(n)]
deg = [0] * n
for i in range(m):
    x, y = xy[i]
    x -= 1
    y -= 1
    g[x].append(y)
    deg[y] += 1

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

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

def bfs():
    q = deque()
    for i in range(n):
        if deg[i] == 0:
            q.append(i)
    dp = [0] * n
    while len(q):
        p = q.popleft()
        for v in g[p]:
            deg[v] -= 1
            if deg[v] == 0:
                q.append(v)
                dp[v] = max(dp[v], dp[p] + 1)
    return dp

ans = 0
dp = bfs()
for v in range(n):
    ans = max(ans, dp[v])

print(ans)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

sys.setrecursionlimit(10 ** 6)

n, m = na()
xy = nan(m)

g = [[] for _ in range(n)]
for i in range(m):
    x, y = xy[i]
    x -= 1
    y -= 1
    g[x].append(y)

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

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

ans = 0
for v in range(n):
    ans = max(ans, dfs(v))

print(ans)

Solution (Python):
import sys
N, M = map(int, input().split())
sys.setrecursionlimit(10**5)
E = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)

dp = [-1]*N


def rec(v):
    if dp[v] != -1:
        return dp[v]
    if len(E[v]) == 0:
        dp[v] = 0
        return dp[v]

    for to in E[v]:
        dp[v] = max(dp[v], rec(to)+1)
    return dp[v]


for i in range(N):
    dp[i] = rec(i)
print(max(dp))

Solution (Python):


import sys
from collections import defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    edge = defaultdict(lambda: [])

    memo = [0] * 110000
    done = [False] * 110000

    def dp(v):
        if done[v]:
            return memo[v]
        ans = 0
        for to in edge[v]:
            ans = max(ans, dp(to) + 1)
        done[v] = True
        memo[v] = ans
        return ans

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
  x,y = map(int,input().split())
  graph[x].append(y)
memo = [0]*(n+1)
done = [False]*(n+1)
for i in range(1,n+1):
  if len(graph[i]) == 0:
    done[i] = True
def cnt(i):
  if done[i]:
    return memo[i]
  else:
    l = []
    for j in graph[i]:
      l.append(cnt(j))
    memo[i] = max(l)+1
    done[i] = True
    return memo[i]
ans = [0]*n
for i in range(n):
  ans[i] = cnt(i+1)
print(max(ans))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
  x,y = map(int,input().split())
  graph[x].append(y)
memo = [0]*(n+1)
done = [False]*(n+1)
for i in range(1,n+1):
  if len(graph[i]) == 0:
    done[i] = True
def cnt(i):
  if done[i]:
    return memo[i]
  else:
    l = []
    for j in graph[i]:
      l.append(cnt(j))
    memo[i] = max(l)+1
    done[i] = True
    return memo[i]
ans = [0]*n
for i in range(n):
  ans[i] = cnt(i+1)
print(max(ans))

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(x):
  if z[x]==-1:
  	z[x]=max([f(i) for i in v[x]]+[-1])+1
  return z[x]
n,m=map(int,raw_input().split())
v=[[] for _ in xrange(n)]
for x,y in [map(int,raw_input().split()) for _ in xrange(m)]:
  v[x-1].append(y-1)
z=[-1]*n
for i in xrange(n):
  if z[i]==-1:
    f(i)
print max(z)

Solution (Python):
from collections import defaultdict, deque

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

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
length=defaultdict(int)

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def dfs(node,paths,dp,vis):
    vis[node]=True
    for i in range(0, len(paths[node])):
        if not vis[paths[node][i]]:
            dfs(paths[node][i],paths,dp,vis)
        dp[node]=max(dp[node],1+dp[paths[node][i]])
n,m=map(int,input().split())
paths=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    paths[a].append(b)
dp,vis=[0]*(n+1),[False]*(n+1)
for i in range(1,n+1):
    if not vis[i]:
        dfs(i,paths,dp,vis)
print(max(dp))

Solution (Python):
import sys
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append(y)

dp = [-1]*n

def DFS(node):
    ma = -1
    for c_node in graph[node]:
        if dp[c_node]>=0:
            tmp = dp[c_node]
        else:
            tmp = DFS(c_node)
        if tmp > ma:
            ma = tmp
    dp[node] = ma+1
    return ma+1

sys.setrecursionlimit(10**9)

for i in range(n):
    if dp[i]>=0:
        continue
    DFS(i)
print(max(dp))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
dst = [[] for _ in range(N)]
src = [[] for _ in range(N)]
for i in range(M):
    x, y = [int(z) - 1 for z in readline().split()]
    dst[x].append(y)
    src[y].append(x)


def solve():
    nodes = []
    nindex = [-1] * N

    def topsort(i):
        res = []
        if nindex[i] != -1:
            return
        for j in src[i]:
            topsort(j)
        nindex[i] = len(nodes)
        nodes.append(i)

    for i in range(N):
        topsort(i)
    dp = [0] * N
    dpi = [None] * N
    for i in range(N):
        node = nodes[i]
        plen = 0
        mj = None
        for j in src[node]:
            k = nindex[j]
            
            if plen < dp[k] + 1:
                plen = dp[k] + 1
                mj = j
        
        dp[i] = plen
        dpi[i] = mj
    return max(dp)


if __name__ == "__main__":
    print(solve())

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
dst = [[] for _ in range(N)]
src = [[] for _ in range(N)]
for i in range(M):
    x, y = [int(z) - 1 for z in readline().split()]
    dst[x].append(y)
    src[y].append(x)


def solve():
    nodes = []
    nindex = [-1] * N

    def topsort(i):
        res = []
        if nindex[i] != -1:
            return
        for j in src[i]:
            topsort(j)
        nindex[i] = len(nodes)
        nodes.append(i)

    for i in range(N):
        topsort(i)
    dp = [0] * N
    dpi = [None] * N
    for i in range(N):
        node = nodes[i]
        plen = 0
        mj = None
        for j in src[node]:
            k = nindex[j]
            
            if plen < dp[k] + 1:
                plen = dp[k] + 1
                mj = j
        
        dp[i] = plen
        dpi[i] = mj
    return max(dp)


if __name__ == "__main__":
    print(solve())

Solution (Python):
import collections
import sys
sys.setrecursionlimit(10**5)
N, M = map(int, input().split())
G = [set() for i in range(N)]
L = [-1]*N


def solve(x, r):
    if L[x] >= 0:
        return(L[x])
    res = 0
    for z in G[x]:
        if r[z]:
            r[z] = False
            res = max(res, solve(z, r) + 1)
        else:
            res = max(res, L[z]+1)
    L[x] = res
    return(res)


for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1

    G[x].add(y)

r = [True]*N

for i in range(N):
    
    if r[i]:
        L[i] = solve(i, r)
print(max(L))

Solution (Python):
from collections import defaultdict, deque

int1 = lambda x: int(x) - 1


def topological_sort(N, G):
    outs = defaultdict(list)
    ins = defaultdict(int)
    for v1, v2 in G:
        outs[v1].append(v2)
        ins[v2] += 1

    q = deque(v1 for v1 in range(N) if ins[v1] == 0)
    while q:
        v1 = q.popleft()
        yield v1
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append(v2)


N, M = map(int, input().split())
G = [tuple(map(int1, input().split())) for _ in range(M)]
dp = [-1] * (N + 1)  

parents = [[N] for _ in range(N)]
for v1, v2 in G:
    parents[v2].append(v1)
for x in topological_sort(N, G):
    dp[x] = max(dp[p] for p in parents[x]) + 1
print(max(dp))

Solution (Python):

from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

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

dp = [0 for _ in range(n)]
q = deque([])


for i in range(n):
    if indeg[i] == 0:
        q.append(i)

while q:
    v = q.popleft()
    for w in g[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            q.append(w)
            dp[w] = max(dp[w], dp[v] + 1)

print(max(dp))

Solution (Python):
N, M = map(int,raw_input().split())
gra = [set() for n in range(N)]
ins = [0] * N

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  ins[y-1] += 1
  start.discard(y-1)

mem = [None for n in range(N)]
q = list(start)
for i in q : mem[i] = 0

longest = 0
while q :
  cur = q.pop(0)
  for nxt in gra[cur] :
    ins[nxt] -= 1
    if ins[nxt] == 0 :
      mem[nxt] = mem[cur] + 1
      longest = max(longest, mem[nxt])
      q.append(nxt)

print longest

Solution (Python):
import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
G = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
DP = [None for i in range(n)]
def dp(i):
    if DP[i] != None:
        return DP[i]
    ret = 0
    for j in G[i]:
        ret = max(ret, dp(j)+1)
    DP[i] = ret
    return ret
print(max([dp(i) for i in range(n)]))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs(v):
    if(dp[v]==-1):
        dp[v]=0
        for nv in G[v]:
            dp[v]=max(dp[v],dfs(nv)+1)
    return dp[v]
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
dp=[-1]*N
res=-1
for v in range(N):
    res=max(res,dfs(v))
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs(v):
    seen[v]=1
    for nv in G[v]:
        if seen[nv]:
            continue
        dfs(nv)
    topo.append(v)

N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
seen=[0]*N
topo=[]
for i in range(N):
    if not seen[i]:
        dfs(i)
dp=[0]*N
for v in reversed(topo):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write

INF=int(10e9)


n,m=mdata()
dp=[0]*n
g=[set() for i in range(n)]
par=[i for i in range(n)]
chl=[0]*n
for i in range(m):
    x,y=mdata()
    g[x-1].add(y-1)
    chl[y-1]=1
vis=[0]*n
for i in range(n):
    if chl[i]==0:
        s1=deque()
        s1.append(i)
        while s1:
            a=s1[-1]
            if vis[a]==1:
                if a!=i:
                    dp[par[a]]=max(dp[par[a]],dp[a]+1)
                s1.pop()
                continue
            vis[a]=1
            for j in g[a]:
                if vis[j]==0:
                    s1.append(j)
                    par[j]=a
                else:
                    dp[a]=max(dp[a],dp[j]+1)
print(max(dp))

Solution (Python):


import sys

sys.setrecursionlimit(10**5+10)

input = sys.stdin.readline

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

dp = [-1]*N
adg_list = [ [] for _ in range(N)]

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




def rec(v):
    if dp[v] !=-1:
        return dp[v]
    
    nv_s = adg_list[v]

    ans = 0
    
    
    for nv in nv_s:
        ans = max(ans , rec(nv) + 1)
    dp[v] = ans
    return dp[v]

ans = 0
for w in range(N):
    ans =max(ans,rec(w))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
dpv = [-1]*N

def dp(v):
    if dpv[v] != -1:
        return dpv[v]
    if len(edge[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in edge[v]:
        res = max(dp(w),res)
    res += 1
    dpv[v] = res
    return res

def solve():
    for i in range(N):
        dp(i)
    ans = max(dpv)
    
    return ans
print(solve())

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def check(v):
    if dp[v] != -1:
        return dp[v]
    if graph[v]:
        dp[v] = max(check(u) for u in graph[v]) + 1
    else:
        dp[v] = 0
    return dp[v]


print(max(check(v) for v in range(1, n + 1)))

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

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    
    return ans
print(solve(edge))

Solution (Python):
import sys
from collections import defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    V, E = map(int, input().split())
    is_visited = [False] * V
    indeg = [0] * V  
    
    G = defaultdict(lambda: [])

    for i in range(E):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        G[s].append(t)
        indeg[t] += 1

    
    out = []
    dp = [0] * V

    def bfs(s):
        q = deque()
        q.append(s)
        is_visited[s] = True
        while q:
            u = q.popleft()
            out.append(u)
            
            for v in G[u]:
                indeg[v] -= 1
                
                if indeg[v] == 0 and (not is_visited[v]):
                    q.append(v)
                    is_visited[v] = True

    def topological():
        for u in range(V):
            if indeg[u] == 0 and (not is_visited[u]):
                bfs(u)

        

    topological()

    for i in out:
        for dest in G[i]:
            dp[dest] = max(dp[dest], dp[i] + 1)

    print(max(dp))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)

V, M = map(int,input().split())
L = [[] for _ in range(V+1)]
DP = [-1 for _ in range (V + 2)]
for _ in range(M):
    x,y = map(int,input().split())
    L[x-1].append(y-1)

def rec(v):
    if DP[v] != -1: return DP[v]
    ret = 0
    for x in L[v]:
        ret = max(ret,rec(x)+1)
    DP[v] = ret
    return DP[v]
ans = 0
for i in range(V):
    ans = max(ans, rec(i))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)

V, M = map(int,input().split())
L = [[] for _ in range(V+1)]
DP = [-1 for _ in range (V + 2)]
for _ in range(M):
    x,y = map(int,input().split())
    L[x-1].append(y-1)

def rec(v):
    if DP[v] != -1: return DP[v]
    ret = 0
    for x in L[v]:
        ret = max(ret,rec(x)+1)
    DP[v] = ret
    return DP[v]
ans = 0
for i in range(V):
    ans = max(ans, rec(i))
print(ans)

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
inf = float("inf")

n_vertices, m_edges = map(int, input().split())
edges = [[] for _ in range(n_vertices)]

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






def rec(v):
    if dp[v] != -1:
        
        return dp[v]
    for v_adj in edges[v]:
        dp[v] = max(dp[v], rec(v_adj) + 1)
    return dp[v]


dp = [-1 for _ in range(n_vertices)]
res = 0
for v in range(n_vertices):
    res = max(res, rec(v))

print(res + 1)

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

N,M = map(int,input().split())
p = [list(map(int,input().split())) for _ in range(M)]
dp = [-1]*N
ip = [[] for _ in range(N)]
for i in range(M):
  ip[p[i][1]-1].append(p[i][0]-1)




def maxpath(i):
  if dp[i] != -1:
    return dp[i]
  a = 0
  for el in ip[i]:
    a = max(a,maxpath(el)+1)
  dp[i] = a
  return a
  
for i in range(N):
  maxpath(i)

print(max(dp))

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
z = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    z[x-1].append(y-1)






visited = [False] * N
memo = [0] * N

def dp(v):
    if visited[v]:
        return memo[v]
    else:
        res = 0
        for u in z[v]:
            res = max(res, dp(u)+1)
        memo[v] = res
        visited[v] = True
        return res
for i in range(N):
    dp(i)

print(max(memo))