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())
xys = [list(map(int, input().split())) for _  in range(M)]

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

has_no_parent = [True] * N
has_no_child = [True] * N
for x, y in xys:
    has_no_child[x-1] = False
    has_no_parent[y-1] = False

dp = [None] * N
for node in range(N):
    if has_no_child[node]:
        dp[node] = 0

for node in range(N):
    if dp[node] is not None:
        continue
    stack = []
    stack.append(node)
    while stack:
        parent = stack[-1]
        all_children_defined = True
        for child in children[parent]:
            if dp[child] is None:
                stack.append(child)
                all_children_defined = False
        if all_children_defined:
            stack.pop()
            dp[parent] = max([dp[child] + 1 for child in children[parent]])

print(max(dp))

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

dp = [-1] * N

def chdp(x):
    if dp[x] != -1:
        return(dp[x]) 
    dp[x] = 0
    for t in path[x]:
        dp[x] = max(dp[x], chdp(t)+1)
    return(dp[x])

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

print(max(dp))

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

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

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

has_no_parent = [True] * N
has_no_child = [True] * N
for x, y in xys:
    has_no_child[x-1] = False
    has_no_parent[y-1] = False

lp = [None] * N
for node in range(N):
    if has_no_child[node]:
        lp[node] = 0

def dp(node):
    if lp[node] is not None:
        return lp[node]
    result = max([dp(child) + 1 for child in children[node]])
    lp[node] = result
    return result

for node in range(N):
    if lp[node] is None:
        dp(node)

print(max(lp))

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

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

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

has_no_parent = [True] * N
has_no_child = [True] * N
for x, y in xys:
    has_no_child[x-1] = False
    has_no_parent[y-1] = False

lp = [None] * N
for node in range(N):
    if has_no_child[node]:
        lp[node] = 0

def dp(node):
    if lp[node] is not None:
        return lp[node]
    result = max([dp(child) + 1 for child in children[node]])
    lp[node] = result
    return result

for node in range(N):
    if lp[node] is None:
        dp(node)

print(max(lp))

Solution (Python):
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce

sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))




def dfs(i):
    visited[i] = True
    for node in g[i]:
        if not visited[node]:
            dfs(node)
        dp[i] = max(dp[i], 1+ dp[node])



if __name__ == "__main__":
    n, m = rinput()
    g = defaultdict(list)
    for i in range(m):
        x, y = rinput()
        g[x].append(y)
    dp = [0]*(n+1)
    visited = [False]*(n+1)
    for i in range(1, n+1):
        if not visited[i]:
            dfs(i)
            
    
    print(max(dp))

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

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

visited = [False]*n
calculated = [False]*n
dp = [1]*n

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1 
        return dp[v]
    visited[v] = True
    for u in to[v]: 
        res = dfs(u)
        if res == -1: return -1 
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]

def main():
    for i in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        to[a].append(b)
    ans = 0
    for i in range(n):
        res = dfs(i)
        ans = max(ans, res)
    print(ans-1)
    return

if __name__ == '__main__':
    main()

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

def topological_sort(G):
    ret = []
    start = []
    parent = [set() for _ in range(len(G))]
    for u in range(len(G)):
        for v in G[u]:
            parent[v].add(u)
    for v in range(len(G)):
        if not parent[v]:
            start.append(v)

    while start:
        u = start.pop()
        ret.append(u)
        for v in G[u]:
            parent[v].remove(u)
            if not parent[v]:
                start.append(v)

    if any(parent):
        
        return None
    return ret

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
parent = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    parent[y].append(x)
V = topological_sort(G)
dp = [0] * (N+1)
for i in V:
    for j in parent[i]:
        dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

Solution (Python):
from collections import deque
N,M = list(map(int,input().split()))
inflows = [0]*(N+1)
edges = [[] for i in range(N+1)]
for i in range(M):
    x,y = list(map(int,input().split()))
    edges[x].append(y)
    inflows[y] += 1

queue = deque([i for i in range(1,N+1) if inflows[i] == 0])
DP = [0]*(N+1)
while queue:
    x = queue.popleft()
    for y in edges[x]:
        inflows[y] -= 1
        DP[y] = max(DP[y],DP[x]+1)
        if inflows[y] == 0:
            queue.append(y)

