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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = collections.defaultdict(set)
    for _ in range(m):
        x,y = LI()
        e[y].add(x)

    fm = {}
    def f(i):
        if i in fm:
            return fm[i]
        if len(e[i]) == 0:
            fm[i] = 0
            return 0
        r = 0
        for c in e[i]:
            t = f(c)
            if r < t:
                r = t
        fm[i] = r + 1
        return r + 1

    r = 0
    for i in range(1,n+1):
        t = f(i)
        if r < t:
            r = t

    return r


print(main())

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)


def rec(vv):
    if p[vv] >= 0:
        return p[vv]

    res = 0
    for nv in g[vv]:
        res = max(res, rec(nv) + 1)
    p[vv] = res
    return res


N, M = map(int, input().split())
g = [[] for _ in range(N)]
p = [-1 for _ in range(N)]

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

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)


def rec(vv):
    if p[vv] >= 0:
        return p[vv]

    res = 0
    for nv in g[vv]:
        res = max(res, rec(nv) + 1)
    p[vv] = res
    return res


N, M = map(int, input().split())
g = [[] for _ in range(N)]
p = [-1 for _ in range(N)]

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

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)


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

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


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 for _ in range(N)]

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

Solution (Python):
from collections import deque
N, M = map(int, input().split())
X = [[] for i in range(N)] 
Y = [0 for i in range(N)] 
dp = [0 for i in range(N)] 

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


Q = deque([])
for i in range(N):
    if Y[i] == 0:
        Q.append(i)

while len(Q) > 0:
    i = Q.popleft()
    for x in X[i]:
        dp[x] = max(dp[x], dp[i] + 1)
        Y[x] -= 1
        if Y[x] == 0:
            Q.append(x)

print(max(dp))

Solution (Python):
from collections import deque
N, M = map(int, input().split())
X = [[] for i in range(N)] 
Y = [0 for i in range(N)] 
dp = [0 for i in range(N)] 

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


Q = deque([])
for i in range(N):
    if Y[i] == 0:
        Q.append(i)

while len(Q) > 0:
    i = Q.popleft()
    for x in X[i]:
        dp[x] = max(dp[x], dp[i] + 1)
        Y[x] -= 1
        if Y[x] == 0:
            Q.append(x)

print(max(dp))

Solution (Python):
def g_longest_path(N, M, Edges):
    """
    N頂点M辺の有向グラフGが与えられる。Gは有向閉路を含まない。
    Gの有向パスのうち、最長のものについてその長さを求めよ。
    有向パスの長さとは、有向パスに含まれる辺の本数のことをいう。
    """
    import sys
    sys.setrecursionlimit(10**6)

    
    graph = [[] for _ in range(N)]
    for x, y in Edges:
        graph[x - 1].append(y - 1)

    
    
    
    def memorized_recursive(v):
        if dp[v] != -1:
            return dp[v]  

        ret = 0
        
        for nv in graph[v]:
            ret = max(ret, memorized_recursive(nv) + 1)
        dp[v] = ret  
        return ret

    ans = 0
    dp = [-1] * N  
    
    for v in range(N):
        ans = max(ans, memorized_recursive(v))
    return ans

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(g_longest_path(N, M, Edges))

Solution (Python):
import collections
n, m = [int(i) for i in input().split()]
todc = collections.defaultdict(lambda: [])
lendc = collections.defaultdict(lambda: -1)


for k in range(m):
    i, j = [int(n) for n in input().split()]
    todc[j] += [i]


def maxlen(n):
    if len(todc[n]) == 0:
        lendc[n] = 0
        return 0
    else:
        m = 0
        for i in todc[n]:
            if lendc[i] == -1:
                lendc[i] = maxlen(i)
            m = max(m, lendc[i]+1)
        return m
       

def maxlen_stack(org_n):
    stack = [org_n]
    while stack:
        n = stack.pop()
        if lendc[n] != -1:
            continue        
        if len(todc[n]) == 0:
            lendc[n] = 0
        else:
            m = 0
            recursive = []
            for i in todc[n]:
                if lendc[i] == -1:
                    recursive.append(i)
                else:
                    m = max(m, lendc[i]+1)
            if recursive:
                stack += [n] + recursive
            else:
                lendc[n] = m         
    return lendc[org_n]

