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 numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,m = map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
      x,y=map(int,input().split())
      g[x-1].append(y-1)
memo = [0]*n
visited = [False]*n

def dp(v):
      if visited[v]:
            return memo[v]
      else:
            res=0
            for u in g[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))

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

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

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

def dp(v):
    if visited[v]:
        return memo[v]
    else:
        res = 0
        for u in g[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))

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

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

memo = [-1]*n

def dp(v):
    if memo[v] >= 0:
        return memo[v]
    else:
        res = 0
        for u in g[v]:
            res = max(res, dp(u) + 1)
        memo[v] = res
        return res

for i in range(n):
    dp(i)
print(max(memo))

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

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

memo = [-1]*n

def dp(v):
    if memo[v] >= 0:
        return memo[v]
    else:
        res = 0
        for u in g[v]:
            res = max(res, dp(u) + 1)
        memo[v] = res
        return res

for i in range(n):
    dp(i)
print(max(memo))

Solution (Python):
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
    x, y = [int(x) for x in input().split()]
    g[x - 1].append(y - 1)
from functools import lru_cache
sys.setrecursionlimit(10**7)
@lru_cache(maxsize=None)
def dp(v):
    res = 0
    for u in g[v]:
        res = max(res, dp(u) + 1)
    return res
ans = -1
for i in range(n):
    ans = max(ans, dp(i))
print(ans)

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

N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

memo = {}
def dp(p):
    if p not in memo:
        memo[p] = max((1 + dp(c) for c in E[p]), default=0)
    return memo[p]

print(max(dp(p) for p in range(1, N + 1)))

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

N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

memo = {}
def dp(p):
    if p in memo:
        return memo[p]

    memo[p] = max((1 + dp(c) for c in E[p]), default=0)
    return memo[p]

print(max(dp(p) for p in range(1, N + 1)))

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


def read():
    N, M = map(int, input().strip().split())
    parents = [list() for i in range(N)]
    n_children = [0 for i in range(N)]
    for i in range(M):
        x, y = map(int, input().strip().split())
        n_children[x-1] += 1  
        parents[y-1].append(x-1)   
    return N, M, n_children, parents


def solve(N, M, n_children, parents):
    dp = [0 for i in range(N)]
    q = deque()
    r = deque()
    for x in range(N):
        if n_children[x] == 0:
            q.append(x)
    while q:
        x = q.pop()
        r.append(x)
        for parent in parents[x]:
            n_children[parent] -= 1
            if n_children[parent] == 0:
                q.append(parent)
    
    while r:
        x = r.pop()
        for y in parents[x]:
            dp[x] = max(dp[x], dp[y]+1)
    return max(dp)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

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

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

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

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

def rec(now):
    global G
    global DP

    if DP[now]!=-1:
        return DP[now]

    else:
        res=0
        for next in G[now]:
            res=max(res,rec(next)+1)
        DP[now]=res
        return DP[now]  


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



print(ans)

Solution (Python):
import collections
n,m = map(int,input().split())
d = {}
indegree = [0]*n
for _ in range(m):
    x,y = map(int,input().split())
    d[x-1] = d.get(x-1,[]) + [y-1]
    indegree[y-1] += 1
dp = [0]*n
q = collections.deque([i for i in range(n) if indegree[i] == 0])
while q:
    node = q.popleft()
    for nei in d.get(node,[]):
        indegree[nei] -= 1
        dp[nei] = max(dp[nei],dp[node]+1)
        if indegree[nei] == 0:
            q.append(nei)
print(max(dp))

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

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

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)

dp=[-1]*n
for i in range(n):
  dp[i]=max(dp[i],dfs(i))
print(max(dp))

Solution (Python):
n,m = map(int, input().split())
link = [[] for _ in range(n)]
inc=[0]*n
for _ in range(m):
    x,y = list(map(int,input().split()))
    link[x-1].append(y-1)
    inc[y-1]+=1

s=[]
for i in range(len(inc)):
    if inc[i]==0:
        s.append(i)
res=[]
while s:
    nxt=s.pop()
    res.append(nxt)
    for m in link[nxt]:
        inc[m]-=1
        if inc[m]==0:
            s.append(m)

path=[-1]*n
for now in res:
    if path[now]==-1:
        path[now]=0
    for nxt in link[now]:
        path[nxt] = max(path[nxt],path[now]+1)

print(max(path))

Solution (Python):






"""Module docstring
"""

import sys
from collections import defaultdict

sys.setrecursionlimit(pow(2, 31) - 1)




def dfs(vertex, succ, dp):
    if vertex in dp:
        return dp[vertex]
    length = 0
    for s in succ[vertex]:
        length = max(length, 1 + dfs(s, succ, dp))
    dp[vertex] = length
    return length



