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):
N,M = map(int, input().split())
E = [[] for _ in range(N)]
E2 = [[] for _ in range(N)]
d = [0]*N
for _ in range(M):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E2[y-1].append(x-1)
    d[y-1] += 1

from collections import deque

tpsort = [v for v in range(N) if len(E2[v]) == 0]
q = deque(tpsort)
while q:
    t = q.popleft()
    for v in E[t]:
        d[v] -= 1
        if d[v] == 0:
            q.append(v)
            tpsort.append(v)

dp = [0]*N
for v in tpsort:
    for par in E2[v]:
        dp[v] = max(dp[v], dp[par]+1)

print(max(dp))

Solution (Python):
from sys import stdin, exit, setrecursionlimit
setrecursionlimit(100000000)

input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())
si = lambda: input().strip('\n')
ssi = lambda: input().strip('\n').split()


def dfs(node):
    if len(graph[node]) == 0:
        dp[node] = 0
        return 0
    if dp[node] != -1: return dp[node]
    ans = 0
    for i in graph[node]:
        ans = max(ans, dfs(i)+1)
    dp[node] = ans
    return ans


n, m = mi()
graph= [[] for i in range(n+1)]
for i in range(m):
    a, b = mi()
    graph[a].append(b)
dp = [-1]*(n+1)
for i in range(1, n+1):
    if dp[i] == -1:
        dfs(i)
print(max(dp))

Solution (Python):
import math
import sys
import collections
import sys

sys.setrecursionlimit(200000)




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

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

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


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

qs = [ list(map(int,input().split(" "))) for _ in range(M)]


di = collections.defaultdict(lambda :[])
for q in qs:
    x,y = q
    di[x].append(y)
    

for i in range(N + 1):
    rec(i)
print(max(dp))

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

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

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


dp = [-1] * N

def rec_calc_depth(i):
  global dp
  if dp[i] >= 0:
    return dp[i]
  else:
    children = graph[i]
    depth = 0
    for child in children:
      depth = max(depth, rec_calc_depth(child)+1)
    
    dp[i] = depth
    return depth

ans = 0
for i in range(N):
  ans = max(ans, rec_calc_depth(i))

print(ans)

Solution (Python):
from collections import deque

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

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


depth = [0] * N
d = deque([i for i in range(N) if not to_this[i]])
while d:
  l = len(d)
  for i in range(l):
    node = d.popleft()
    children = graph[node]
    for child in children:
      to_this[child] -= 1
      if not to_this[child]:
        d.append(child)
        depth[child] = depth[node] + 1

print(max(depth))

Solution (Python):
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
edges = [[] for _ in range(n)]
edges2 = [0] * n

dis = [0] * n

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

q = []

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

while q:
    l = q.pop(0)
    for i in edges[l]:
        dis[i] = max(dis[i], dis[l] + 1)
        edges2[i] -= 1
        if edges2[i] == 0:
            q.append(i)

print(max(dis))

Solution (Python):
import sys
input = sys.stdin.readline

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

dis = [0] * n

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

q = []

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

while q:
    l = q.pop(0)
    for i in edges[l]:
        dis[i] = max(dis[i], dis[l] + 1)
        edges2[i].remove(l)
        if not edges2[i]:
            q.append(i)

print(max(dis))

Solution (Python):
import sys
input = sys.stdin.readline

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

dis = [0] * n

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

q = []

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

while q:
    l = q.pop(0)
    for i in edges[l]:
        dis[i] = max(dis[i], dis[l] + 1)
        edges2[i].remove(l)
        if not edges2[i]:
            q.append(i)

print(max(dis))

Solution (Python):
from collections import defaultdict, deque


def longest_path(n, edges):
    adj_list = defaultdict(list)
    for x, y in edges:  
        adj_list[y].append(x)

    state = [0] * n
    distances = [0] * n
    stack = deque(range(n))

    while stack:
        x = stack.pop()
        if state[x] == 0:
            state[x] = 1
            stack.append(x)
            stack.extend(adj_list[x])
        elif state[x] == 1:
            state[x] = 2
            if adj_list[x]:
                distances[x] = max(distances[y] for y in adj_list[x]) + 1

    return max(distances)