k = 0
for i in range(1, n+1):
    if lendc[i] == -1:
        
        lendc[i] = maxlen_stack(i)
    k = max(k, lendc[i])
print(k)

Solution (Python):
import collections
n, m = [int(i) for i in input().split()]
todc = collections.defaultdict(lambda: [])
lendc = collections.defaultdict(lambda: -1)


for k in range(m):
    i, j = [int(n) for n in input().split()]
    todc[j] += [i]


def maxlen(n):
    if len(todc[n]) == 0:
        lendc[n] = 0
        return 0
    else:
        m = 0
        for i in todc[n]:
            if lendc[i] == -1:
                lendc[i] = maxlen(i)
            m = max(m, lendc[i]+1)
        return m
       

def maxlen_stack(org_n):
    stack = [org_n]
    while stack:
        n = stack.pop()
        if len(todc[n]) == 0:
            lendc[n] = 0
        else:
            m = 0
            recursive = []
            for i in todc[n]:
                if lendc[i] == -1:
                    recursive.append(i)
                else:
                    m = max(m, lendc[i]+1)
            if recursive:
                stack += [n] + recursive
            else:
                lendc[n] = m         
    return lendc[org_n]

k = 0
for i in range(1, n+1):
    if lendc[i] == -1:
        
        lendc[i] = maxlen_stack(i)
    k = max(k, lendc[i])
print(k)

Solution (Python):
import collections, sys

n, m = map(int, input().split())
pres = collections.defaultdict(list)
nxts = collections.defaultdict(list)
for line in sys.stdin:
    x, y = map(int, line.split())
    pres[y].append(x)
    nxts[x].append(y)

stack, count, nodes = [], [0], []
for node in range(1, n + 1):
    count.append(len(pres[node]))
    if count[node] == 0:
        stack.append(node)

while stack:
    node = stack.pop()
    nodes.append(node)
    for nxt in nxts[node]:
        count[nxt] -= 1
        if count[nxt] == 0:
            stack.append(nxt)

dp = [0] * (n + 1)
for node in nodes:
    for pre in pres[node]:
        dp[node] = max(dp[node], dp[pre] + 1)

print(max(dp))

Solution (Python):
import sys
raw_input = sys.stdin.readline
N,M = map(int,raw_input().split())
paths = [[] for x in range(N)]
inc = [0 for x in range(N)]
for i in range(M):
    a,b = map(int,raw_input().split())
    paths[a-1].append(b-1)
    inc[b-1] += 1
q = []
for i in range(N):
    if not inc[i]:
        q.append(i)
dp = [0 for x in range(N)]
while q:
    c = q.pop(0)
    for i in paths[c]:
        dp[i] = max(dp[i],dp[c]+1)
        inc[i] -= 1
        if not inc[i]:
            q.append(i)
print max(dp)

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

n,m=map(int,input().split())
d={}
dp={}
n=[]

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

def lp(a):
	if a in dp:
		return dp[a]
	if a not in d:
		dp[a]=1
		return 1
	ans=0
	for i in d[a]:
		ans=max(ans,1+lp(i))
	dp[a]=ans
	return ans

p=0
for i in n:
	p=max(p,lp(i))
print(p-1)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

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

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

dp = [0 for _ in range(N)]


def dfs(u):
    if dp[u] != 0 or len(graph[u]) == 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

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

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

dp = [0 for _ in range(N)]


def dfs(u):
    if dp[u] != 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


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

Solution (Python):
from collections import defaultdict, deque
from sys import stdin
N, M = map(int, stdin.readline().split())
x = []
y = []
count_in = defaultdict(int)
graph = [[] for _ in range(N)]
graph = defaultdict(list)
graph_reverse = defaultdict(list)
for _ in range(M):
    tmpx, tmpy = map(int, stdin.readline().split())
    x.append(tmpx-1)
    y.append(tmpy-1)
    graph[tmpx-1].append(tmpy-1)
    graph_reverse[tmpy-1].append(tmpx-1)
    count_in[tmpy-1] += 1