def solve(values, _nb_vertices, _nb_edges) -> int:
    succ = defaultdict(list)
    for s, d in values:
        succ[s].append(d)
    
    dp = defaultdict(lambda: -1)
    for vertex in frozenset(succ.keys()):
        if vertex in dp:
            dp[vertex] = max(dp[vertex], dfs(vertex, succ, dp))
        else:
            dp[vertex] = dfs(vertex, succ, dp)
    return max(dp.values())


def do_job():
    "Do the work"
    
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


if __name__ == "__main__":
    do_job()

Solution (Python):
from collections import deque

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

stack = []

for u in range(N):
    if deg[u] == 0:
        stack.append(u) 
topol = []
while len(stack) != 0:
    u = stack.pop()
    topol.append(u)
    for v in G[u]:
        deg[v] -= 1
        if deg[v] == 0:
            stack.append(v)


dp = [0 for i in range(N)]
for u in topol:
    for v in G[u]:
        dp[v] = max(dp[v], dp[u]+1)
res = 0
for i in range(N):
    if res < dp[i]:
        res = dp[i]
print(res)

Solution (Python):
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 9)
def solve(num):
    
    if(dic[num]==0):
        return 0

    mx = 0
    for el in dic[num]:
        if(dp[el]==-1):
            temp1 = solve(el)
            mx = max(mx, 1 + temp1)
            dp[el] = temp1
        else:
            mx = max(mx, 1 + dp[el])

    return mx

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

for _ in range(m):
    xtemp, ytemp = map(int, input().split())
    if(xtemp not in dic):
        dic[xtemp] = []
        dic[xtemp].append(ytemp)
    else:
        dic[xtemp].append(ytemp)

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

mxGl = 0
keys = list(dic.keys())
for node in keys:
    if(dp[node]==-1):
        temp = solve(node)
        dp[node] = temp
        mxGl = max(mxGl, temp)
    else:
        mxGl = max(mxGl, dp[node])
print(mxGl)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = sys.stdin.readline

node_num, path_num = map(int, input().split())
graph = [[] for _ in range(node_num)]

for i in range(path_num):
    from_node, to_node = map(int, input().split())
    graph[from_node - 1].append(to_node - 1)



dp = [-1] * node_num

def rec(v):
    
    
    if dp[v] > -1:
        return dp[v]
    else:
        dp[v] = 0
        for nv in graph[v]:
            dp[v] = max(dp[v], rec(nv) + 1)
        return dp[v]

ans = 0
for node in range(node_num):
    ans = max(ans, rec(node))
print(ans)

Solution (Python):


def submit():
    n, m = map(int, input().split())
    edge = {i + 1: [] for i in range(n)}
    indig = {i + 1: 0 for i in range(n)}
    dp = [-1 for _ in range(n + 1)]

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

    indig0 = []
    for node in range(1, n + 1):
        if indig[node] == 0:
            indig0.append(node)
            dp[node] = 0

    topo = []
    while indig0:
        p = indig0.pop()
        topo.append(p)
        for e in edge[p]:
            indig[e] -= 1
            if indig[e] == 0:
                indig0.append(e)

    
    for node in topo:
        for e in edge[node]:
            dp[e] = max(dp[e], dp[node] + 1)
    
    print(max(dp))

if __name__ == "__main__":
    submit()

Solution (Python):
from collections import deque

class Graph:
    def __init__(self,size):
        self.graph = [ {
            'idx' : i,
            'to': [],
            'inputs' : 0,
        } for i in range(size) ]

    def add_node(self,start,end):
        self.graph[start]['to'].append(end)
        self.graph[end]['inputs'] += 1

    def topological_sort(self):
        inputs = [i['inputs'] for i in self.graph]
        no_inputs = deque([ i['idx'] for i in self.graph if i['inputs'] == 0])
        ans = []
        while no_inputs:
            vertex1 = no_inputs.popleft()
            ans.append(vertex1)
            for vertex2 in self.graph[vertex1]['to']:
                inputs[vertex2] -= 1
                if inputs[vertex2] == 0:
                    no_inputs.append(vertex2)
        return ans

def main():
    n,m = map(int, input().split())
    G = Graph(n)
    for _ in range(m):
        x,y = map(int, input().split())
        G.add_node(x-1,y-1)
    tp = G.topological_sort()
    dist = [0] * n
    for v in tp[::-1]:
        for t in G.graph[v]['to']:
            if dist[v] <= dist[t]:
                dist[v] = dist[t] + 1
    print(max(dist))

if __name__ == '__main__':
    main()

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


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


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


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