def main():
    n, m = [int(x) for x in input().split()]
    edges = [None] * m
    for i in range(m):
        edges[i] = [int(x) - 1 for x in input().split()]

    return longest_path(n, edges)


print(main())

Solution (Python):
from collections import deque
n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

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

for x, y in xy:
    graph[y-1].append(x-1)
    out_deg[x-1] += 1

stack = deque([i for i in range(n) if out_deg[i] == 0])

while stack:
    node = stack.popleft()
    for i in graph[node]:
        dp[i] = max(dp[i], dp[node]+1)
        out_deg[i] -= 1
        if out_deg[i] == 0:
            stack.append(i)

print(max(dp))

Solution (Python):
from collections import deque
n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

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

for x, y in xy:
    graph[y-1].append(x-1)
    out_deg[x-1] += 1

stack = deque([i for i in range(n) if out_deg[i] == 0])

while stack:
    node = stack.popleft()
    for i in graph[node]:
        dp[i] = max(dp[i], dp[node]+1)
        out_deg[i] -= 1
        if out_deg[i] == 0:
            stack.append(i)

print(max(dp))

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

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

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

dp = [0]*N


def dist(v):
    if dp[v] > 0:
        return dp[v]
    dp[v] = 0
    for nv in h[v]:
        dp[v] = max([dp[v], dist(nv)+1])
    return dp[v]


ans = 0
for v in range(N):
    ans = max([ans, dist(v)])

print(ans)

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):
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 = [-1 for _ in range(n)]


def LP(v):
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for w in g[v]:
        ans = max(ans, LP(w)+1)
    dp[v] = ans
    return dp[v]


for i in range(n):
    LP(i)

print(max(dp))

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

vs = set()
dvs = [0 for _ in range(N+1)]
def dfs_w(v, d):
    
    stack = [v]
    path = []
    cd=ld= 0
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v in vs:
            p = stack.pop()
            dvs[-p] = max(dvs[-p], dvs[v]+1)
            continue
        if v < 0:
            c = path.pop()
            dvs[-v] = max(dvs[-v], dvs[c]+1)
            cd -= 1
        else:
            vs.add(v)
            path.append(v)
            ld = max(ld, cd)
            cd += 1
            for u in d[v]:
                stack += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    d[a].add(b)

for i in range(N):
    i += 1
    if i in vs:
        continue
    dfs_w(i, d)
print(max(dvs))

Solution (Python):
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def zrob_listy_sadziedztwa(lista): 
    listy_sasiedzitwa = {}
    for x, y in lista: 
        listy_sasiedzitwa[x] = []
        listy_sasiedzitwa[y] = []
    for x, y in lista: 
        listy_sasiedzitwa[y].append(x)
    return listy_sasiedzitwa

def wyjscie_do_szkoly_bfs(lista_zasad): 
    zasady = {}
    ile_niespelnionych = {}
    for rzecz1,rzecz2 in lista_zasad: 
        zasady[rzecz1] = [] 
        zasady[rzecz2] = []
        ile_niespelnionych[rzecz1] = 0 
        ile_niespelnionych[rzecz2] = 0
    for rzecz1, rzecz2 in lista_zasad: 
        zasady[rzecz1].append(rzecz2)
        ile_niespelnionych[rzecz2] += 1
    kolejnosc_ubioru = [rzecz for rzecz in zasady if ile_niespelnionych[rzecz] == 0]
    nr_przegladnanego = 0
    while nr_przegladnanego < len(kolejnosc_ubioru): 
        for ubranie in zasady[kolejnosc_ubioru[nr_przegladnanego]]: 
            ile_niespelnionych[ubranie] -= 1
            if ile_niespelnionych [ubranie] == 0:
                kolejnosc_ubioru.append(ubranie)
        nr_przegladnanego += 1
    if len(kolejnosc_ubioru) != len(zasady): 
        raise Exception('Nie można się ubrać Skurwysynu')
    return kolejnosc_ubioru 