print(max(DP))

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
path = [0 for i in range(n+1)]
con = [0 for i in range(n+1)]
for a,b in ab:
  graph[b].append(a)
  path[a] = -1
  con[a] += 1
stack = []
for i in range(1,n+1):
  if path[i] == 0:
    stack.append(i)
    while stack:
      x = stack.pop()
      for y in graph[x]:
        path[y] = max(path[y],path[x]+1)
        con[y] -= 1
        if con[y] == 0:
          stack.append(y)
print(max(path))

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

def rec(n):
  if dp[n] != -1:
    return dp[n]
  else:
    max_n = 0
    for i in graph[n]:
      max_n = max(max_n, rec(i)+1)
    dp[n] = max_n
    return dp[n]
  
N, M = list(map(int, input().split()))

dp = [-1]*N 

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

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

Solution (Python):
n, m = map(int, input().split())
adj = {}
indegrees = [0 for _ in range(n+1)]
for _ in range(m):
  cur, nxt = map(int, input().split())
  adj[cur] = adj.get(cur, []) + [nxt]
  indegrees[nxt] += 1
  
stack = []
for i in range(1, n+1):
  if indegrees[i] == 0:
    stack.append(i)
    
dp = [0 for _ in range(n+1)]
    
while stack:
  cur = stack.pop()
  for nxt in adj.get(cur, []):
    indegrees[nxt] -= 1
    if indegrees[nxt] == 0:
      stack.append(nxt)
    dp[nxt] = max(dp[nxt], dp[cur] + 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 -= 1
    y -= 1
    g[x].append(y)
dp = [-1]*n
 
def dfs(i):
    
    if dp[i] != -1:
        return dp[i]
    
    tmp = 0
    
    for j in g[i]:
        
        tmp = max(tmp, dfs(j) + 1)
    
    
    dp[i] = tmp
    return tmp
 
for i in range(n):
    dfs(i)

print(max(dp))

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

N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}

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

"""
dp[v]: ノードv(1~N)を始点とした最大長
"""
dp = [0] * (1+N)

def max_length_from(v):
    if dp[v] != 0:
        return dp[v]
    max_length = 0
    for vv in graph[v]:
        tmp = max_length_from(vv) + 1
        if tmp > max_length:
            max_length = tmp
    dp[v] = max_length
    return max_length

for v in range(1, N+1):
    max_length_from(v)

print(max(dp))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    n,m = map(int,input().split())
    edge = [[] for i in range(n)]
    
    st = []
    
    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 i in range(n):
        if to[i] == 0:
            st.append(i)

    
    dp = [0]*n
    while st:
        go = st.pop()
        for e in edge[go]:
            to[e] -= 1
            if to[e] == 0:
                st.append(e)
            dp[e] = max(dp[e],dp[go]+1)
    print(max(dp))


if __name__ == '__main__':
    main()

Solution (Python):





def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    n,m = map(int,input().split())
    edge = [[] for i in range(n)]
    
    st = []
    
    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 i in range(n):
        if to[i] == 0:
            st.append(i)

    
    dp = [0]*n
    while st:
        go = st.pop()
        for e in edge[go]:
            to[e] -= 1
            if to[e] == 0:
                st.append(e)
            dp[e] = max(dp[e],dp[go]+1)
    print(max(dp))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

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

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

dp = [-1] *n
for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)
  

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

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

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

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

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

dp = [-1] *n
for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)
  

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
n , m = map(int,input().split())

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

dp = [-1] * n
for _ in range(m):
  v1, v2 = map(int,input().split())
  v1-=1 ; v2-=1
  g[v1].append(v2)

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

print(res)

Solution (Python):
from collections import defaultdict,deque

N,M=map(int,input().split())
Out=defaultdict(list)
In=defaultdict(int)

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

q=deque(v for v in range(1,N+1) if In[v]==0)

dp=[0]*(N+1)

while q:
    From = q.popleft()
    for to in Out[From]:
        dp[to]=max(dp[From]+1,dp[to])
        In[to]-=1
        if In[to]==0:
            q.append(to)
print(max(dp))

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

def dfs(i):
    if dp[i] != -1:
        return dp[i]

    tmp = 0
    for j in g[i]:
        tmp = max(tmp, dfs(j) + 1)

    dp[i] = tmp
    return tmp

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