dp = [-1] * n
for v in range(n):
    dp[v] = max(dp[v], dfs(v))
print(max(dp))

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 7)


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


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


n, m = map(int, input().split())
g = {i: set() for i in range(n)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x - 1].add(y - 1)

dp = defaultdict(lambda: -1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print(max(dp.values()))

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


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


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


n, m = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x].add(y)

dp = [-1] * (n + 1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print(max(dp))

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

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)

@lru_cache(maxsize=10**5+1)
def dp(v):
    res = 0
    for w in G[v]:
        res = max(res, dp(w)+1)
    return res

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

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

inord = [0 for i in range(N)]
stack = []
for u in range(N):
    for v in G[u]:
        inord[v] += 1

for i in range(N):
    if inord[i] == 0:
        stack.append(i)

ans = []
while len(stack):
    u = stack.pop()
    ans.append(u)
    for v in G[u]:
        inord[v] -= 1
        if inord[v] == 0:
            stack.append(v)




dp = [0 for i in range(N)]
for u in ans:
    for v in G[u]:
        dp[v] = max(dp[u]+1, dp[v])

ret = 0
for i in range(N):
    ret = max(ret, dp[i])
print(ret)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)
input=sys.stdin.readline

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

memo={i:-1 for i in range(1,N+1)}
for i in range(1,N+1):
    if not edge[i]:
        memo[i]=0

def long_path(start):
    if memo[start]!=-1:
        return memo[start]

    memo[start]=max(1+long_path(i) for i in edge[start])

    return memo[start]

ans=0
for i in range(1,N+1):
    ans=max(ans,long_path(i))

print(ans)

Solution (Python):

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

indeg = [0 for _ in range(N)]
outdeg = [[] for _ in range(N)]

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

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

dp = [0 for _ in range(N)]
while heads:
    h = heads.pop()
    for c in outdeg[h]:
        dp[c] = max(dp[c], dp[h]+1)
        indeg[c] -= 1
        if indeg[c] == 0:
            heads.append(c)


ans = max(dp)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2000000000)
n,m=map(int,input().split())
v=[[] for i 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
print(max(dp(i) for i in range(n)))

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
dinp = [0]*n
edges = [[]for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)
    dinp[y] += 1


next_v = deque([])
dist = [-1]*n
for i in range(n):
    if dinp[i] == 0:
        next_v.append(i)
        dist[i] = 0
ans = 0
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        dinp[v2] -= 1
        if dinp[v2] != 0:
            continue
        next_v.append(v2)
        if dist[v]+1 <= dist[v2]:
            continue
        dist[v2] = dist[v]+1
        ans = max(ans, dist[v2])
print(ans)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
dinp = [0]*n
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)
    dinp[y] += 1

queue = deque([])
for i in range(n):
    if dinp[i] == 0:
        queue.append(i)

toposorted = []
while queue:
    v = queue.popleft()
    toposorted.append(v)
    for v2 in edges[v]:
        dinp[v2] -= 1
        if dinp[v2] == 0:
            queue.append(v2)

dist = [0]*n
for i in range(n):
    v = toposorted[i]
    for v2 in edges[v]:
        if dist[v2] <= dist[v]-1:
            continue
        dist[v2] = dist[v]-1
print(-min(dist))

Solution (Python):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
dd = defaultdict(int)
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)
    dd[y] += 1

queue = deque([])
for i in range(n):
    if dd[i] == 0:
        queue.append(i)

toposorted = []
while queue:
    v = queue.popleft()
    toposorted.append(v)
    for v2 in edges[v]:
        if dd[v2] <= 0:
            continue
        dd[v2] -= 1
        if dd[v2] == 0:
            queue.append(v2)

dist = [0]*n
for i in range(n):
    v = toposorted[i]
    for v2 in edges[v]:
        if dist[v2] <= dist[v]-1:
            continue
        dist[v2] = dist[v]-1
print(-min(dist))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)


def memoize(f):
    memo = [-1]*n

    def memoized(args):
        if memo[args] != -1:
            return memo[args]
        else:
            memo[args] = f(args)
            return memo[args]
    return memoized


@memoize
def longest_path(v):
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    return retval


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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)

dist = [-1]*n


def longest_path(v):
    if dist[v] != -1:
        return dist[v]
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    dist[v] = retval
    return dist[v]


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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)


def memoize(f):
    memo = dict()

    def memoized(*args):
        if args in memo.keys():
            return memo[args]
        else:
            memo[args] = f(*args)
            return memo[args]
    return memoized

@memoize
def longest_path(v):
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    return retval


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