def longest_patch(): 
    N, M = wczytaj_liste()
    lista_krawedzi = []
    for i in range(M): 
        x, y = wczytaj_liste()
        lista_krawedzi.append((x,y))
    listy_krawedzi = zrob_listy_sadziedztwa(lista_krawedzi)
    kolejnosc = wyjscie_do_szkoly_bfs(lista_krawedzi)
    najdluzsze_drogi = {}
    for wierzcholek in kolejnosc: 
        if len(listy_krawedzi[wierzcholek]) == 0: 
            najdluzsze_drogi[wierzcholek] = 0
        else: 
            maksimum = 0 
            for x in listy_krawedzi[wierzcholek]: 
                if najdluzsze_drogi[x]> maksimum:
                      maksimum = najdluzsze_drogi[x]
            najdluzsze_drogi[wierzcholek] = maksimum + 1
    najdluzsza = 0 
    for a_chuj_wie_co in najdluzsze_drogi: 
        if najdluzsze_drogi[a_chuj_wie_co] > najdluzsza:
            najdluzsza = najdluzsze_drogi[a_chuj_wie_co]
    print (najdluzsza)

longest_patch()

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

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

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

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

def get_longest(x):
    global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)


def dfs(v, graph, memo):
    if memo[v] != -1:
        return memo[v]
    ret = 0
    for c in graph[v]:
        ret = max(ret, dfs(c, graph, memo) + 1)
    memo[v] = ret
    return ret


def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        graph[x].append(y)
    memo = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, dfs(i, graph, memo))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import defaultdict
from collections import deque

INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))


def Topological_sorting(g):
    in_deg = [0]*g.N
    for i in range(g.N):        
        for to_, _ in g.E[i]:
            in_deg[to_] += 1

    ans = [v for v in range(g.N) if in_deg[v] == 0]
    deq = deque(ans)

    while deq:                  
        v = deq.popleft()
        for t, _ in g.E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
                deq.append(t)
    if len(ans) != g.N:
        return False
    return ans


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)

    tsg = Topological_sorting(g)

    DP = [0]*N
    for i in tsg:
        for to, _ in g.E[i]:
            DP[to] = max(DP[i]+1, DP[to])
    print(max(DP))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    x = [int()] * (M)  
    y = [int()] * (M)  
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def calc(dp,adj,i):
    if(len(adj[i])==0):
        dp[i]=0
    elif dp[i]>0:
        return dp[i]
    else:
        for j in adj[i]:
            dp[i]=max(dp[i],calc(dp,adj,j))
        dp[i]+=1
    return dp[i]
n,m=map(int,input().split())
adj=[]
for i in range(n+1):
    adj.append([])
for i in range (m):
    x,y=map(int,input().split())
    adj[x].append(y)
dp=[-1]*(n+1);
for i in range(1,n+1):
    calc(dp,adj,i)
print(max(dp))

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

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

_map = {}
for i in range(n):
    _map[i+1] = []

for i in range(m):
    [x1, y1] = map(int, input().split())

    _map[y1].append(x1)

_memo = {}

def lpath(vertex):
    if vertex in _memo:
        return _memo[vertex]

    if len(_map[vertex]) == 0:
        return 0
    else:
        _max = 0
        for nv in _map[vertex]:
            
            x = lpath(nv)
            if (x > _max):
                _max = x

        _memo[vertex] = _max + 1
        return _max + 1

global_longest_path = 0
for i in range(n):
    longest_path_to_cur_node = lpath(i + 1)
    if global_longest_path < longest_path_to_cur_node:
        global_longest_path = longest_path_to_cur_node

print(global_longest_path)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

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

graph = [[] for _ in range(N)]
out_deg = [0]*N
for x, y in xy:
    graph[y-1].append(x-1)
    out_deg[x-1] += 1


dp = [0]*N
stack = deque([i for i in range(N) if out_deg[i]==0])
while stack:
    node = stack.popleft()
    for child in graph[node]:
        dp[child] = max(dp[child], dp[node]+1)
        out_deg[child] -= 1
        if out_deg[child] == 0:
            stack.append(child)
    
print(max(dp))

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


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

tree = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)

set_ = set([])
for i in range(n):
    for j in tree[i]:
        set_.add(j)

start = set([])
for i in range(n):
    if i not in set_:
        start.add(i)

memo = {}
dp = [0]*n