q = deque(v for v in range(N) if count_in[v] == 0)
res = []
while q:
    v = q.popleft()
    res.append(v)
    for v_out in graph[v]:
        count_in[v_out] -= 1
        if count_in[v_out] == 0:
            q.append(v_out)

dp = [0 for _ in range(N)]
dp[0] = 0
point2order = defaultdict(int)
for i in range(N):
    point2order[res[i]] = i
    for v in graph_reverse[res[i]]:
        dp[i] = max(dp[i], dp[point2order[v]]+1)
print(dp[N-1])

Solution (Python):
N,M = map(int,input().split())

E = [[] for _ in range(N)]
rE = [0]*N

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

memo = [0]*N

Q = [x for x in range(N) if not rE[x]]

while Q:
  v = Q.pop()
  m = memo[v]+1
  for u in E[v]:
    memo[u] = max(memo[u], m)
    rE[u] -= 1
    if not rE[u]:
      Q.append(u)

print(max(memo))

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


def dfs(v):
    if cache[v] > -1:
        return cache[v]
    lv = links[v]
    cache[v] = ret = max(map(dfs, lv)) + 1 if lv else 0
    return ret


n, m = map(int, input().split())
links = [set() for _ in range(n)]
cache = [-1] * n
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    links[x - 1].add(y - 1)

print(max(map(dfs, range(n))))

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


def dfs(v):
    if cache[v] > -1:
        return cache[v]
    lv = links[v]
    cache[v] = ret = max(map(dfs, lv)) + 1 if lv else 0
    return ret


n, m = map(int, input().split())
links = [set() for _ in range(n)]
cache = [-1] * n
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].add(y)

print(max(map(dfs, range(n))))

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


def dfs(v):
    if cache[v] > -1:
        return cache[v]
    lv = links[v]
    cache[v] = ret = max(map(dfs, lv)) + 1 if lv else 0
    return ret


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
cache = [-1] * n
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(map(dfs, sss)))

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(map(dfs, lv)) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(map(dfs, sss)))

Solution (Python):

import sys
sys.setrecursionlimit(300000) 

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


visited = [False] * N
topo_order = [] 


def dfs_visit(node):
    global visited, topo_order
    if visited[node]: return
    visited[node] = True
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs_visit(neighbor)
    
    topo_order.append(node)
    


for node in range(N):
    dfs_visit(node)
topo_order = topo_order[::-1]


dp = [0]*N

for node in topo_order:
    for neighbor in adj[node]:
        dp[neighbor] = max(dp[neighbor], dp[node]+1)
print(max(dp))

Solution (Python):
from collections import deque
n,m = map(int,input().split())
g = [[] for i in range(n)]
h = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  h[y].append(x)
topo = []
hukasa = [0] * n
hairu = [0]*n
que = deque([])
for i in range(n):
  hairu[i] = len(h[i])
  if hairu[i] == 0:
    topo.append(i)
    que.append(i)
def dfs(x):
  for i in g[x]:
    hairu[i]-=1
    if hairu[i] == 0:
      topo.append(i)
      que.append(i)
while que:
  x = que.popleft()
  dfs(x)
def dfs2(x):
  for i in g[x]:
    hukasa[i] = max(hukasa[i],hukasa[x]+1)
for i in topo:
  dfs2(i)
print(max(hukasa))

Solution (Python):
from collections import defaultdict
debug = print
def debug(*va): pass

def longest_by_topological_sort(N, nexts, prevs):
    visited = [-1] * N
    max_dist = 0
    que = list(range(N))
    while len(que):
        p = que.pop()
        if visited[p] == -1:
            if all(visited[q] != -1 for q in prevs[p]):
                dist = 0
                for q in prevs[p]:
                    dist = max(dist, visited[q] + 1)
                visited[p] = dist
                max_dist = max(max_dist, dist)
                for n in nexts[p]:
                    que.append(n)
    return max_dist

def test_separate():
    import time
    N = 10**5
    t0 = time.time()
    print(longest_by_topological_sort(N, defaultdict(list), defaultdict(list)))
    print('elapsed', time.time() - t0)