Solution (Python):
n, m = map(int, input().split())
G = [[] for i in range(n)]
I = [0 for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    I[y-1] += 1

Q = [i for i in range(n) if I[i] == 0]

L = [0 for i in range(n)]
while Q:
    i = Q.pop()
    while G[i]:
        j = G[i].pop()
        I[j] -= 1
        L[j] = max(L[j], L[i]+1)
        if I[j] == 0:
            Q.append(j)
print(max(L))

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)



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

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

def memo(i):
    if dp[i] != -1:
        return dp[i]
    a=0
    for j in to[i]:
        a=max(a, memo(j)+1)
    dp[i] = a
    return a

lp = 0
for i in range(N):
    lp = max(lp,memo(i))
print(lp)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = sys.stdin.readline

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

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

def memo(i):
    if dp[i] != -1:
        return dp[i]
    a=0
    for j in to[i]:
        a=max(a, memo(j)+1)
    dp[i] = a
    return a

lp = 0
for i in range(N):
    lp = max(lp,memo(i))
print(lp)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
gout = [[] for i in range(N)]
deg = [0] * N

for i in range(M):
    x, y = MAP()
    gout[x-1].append(y-1)
    deg[y-1] += 1

topo = [v for v in range(N) if deg[v] == 0]
path_len = [0] * N
ans = 0
q = deque(topo)

while q:
    v = q.popleft()
    for t in gout[v]:
        
        deg[t] -= 1
        
        
        if deg[t] == 0:
            q.append(t)
            path_len[t] = path_len[v] + 1
            ans = path_len[t]
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

dp=[-1]*n

def memo(v):
    if dp[v]+1: 
        return dp[v]
    a=0
    for i in es[v]:
        a=max(a,memo(i)+1)
    dp[v]=a
    return a

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

print(ans)

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

def solve(g):
    dp = [-1]*len(g)
    def _solve(f):
        if dp[f] == -1:
            dp[f] = 0
            for c in g[f]:
                dp[f] = max(dp[f], 1 + _solve(c))
        return dp[f]
    for f in range(len(g)):
        _solve(f)
    
    return max(dp)

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    f, t = map(int, input().split())
    g[f-1].append(t-1)

print(solve(g))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



sys.setrecursionlimit(10**8)


def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num


N, M = mi()
x = li2(M)


adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])


dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Solution (Python):
from collections import deque

N,M = [int(v) for v in input().split()]
ad_list = [[] for _ in range (N+1)]
ad_num = [0 for _ in range(N)]
topo = []

for _ in range(M):
    l,r = [int(v) for v in input().split()]
    ad_list[l].append(r)
    ad_num[r-1] += 1

for i in range(1,N+1):
    if ad_num[i-1] == 0:
        topo.append([i,0])
queue = deque(topo[:])
while queue:
    n1,cnt = queue.popleft()
    for n2 in ad_list[n1]:
        ad_num[n2-1] -= 1
        if ad_num[n2-1] == 0:
            topo.append([n2,cnt+1])
            queue.append([n2,cnt+1])
print(max([v[1] for v in topo]))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()

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

used = [False] * n
top = []


def dfs(i):
    if not used[i]:
        used[i] = True
        for j in e[i]:
            dfs(j)
        top.append(i)


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

ans = [0] * n
for i in reversed(top):
    for j in e[i]:
        ans[j] = max(ans[j], ans[i] + 1)
print(max(ans))

Solution (Python):
from collections import deque
from collections import defaultdict
N, M = map(int, input().split())
d = [0]*N
G = defaultdict(list)
for i in range(M):
    s, t = map(int, input().split())
    d[t-1] += 1
    G[s-1].append(t-1)
q = deque([])
for i in range(N):
    if d[i] == 0:
        q.append(i)
ans = []
while q:
    s = q.popleft()
    ans.append(s)
    for t in G[s]:
        d[t] -= 1
        if d[t] == 0:
            q.append(t)
dp = [0] * (N+1)
num = 0
for i in range(0,N):
    for n in G[ans[i]]:
        dp[n] = max(dp[n], dp[ans[i]]+1)
print(dp[ans[-1]])

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



sys.setrecursionlimit(10**8)


def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num


N, M = mi()
x = li2(M)


adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])


dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



sys.setrecursionlimit(10**9)


def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num


N, M = mi()
x = li2(M)


adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])


dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



sys.setrecursionlimit(10**8)


def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num


N, M = mi()
x = li2(M)


adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])


dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



sys.setrecursionlimit(10**9)


def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num


N, M = mi()
x = li2(M)


adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])


dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



sys.setrecursionlimit(10**8)


def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num


N, M = mi()
x = li2(M)


adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])


dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



sys.setrecursionlimit(10**6)

def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num



N, M = mi()
x = li2(M)


adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))