def solve(pos):
    if pos in memo:
        return memo[pos]
    if len(tree[pos]) == 0:
        memo[pos] = 0
        return memo[pos]

    tmp = 0
    for next_pos in tree[pos]:
        tmp = max(solve(next_pos) + 1, tmp)
    memo[pos] = tmp
    return memo[pos]

for i in range(n):
    solve(i)
ans = 0
for i in memo:
    ans = max(ans, memo[i])
print(ans)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

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

edge = [[] for i in range(N)]


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


outs = deque([V for V in range(N) if ins[V] == 0])


dp = [0] * N


while outs:
    i = outs.pop()
    
    
    for j in edge[i]:
        ins[j] -= 1
        if ins[j] == 0:
            outs.append(j)
        dp[j] = max(dp[j], dp[i]+1)

print(max(dp))

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

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

dp = [-1 for k in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [0] * (N + 1)
e = dd(list)
inc = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  inc[v] += 1
def topologically(n, e, inc):
  res = []
  s = []
  c = 0
  many = 0
  for i in range(1, n + 1):
    if inc[i] == 0:
      s.append(i)
      c += 1
  many = c > 1
  while len(s):
    p = s.pop()
    res.append(p)
    for q in e[p]:
      inc[q] -= 1
      if inc[q] == 0:
        s.append(q)
    many = many or ((len(s) - c) > 0)
    c = len(s)
  return res + [many]
res = topologically(N, e, inc)
for x in range(N):
  i = res[x]
  for q in e[i]:
    dp[q] = max(dp[q], dp[i] + 1)
print(max(dp))

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

N,M = map(int, input().split())
edges = [[] for i in range(N)]
while M:
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    M -= 1

dp = [-1] * N
def dist(vertex):
    if dp[vertex] != -1:
        return dp[vertex]
    
    res = 0
    for to in edges[vertex]:
        res = max(res, dist(to) + 1)
    
    dp[vertex] = res
    return  res

ans = 0
for i in range(N):
    ans = max(ans, dist(i))
print(ans)

Solution (Python):
from sys import stdin,stdout
from collections import defaultdict
d,nbr = defaultdict(list),defaultdict(list)

def topological(inDeg,n,d):
    q,topOrder = [],[]
    vis = [ False for i in range(n+1)]
    for i in range(1,n+1):
        if inDeg[i]==0:
            q.append(i)
            vis[i] = True
    while len(q)>0:
        top = q.pop(0)
        topOrder.append(top)
        for x in d[top]:
            inDeg[x]-=1
            if inDeg[x]==0:
                q.append(x)
                vis[x]=True
    return topOrder


n, m = map(int,stdin.readline().split())
E = []
inDeg = [ 0 for i in range(n+1)]
for i in range(m):
    x,y = map(int,stdin.readline().split())
    E.append([x,y])
    inDeg[y]+=1
    d[x].append(y)

order = topological(inDeg,n,d)
for k,v in zip(d.keys(),d.values()):
    for x in v:
        nbr[x].append(k)


dp = [ 0 for i in range(n+1) ]
for x in order:
    if len(nbr[x])>0:
        for near in nbr[x]:
            dp[x] = max(dp[x],dp[near]+1)

print(max(dp))

Solution (Python):



def main():
    from sys import setrecursionlimit

    setrecursionlimit(10 ** 7)

    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    dp = [-1 for _ in range(n)]

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

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

        result = 0

        for next_v in graph[v]:
            result = max(result, rec(next_v) + 1)

        dp[v] = result

        return dp[v]

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def topological_sort(N,lst_ab):
    a_to_b=[[] for i in range(n+1)]
    b_from_a=[0]*(n+1)
    for A,B in lst_ab:
        a_to_b[A].append(B)
        b_from_a[B]+=1
    flag=[0]*(n+1)
    ans=[]
    for i in range(1,n+1):
        if b_from_a[i]==0 and flag[i]==0:
            flag[i]=1
            ans.append(i)
            que=[i]
            while que:
                h=que.pop()
                for u in a_to_b[h]:
                    b_from_a[u]-=1
                    if flag[u]==0 and b_from_a[u]==0:
                        flag[u]=1
                        ans.append(u)
                        que.append(u)
    if len(ans)==N: return ans
    else: return False
n,m=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(m)]
h=topological_sort(n,xy)
data=[[] for i in range(n+1)]
for x,y in xy:
    data[x].append(y)