print(max(dp))

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N,M = imn()
G = [[] for _ in range(N)]
dp = [-1 for _ in range(N)]

for i in range(M):
    xy = iln()
    G[xy[0]-1].append(xy[1]-1)

def dfs(v):
    if dp[v] != -1: return dp[v]
    ans = 0
    for n in G[v]:
        ans = max(ans, dfs(n)+1)
    dp[v] = ans
    return dp[v]

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

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

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

dp = [-1] * N
def dfs(v):
    if dp[v] > -1:
        return dp[v] + 1
    ret = 0
    for i in path[v]:
        ret = max(ret, dfs(i))
    dp[v] = ret
    return ret + 1


for i in range(N):
    if dp[i] < 0:
        dfs(i)

print(max(dp))

Solution (Python):
"""memo
    トポロジカルソート「http://zehnpaard.hatenablog.com/entry/2018/06/26/201512」
    をしてから，dpで求めた．（ソートと同時にdp求められそう）
"""
from collections import deque, defaultdict
import sys
input == sys.stdin.readline

def main():
    v, n = map(int, input().split())
    es = [[int(x) for x in input().split()] for _ in range(n)]

    outs = defaultdict(list)
    ins = defaultdict(int)
    
    for v1, v2 in es:
        outs[v1].append(v2)
        ins[v2] += 1
        
    
    q = deque(v1 for v1 in range(1,v+1) if ins[v1] == 0) 
    
    res = []
    
    
    dp = [0]*(v+1)
    while q:
        
        v1 = q.popleft()
        res.append(v1)
        for v2 in outs[v1]: 
            dp[v2] = dp[v1] + 1
            
            ins[v2] -= 1
            if ins[v2] == 0: 
                
                q.append(v2)
    
    
    

    print(max(dp))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque

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

outs = defaultdict(list)
ins = defaultdict(int)

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

q = deque(v1 for v1 in range(v+1) if ins[v1] == 0)

res = []


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




dp = [0]*(v+1)
for i in res[1:]:
    for j in outs[i]:
        dp[j] = dp[i] + 1
        

print(max(dp))

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


N, M = map(int, input().split())
g = {}
for i in range(N):
    g[i] = set()
for _ in range(M):
    pre, post = map(int, input().split())
    g[post-1].add(pre-1)    


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


def dp_rec(p):

    if dp[p] != -1:
        return dp[p]

    res = 0
    for n in g[p]:
        res = max(res, dp_rec(n) + 1)

    dp[p] = res
    return res


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

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

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)

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


def calc(x):
    if lst[x] != -1:
        return lst[x]
    tmp = 0
    for next_ in G[x]:
        tmp = max(tmp, calc(next_))
    
    lst[x] = tmp + 1
    return tmp + 1

ans = 0
for i in range(1, N + 1):
    if lst[i] == -1:
        ans = max(ans, calc(i))

print (ans - 1)

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

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)

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


def calc(x):
    if lst[x] != -1:
        return lst[x]
    tmp = 0
    for next_ in G[x]:
        tmp = max(tmp, calc(next_))
    
    lst[x] = tmp + 1
    return tmp + 1

for i in range(1, N + 1):
    if lst[i] == -1:
        calc(i)

print (max(lst) - 1)

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


def main():
    n, m = map(int, input().split())

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

    def longest(i, memo):
        if memo[i] >= 0:
            return memo[i]
        if len(net[i]) == 0:
            l = 0
        else:
            l = max(longest(j, memo) + 1 for j in net[i])
        memo[i] = l
        return l

    memo = [-1] * n
    l = max(longest(i, memo) for i in range(n))
    print(l)


main()

Solution (Python):
N, M = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(M)]

from collections import defaultdict
from collections import deque
from collections import Counter
g = defaultdict(set)

for x, y in XY:
  g[x].add(y)
  
  