def test_fanout():
    import time
    N = 10**5
    nn, pp = defaultdict(list), defaultdict(list)
    for i in range(1, N):
        nn[0].append(i)
        pp[i].append(0)
    t0 = time.time()
    print(longest_by_topological_sort(N, nn, pp))
    print('elapsed', time.time() - t0)

def test_middle():
    import time
    N = 10**5
    nn, pp = defaultdict(list), defaultdict(list)
    for i in range(1, N):
        
        nn[0].append(i)
        pp[i].append(0)
        
        nn[i].append(1)
        pp[1].append(i)
    t0 = time.time()
    print(longest_by_topological_sort(N, nn, pp))
    print('elapsed', time.time() - t0)

if __name__ == '__main__':
    N, M = map(int, input().split())

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

    max_dist = longest_by_topological_sort(N, nextnodes[0], nextnodes[1])
    print(max_dist)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
memo=[-1]*N
def rec(x):
  if memo[x]>=0:
    return memo[x]
  res=0
  if not G[x]:
    memo[x]=0
    return 0
  for y in G[x]:
    res=max(rec(y),res)
  memo[x]=res+1
  return memo[x]
for i in range(N):
  rec(i)
print(max(memo))

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

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


EDGELIST=[[] for i in range(N+1)]
LEAF=[]
for x,y in EDGE:
    
    EDGELIST[x].append(y)

for i in range(1,N+1):
    if EDGELIST[i]==[]:
        LEAF.append(i)

DIST=[-1]*(N+1)
for l in LEAF:
    DIST[l]=0

def distance(x):
    if DIST[x]!=-1:
        return DIST[x]
    ANS=0
    for to in EDGELIST[x]:
        if ANS<distance(to)+1:
            ANS=distance(to)+1

    DIST[x]=ANS
    return ANS

for i in range(1,N+1):
    DIST[i]=distance(i)

print(max(DIST))

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

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


EDGELIST=[[] for i in range(N+1)]
LEAF=[]
for x,y in EDGE:
    
    EDGELIST[x].append(y)

for i in range(1,N+1):
    if EDGELIST[i]==[]:
        LEAF.append(i)

DIST=[-1]*(N+1)
for l in LEAF:
    DIST[l]=0

def distance(x):
    if DIST[x]!=-1:
        return DIST[x]
    ANS=0
    for to in EDGELIST[x]:
        if ANS<distance(to)+1:
            ANS=distance(to)+1

    DIST[x]=ANS
    return ANS

for i in range(1,N+1):
    DIST[i]=distance(i)

print(max(DIST))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
is_root = [True for _ in range(n)]

for _ in range(m):
	x, y = map(int, input().split())
	edges[x-1].append(y-1)
	rank[y-1] += 1
	is_root[y-1] = False

dp = [0 for _ in range(n)]
def dfs(x):
	global dp
	for c in edges[x]:
		rank[c] -= 1
		dp[c] = max(dp[c], dp[x]+1)
		if rank[c] == 0:
			dfs(c)
	return

for i in range(n):
	if is_root[i]:
		dfs(i)


print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
is_root = [True for _ in range(n)]

for _ in range(m):
	x, y = map(int, input().split())
	edges[x-1].append(y-1)
	rank[y-1] += 1
	is_root[y-1] = False

dp = [0 for _ in range(n)]
def dfs(x):
	global dp
	for c in edges[x]:
		rank[c] -= 1
		dp[c] = max(dp[c], dp[x]+1)
		if rank[c] == 0:
			dfs(c)
	return

for i in range(n):
	if is_root[i]:
		dfs(i)


print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[-1]*N
def f(x):
    if dp[x]!=-1:
        return dp[x]
    if len(table[x])==0:
        return 0
    t=0
    for i in table[x]:
        t=max(t,f(i)+1)
    dp[x]=t
    return t
for i in H:
    f(i)
print(max(dp))

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


dist = [0] * n
checked = [False] * n
def check(x):
  if checked[x]:return dist[x]
  ret = 0
  for fr in rev_edges[x]:
    ret = max(ret, check(fr) + 1)
  dist[x] = ret
  checked[x] = True
  return ret