lst=[0]*(n+1)
for u in h:
    for v in data[u]:
        lst[v]=max(lst[v],lst[u]+1)
print(max(lst))

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

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

dp = [-1] * N
def dist(v):
  if dp[v] != -1: return dp[v]
  
  res = 0
  for to in edge[v]:
    res = max(res, dist(to) + 1)
  
  dp[v] = res
  return res

ans = 0
for i in range(N):
  ans = max(ans, dist(i))

print(ans)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
F = {i:[] for i in range(1,N+1)}
for _ in range(M):
    y,x = map(int,input().split())
    G[x].append(y)
    F[y].append(x)
A = []
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    s = i
    if hist[s]==1:continue
    if G[s]:
        while G[s]:
            s = G[s][0]
    que = deque([s])
    A.append(s)
    hist[s] = 1
    while que:
        x = que.popleft()
        for y in F[x]:
            if hist[y]==0:
                G[y].remove(x)
                if len(G[y])==0:
                    que.append(y)
                    A.append(y)

                    hist[y]=1

dp = [0 for _ in range(N+1)]
for i in range(N-1):
    for x in F[A[i]]:
        dp[x] = max(dp[x],dp[A[i]]+1)
print(max(dp))

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

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(N)]
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x-1].append(y-1)


    dp=[0]*(N)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if not dic[frm]:
            return 0

        dp[frm]=max(dfs(val)+1 for val in dic[frm])

        return dp[frm]

    mx=0
    return max(dfs(x) for x in range(N))


print(main())

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

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(N)]
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x-1].append(y-1)


    dp=[0]*(N)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if not dic[frm]:
            return 0

        for val in dic[frm]:
            mx=max(mx,dfs(val)+1)

        dp[frm]=mx
        return mx

    mx=0
    for key in range(N):
        mx=max(mx,dfs(key))

    return mx

print(main())

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

class Graph:
    def __init__(self, N):
        self.in_degree = [0] * (N+1)
        self.dist = [0] * (N+1)
        self.visited = [False] * (N+1)
        self.edges = defaultdict(list)
        self.N = N

    def add_edge(self, x, y):
        self.edges[x].append(y)
        self.in_degree[y] += 1

    def dfs(self, x):
        self.visited[x] = True
        for y in self.edges[x]:
            self.dist[y] = max(self.dist[y], self.dist[x] + 1)
            self.in_degree[y] -= 1
            if self.in_degree[y] == 0:
                self.dfs(y)

    def longest_path(self):
        for i in range(1, self.N+1):
            if not self.visited[i] and self.in_degree[i] == 0:
                self.dfs(i)

        ans = 0
        for i in range(1, self.N+1):
            ans = max(ans, self.dist[i])

        return ans


def main():
    N, M = map(int, input().split())
    graph = Graph(N)
    for _ in range(M):
        x, y = map(int, input().split())
        graph.add_edge(x, y)

    ans = graph.longest_path()
    print(ans)


if __name__ == "__main__":
    main()

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

from collections import defaultdict



class Graph:

    def __init__(self, N):
        self.graph = defaultdict(list)
        self.N = N
        self.memo = [-1] * (N+1)
        self.tovisit = set(range(1, N+1))

    def add_edge(self, x, y):
        self.graph[x].append(y)

    def _longest_path(self, node):
        if self.memo[node] == -1:
            res = 0
            for y in self.graph[node]:
                res = max(res, 1 + self._longest_path(y))

            self.memo[node] = res
            self.tovisit.discard(node)

        return self.memo[node]

    def longest_path(self):
        while self.tovisit:
            self._longest_path(self.tovisit.pop())

        res = 0
        for i in range(1, self.N+1):
            res = max(res, self.memo[i])

        return res


def main():

    N, M = map(int, input().split())
    graph = Graph(N)
    for _ in range(M):
        x, y = map(int, input().split())
        graph.add_edge(x, y)

    ans = graph.longest_path()
    print(ans)


if __name__ == "__main__":
    main()