def TSort(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    funin = Counter()
    
    for u in V:
        for v in g[u]:
            funin[v] += 1
    
    q = deque()
    for v in V:
        if funin[v] == 0:
            q.append(v)
    L = []
    while q:
        u = q.popleft()
        L.append(u)
        for v in g[u]:
            funin[v] -= 1
            if funin[v] == 0:
                q.append(v)
    return L

  
D = Counter()
ns = TSort(g)
for u in ns:
  for v in g[u]:
    D[v] = max(D[v], D[u] + 1)
print(D.most_common()[0][1])

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

N,M = map(int,input().split())
A = [list(map(int, input().split())) for i in range(M)]
visit = set()
G = collections.defaultdict(set)
for idx,(f,to) in enumerate(A):
    G[f].add(to)

cache = {}
    
def dfs(start):
    if start in cache:
        return cache[start]
    ma = 0
    for i in G[start]:
        if i not in visit:
            
            ma = max(ma,dfs(i))
            
    cache[start] = ma + 1 
    return ma + 1

ma = 0 
for f,to in A:
    
    ma = max(ma,dfs(f))
    
print(ma - 1)

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

N,M = map(int,input().split())
A = [list(map(int, input().split())) for i in range(M)]
visit = set()
G = collections.defaultdict(set)
for idx,(f,to) in enumerate(A):
    G[f].add(to)

cache = {}
    
def dfs(start):
    if start in cache:
        return cache[start]
    ma = 0
    for i in G[start]:
        if i not in visit:
            visit.add(i)
            ma = max(ma,dfs(i))
            visit.remove(i)
    cache[start] = ma + 1 
    return ma + 1

ma = 0 
for f,to in A:
    visit.add(f)
    ma = max(ma,dfs(f))
    visit.remove(f)
print(ma - 1)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

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

dp = [-1]*n

def rec(node):
  if dp[node] != -1: return dp[node]
  result = 0
  for vi in G[node]:
    result= max(result,rec(vi)+1)
    dp[node] = result
  return result


for i in range(n):
  if dp[i] == -1:
      rec(i)
print(max(dp))

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

def Topological_Sort(G):
    
    V=len(G)
    div=[0]*V
    for gi in G:
        for ei  in gi:
            div[ei]+=1
    used=[0]*V
    result=[]

    def bfs(node):
        que = collections.deque([node])
        used[node] = 1
        while que:
            tmp = que.popleft()
            result.append(tmp)
            for v in G[tmp]:
                div[v] -= 1
                if div[v] == 0 and not used[v]:
                    que.append(v)
                    used[v] = 1

    for i in range(V):
        if div[i]==0 and not used[i]:
            bfs(i)
    return result
DAG = Topological_Sort(G)
dp=[0]*n
for ni in DAG:
  for vi in G[ni]:
    dp[vi] = max(dp[vi],dp[ni]+1)
print(max(dp))

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

def main():
    n, m = map(int, input().split())

    dag = [[] for _ in range(n+1)]
    for _ in range(m):
        src, dst = map(int, input().split())
        dag[src].append(dst)


    dists = [0] * (n+1)

    def longest(v):
        if dists[v]:
            return dists[v]
        for to in dag[v]:
            dists[v] = max(dists[v], longest(to) + 1)
        return dists[v]

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
 
sys.setrecursionlimit(150000)

def gdp(n, dp, G):
    if dp[n]!=-1:
        return dp[n]
 
    if G[n]==[]:
        dp[n]=0
        return 0
 
    for i in G[n]:
        ll=gdp(i, dp, G)
        if dp[n]<ll+1:
            dp[n]=ll+1
 
    return dp[n]
 
def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    G=[[] for _ in range(N)]
    for i in range(M):
        G[x[i]-1].append(y[i]-1)
 
    dp=[-1]*N
 
    print(max(gdp(i, dp, G) for i in range(N)))
 
    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(150000)

def gdp(n, dp, G):
    if dp[n]!=-1:
        return dp[n]

    if G[n]==[]:
        dp[n]=0
        return 0

    for i in G[n]:
        ll=gdp(i, dp, G)
        if dp[n]<ll+1:
            dp[n]=ll+1

    return dp[n]

def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    G=[[] for _ in range(N)]
    for i in range(M):
        G[x[i]-1].append(y[i]-1)

    dp=[-1]*N

    print(max(gdp(i, dp, G) for i in range(N)))

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

def gdp(n, dp, G):
    if dp[n]!=-1:
        return dp[n]

    if G[n]==[]:
        dp[n]=0
        return 0

    for i in G[n]:
        ll=gdp(i, dp, G)
        if dp[n]<ll+1:
            dp[n]=ll+1

    return dp[n]

def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    G=[[] for _ in range(N)]
    for i in range(M):
        G[x[i]-1].append(y[i]-1)

    dp=[-1]*N

    print(max(gdp(i, dp, G) for i in range(N)))

    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):