for i in range(n):
  check(i)
print(max(dist))

Solution (Python):
import sys
sys.setrecursionlimit(300000)
fin = sys.stdin.readline


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    x, y = [int(elem) - 1 for elem in fin().split()]
    adj[x].append(y)

visited = [False] * N
topo_order = []

def dfs_visit(node):
    visited[node] = True
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs_visit(neighbor)
    topo_order.append(node)


for node in range(N):
    dfs_visit(node)
topo_order = topo_order[::-1]

dp = [0] * N
for node in topo_order[:-1]:
    for neighbor in adj[node]:
        dp[neighbor] = max(dp[neighbor], dp[node] + 1)

print(max(dp))

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

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


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


T = topological_sort(G)
dist = [0] * N
for n in T:
    for v in G[n]:
        dist[v] = max(dist[v], dist[n] + 1)

print(max(dist))

Solution (Python):
N,M = map(int,input().split())
es = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

indeg = [0 for i in range(N)]
outdeg = [[] for i in range(N)]
for a,b in es:
    indeg[b] += 1
    outdeg[a].append(b)

heads = []
for i in range(N):
    if indeg[i]: continue
    heads.append(i)

dp = [0] * N
while heads:
    a = heads.pop()
    for b in outdeg[a]:
        indeg[b] -= 1
        if indeg[b] == 0:
            heads.append(b)
        dp[b] = max(dp[b], dp[a] + 1)
print(max(dp))

Solution (Python):
from collections import deque

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

dp = [0] * N
Q = deque([v for v in range(N) if indegs[v] == 0])
while Q:
    vNow = Q.popleft()
    for v2 in adjL[vNow]:
        dp[v2] = max(dp[v2], dp[vNow] + 1)
        indegs[v2] -= 1
        if indegs[v2] == 0:
            Q.append(v2)

print(max(dp))

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
xy = []

ins = [0]*n
graph = [[] for _ in range(n)]

dp = [0]*n
for _ in range(m):
    x,y = li_()
    ins[y] += 1
    graph[x].append(y)
    
stack = []
for i in range(n):
    if ins[i] == 0:
        stack.append(i)

while stack:
    nex_stack = []
    for point in stack:
        for nexp in graph[point]:
            dp[nexp] = max(dp[nexp], dp[point]+1)
            ins[nexp] -= 1
            if ins[nexp] == 0:
                nex_stack.append(nexp)
                
    stack = nex_stack
    
print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    G[x-1].add(y-1)
dp=[-1 for i in range(N)]
def search(k):
    if dp[k]!=-1:
        return dp[k]
    res=0
    for r in G[k]:
        if search(r)+1>res:
            res=search(r)+1
    dp[k]=res
    return res
for i in range(N):
    if dp[i]==-1:
        search(i)
print(max(dp))

Solution (Python):
n, m = map(int, raw_input().split())
graph = [[] for _ in xrange(n)]
ind = [0 for _ in xrange(n)]
outd = [0 for _ in xrange(n)]
used = [False for _ in xrange(n)]
topo = []
cnt = 0

for i in xrange(m):
    u, v = map(int, raw_input().split())
    ind[v-1] += 1
    outd[u-1] += 1
    graph[u-1].append(v-1)
    
for i in xrange(n):
    if ind[i] == 0 and used[i] == False:
        topo.append(i)
        used[i] = True

while cnt < n:
    u = topo[cnt]
    for v in graph[u]:
        ind[v] -= 1
        if ind[v] == 0 and used[v] == False:
            used[v] = True
            topo.append(v)
    cnt += 1
    
dp = [0 for _ in xrange(n)]
for u in topo:
    for v in graph[u]:
        dp[v] = max(dp[v], dp[u] + 1)
res = max(dp)
print res

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

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

memo = [-1]*N
def dfs(v):
    if memo[v] != -1:
        return memo[v]
    memo[v] = r = max(dfs(w) for w in G[v]) + 1 if G[v] else 0
    return r
print(max(dfs(v) for v in range(N)))