from collections import deque

def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    parents = [0] * (n+1)
    for _ in range(m):
        src, dst = map(int, input().split())
        graph[src].append(dst)
        parents[dst] += 1

    q = deque()
    for i in range(1, n+1):
        if parents[i] == 0:
            q.append(i)

    dists = [0] * (n+1)
    for i in q:
        dists[0] = 0

    while q:
        at = q.popleft()
        for to in graph[at]:
            parents[to] -= 1
            if parents[to] == 0:
                q.append(to)
                dists[to] = dists[at] + 1

    print(max(dists[1:]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
 
n, m = map(int, input().split())
 
edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)
 
dp = [-1 for _ in range(n+1)]
 
def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d
 
for u in range(1, n+1):
    longest_path(u)
 
print(max(dp))

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

def main():
    n,m=map(int,input().split())
    g1=[[] for _ in range(n+1)]
    g2=[0]*(n+1)
    for i in range(m):
        a,b=map(int,input().split())
        g1[a].append(b)
        g2[b]+=1
    st=deque([])
    for i in range(n+1):
        if g2[i]==0:
            st.append(i)
    d=[10**5+1]*(n+1)
    for i in st:
        d[i]=0
    while st:
        a=st.popleft()
        for b in g1[a]:
            g2[b]-=1
            if g2[b]==0:
                st.append(b)
                d[b]=d[a]+1
    print(max(d[1:]))


if __name__ == '__main__':
    main()

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

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

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


def dfs(s):
    
    if dp[s] != -1:
        return dp[s]
    
    rep = 0
    for g in graph[s]:
        rep = max(rep, dfs(g)+1)
    dp[s] = rep
    return rep


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

print(ans)

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

from collections import deque
n,m=map(int,input().split())
infi=10**10


graph1=[[]for _ in range(n+1)]

graph2=[ 0 for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    graph1[x].append(y)
    graph2[y]+=1

start=deque([])
for i in range(1,n+1):
    if graph2[i]==0:
        start.append(i)








dist=[infi]*(n+1)
for i in start:
    dist[i]=0
while start:
    a=start.popleft()
    kyori=dist[a]

    for b in graph1[a]:
        graph2[b]-=1
        if graph2[b]==0:
            start.append(b)
            dist[b]=min(dist[b],dist[a]+1)
print(max(dist[1:]))

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(100000000)
from collections import defaultdict
from collections import deque


def recursive_dfs(graph, start_node, map1):
  if start_node not in graph:
    map1[start_node] = 0
    return 0
  dist = 0
  for child in graph[start_node]:
    if child not in map1:
      dist = max(recursive_dfs(graph, child, map1), dist)
    else:
      dist = max(map1[child], dist)
  map1[start_node] = dist + 1
  
  return (dist + 1)
 
N,M = [int(i) for i in input().split()] 
graph = defaultdict(list)
for i in range(M):
  s,d = [i for i in input().split()]
  graph[s].append(d)
map1 = defaultdict(int)
ans = 0
for i in range(1, N+1):
  if i in map1:
    ans = max(ans, map1[str(i)])
  else:
    ans = max(recursive_dfs(graph, str(i), map1), ans)
print("%s" % ans)

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

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

F = [-1 for _ in range(N)]


def dfs(s):
    if F[s] != -1:
        return F[s]
    ret = 0
    for g in G[s]:
        ret = max(ret, dfs(g)+1)
    F[s] = ret
    return ret


res = 0
for i in range(N):
    res = max(dfs(i), res)

print(res)

Solution (Python):



from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def main():
  n, m = map(int, input().strip().split())
  memo = [-1] * (n+1)
  graph = defaultdict(list)

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

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

    lp = 0
    for t in graph[v]:
      lp = max(lp, rec(t)+1)
    memo[v] = lp
    return memo[v]

  lp = 0
  for v in range(1, n+1):
    lp = max(lp, rec(v))
  print(lp)


if __name__=='__main__':
  main()