Problem:
 Score : 100 points    Problem Statement There is a directed graph G with N vertices and M edges.
The vertices are numbered 1, 2, \ldots, N , and for each i ( 1 \leq i \leq M ), the i -th directed edge goes from Vertex x_i to y_i . G  does not contain directed cycles .  Find the length of the longest directed path in G .
Here, the length of a directed path is the number of edges in it.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq x_i, y_i \leq N  All pairs (x_i, y_i) are distinct.  G  does not contain directed cycles .         Input Input is given from Standard Input in the following format:  N  M  x_1  y_1  x_2  y_2  :  x_M  y_M       Output Print the length of the longest directed path in G .        Sample Input 1 4 5
1 2
1 3
3 2
2 4
3 4      Sample Output 1 3  The red directed path in the following figure is the longest:        Sample Input 2 6 3
2 3
4 5
5 6      Sample Output 2 2  The red directed path in the following figure is the longest:        Sample Input 3 5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3      Sample Output 3 3  The red directed path in the following figure is one of the longest:

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


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    edge[s].append(t)

dp = [-1]*N

def dfs(s):
    if dp[s] != -1:
        return dp[s]
    if len(edge[s]) == 0:
        dp[s] = 0
        return 0
    res = 0
    for t in edge[s]:
        res = max(res, dfs(t)+1)
    dp[s] = res
    return res

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

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

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

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

stack = []

for i in range(N):
    if not deg[i]:
        stack.append(i)

while stack:
    node = stack.pop()
    for adj in graph[node]:
        deg[adj] -= 1
        dp[adj] = max(dp[adj], dp[node] + 1)
        if not deg[adj]:
            stack.append(adj)

print(max(dp))

Solution (Python):

import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def get_longest(x, longest, edges):
    if longest[x] is not None:
        return longest[x]
    if not edges[x]:
        longest[x] = 0
    else:
        result = max([get_longest(y, longest, edges)
                      for y in edges[x]])
        longest[x] = result + 1
    return longest[x]


def main():
    input = sys.stdin.readline
    
    
    

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

    edges = defaultdict(set)
    for i in range(M):
        x, y = map(int, input().split())
        edges[x].add(y)

    longest = [None] * (N + 1)
    for x in range(N):
        x += 1
        if longest[x] is None:
            get_longest(x, longest, edges)

    print(max(longest[1:]))


if __name__ == '__main__':
    main()

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


def main():
    def DFS(v):
        if DP[v] == -1:
            res = 0
            for i in G[v]:
                res = max(res, DFS(i) + 1)

            DP[v] = res

        return DP[v]


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

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

    DP = [-1] * N
    for v in range(N):
        DFS(v)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()

Solution (Python):
from collections import deque


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

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

    DP = [0] * N
    queue = deque()
    for i in range(N):
        if ins[i] == 0:
            queue.append(i)

    while queue:
        v = queue.popleft()
        for i in G[v]:
            ins[i] -= 1
            if ins[i] == 0:
                DP[i] = max(DP[i], DP[v] + 1)
                queue.append(i)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys
import numpy as np
import numba

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


@numba.njit(cache=True)
def get_longest(start, values, next, head, longest):
    ret = longest[start]
    if ret != -1:
        return ret

    ret = 0
    p = head[start]
    while p:
        v = values[p]
        x = get_longest(v, values, next, head, longest) + 1
        if x > ret:
            ret = x
        p = next[p]

    longest[start] = ret
    return ret


@numba.njit(cache=True)
def solve(N, M, data):
    longest = np.repeat(-1, N + 1)

    values = np.zeros(M + 1, np.int32)
    next = np.zeros(M + 1, np.int32)
    head = np.zeros(N + 1, np.int32)
    p = 1
    for i in range(0, 2 * M, 2):
        v1 = data[i]
        v2 = data[i + 1]
        values[p] = v2
        next[p] = head[v1]
        head[v1] = p
        p += 1

    for i in range(N + 1):
        if head[i] == 0:
            longest[i] = 0

    ret = 0
    for v in range(N + 1):
        x = get_longest(v, values, next, head, longest)
        if x > ret:
            ret = x
    return ret


def main():
    N, M = map(int, input().split())
    data = np.int32(read().split())
    print(solve(N, M, data))


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def _test():
    """
    
    
    

    
    
    

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    
    
    
    
    
    
    
    
    
    import numba
    numba.njit(cache=True)(get_longest)
    numba.njit(cache=True)(solve)
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  

    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
from collections import deque


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

    G = [[] for _ in range(N)]
    ins = [0] * N
    for i in range(M):
        G[xy[i][0] - 1].append(xy[i][1] - 1)
        ins[xy[i][1] - 1] += 1

    DP = [0] * N
    queue = deque()
    for i in range(N):
        if ins[i] == 0:
            queue.append(i)

    while queue:
        v = queue.popleft()
        for i in G[v]:
            ins[i] -= 1
            if ins[i] == 0:
                DP[i] = max(DP[i], DP[v] + 1)
                queue.append(i)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()

Solution (Python):

"""
Simple Version
Python TLE https://atcoder.jp/contests/dp/submissions/14906600
PyPy TLE https://atcoder.jp/contests/dp/submissions/14906630
"""
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = [-1] * (N + 1)
    for i in range(N + 1):
        if not edges[i]:
            longest[i] = 0

    def get_longest(start):
        next = edges[start]
        for v in next:
            if longest[v] == -1:
                longest[v] = get_longest(v)

        ret = max(longest[v] for v in next) + 1
        return ret

    for i in range(N + 1):
        if longest[i] == -1:
            longest[i] = get_longest(i)

    return max(longest[v] for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


main()

Solution (Python):

"""
Simple Version
Python TLE https://atcoder.jp/contests/dp/submissions/14906600
PyPy TLE https://atcoder.jp/contests/dp/submissions/14906630
"""
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = {}

    stack = [v for v in edges]

    while stack:
        v = stack.pop()
        if v > 0:
            if v in longest:
                continue
            next_edges = edges.get(v)
            stack.append(-v)
            if next_edges:
                stack.extend(next_edges)
        else:
            next_edges = edges.get(-v)
            if not next_edges:
                ret = 0
            else:
                ret = max(longest[x] for x in next_edges) + 1
            longest[-v] = ret

    return max(longest[v] for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def _test():
    """
    
    
    

    
    
    

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):

"""
Simple Version
Python TLE https://atcoder.jp/contests/dp/submissions/14906600
PyPy TLE https://atcoder.jp/contests/dp/submissions/14906630
"""
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = {}

    stack = [v for v in edges]

    while stack:
        v = stack.pop()
        if v > 0:
            if v in longest:
                continue
            next_edges = edges.get(v)
            stack.append(-v)
            if next_edges:
                stack.extend(next_edges)
        else:
            next_edges = edges.get(-v)
            if not next_edges:
                ret = 0
            else:
                ret = max(longest[x] for x in next_edges) + 1
            longest[-v] = ret

    return max(longest[v] for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def _test():
    """
    
    
    

    
    
    

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys
import numpy as np
import numba

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


@numba.njit
def get_longest(start, values, next, head, longest):
    ret = longest[start]
    if ret != -1:
        return ret

    ret = 0
    p = head[start]
    while p:
        v = values[p]
        x = get_longest(v, values, next, head, longest) + 1
        if x > ret:
            ret = x
        p = next[p]

    longest[start] = ret
    return ret


@numba.njit
def solve(N, M, data):
    longest = np.repeat(-1, N + 1)

    values = np.zeros(M + 1, np.int32)
    next = np.zeros(M + 1, np.int32)
    head = np.zeros(N + 1, np.int32)
    p = 1
    for i in range(0, 2 * M, 2):
        v1 = data[i]
        v2 = data[i + 1]
        values[p] = v2
        next[p] = head[v1]
        head[v1] = p
        p += 1

    for i in range(N + 1):
        if head[i] == 0:
            longest[i] = 0

    ret = 0
    for v in range(N + 1):
        x = get_longest(v, values, next, head, longest)
        if x > ret:
            ret = x
    return ret


def main():
    N, M = map(int, input().split())
    data = np.int32(read().split())
    print(solve(N, M, data))


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def _test():
    """
    
    
    

    
    
    

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    import numba
    cc = CC('my_module')
    cc.export(
        'solve',
        numba.i8(
            numba.i8, numba.i8,
            numba.typeof({1: [1]})))(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):

"""
Simple Version
Python TLE https://atcoder.jp/contests/dp/submissions/14906600
PyPy TLE https://atcoder.jp/contests/dp/submissions/14906630
"""
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = [-1] * (N + 1)
    for i in range(N + 1):
        if not edges[i]:
            longest[i] = 0

    def get_longest(start):
        next = edges[start]
        for v in next:
            if longest[v] == -1:
                longest[v] = get_longest(v)

        ret = max(longest[v] for v in next) + 1
        return ret

    for i in range(N + 1):
        if longest[i] == -1:
            longest[i] = get_longest(i)

    return max(longest[v] for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


main()

Solution (Python):

"""
Simple Version
Python TLE https://atcoder.jp/contests/dp/submissions/14906600
PyPy TLE https://atcoder.jp/contests/dp/submissions/14906630
"""
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = [-1] * (N + 1)
    for i in range(N + 1):
        if not edges[i]:
            longest[i] = 0

    def get_longest(start):
        ret = longest[start]
        if ret != -1:
            return ret

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


def cal(e):
    if ans_array[e] != -1:
        return ans_array[e]
    ans = 0
    if e in node_dic:
        for x in node_dic[e]:
            ans = max(ans, cal(x) + 1)
    ans_array[e] = ans
    return ans


N, M = na()
node_dic = {}
no_in = [1] * N

for _ in range(M):
    x, y = na()
    if x-1 in node_dic:
        node_dic[x-1].append(y-1)
    else:
        node_dic[x-1] = [y-1]
    no_in[y-1] = 0





ans_array = [-1] * N

edge = deque([])

for i, x in enumerate(no_in):
    if x == 1:
        cal(i)


print(max(ans_array))

Solution (Python):

"""
Cython test
"""
from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


def solve(N, M, edges):
    longest = [-1] * (N + 1)

    def get_longest(start):
        if longest[start] != -1:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


def _test():
    """
    
    
    

    
    
    

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

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

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 rec(v):
    if dp[v] >= 0:
        return dp[v]
    temp = 0
    for next in graph[v]:
        temp = max(rec(next) + 1, temp)
    dp[v] = temp
    return temp

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

Solution (Python):
import sys
from collections import deque
def tsort(n,g,inc):
    s,tsl=deque(),[]
    s.extend([i for i,x in enumerate(inc) if x==0])
    while len(s)>0:
        x=s.popleft()
        tsl.append(x)
        for y in g[x]:
            inc[y]-=1
            if inc[y]==0:s.append(y)
    return tsl
def main():
    N,M=tuple(map(int,sys.stdin.readline().split()))
    lpl,inc,g=[0 for _ in range(N)],[0 for _ in range(N)],[[] for _ in range(N)]
    for _ in [0]*M:
        x,y=tuple(map(int,sys.stdin.readline().split()))
        inc[y-1]+=1
        g[x-1].append(y-1)
    tsl=tsort(N,g,inc)
    for t in tsl:
        for n in g[t]:lpl[n]=lpl[t]+1 if lpl[t]+1>lpl[n] else lpl[n]
    print(max(lpl))
if __name__=='__main__':main()

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

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

def rec(c):
    if dp[c] != -1:
        return dp[c]
    res = 0
    for i in graph[c]:
        res = max(res, rec(i) + 1)
    dp[c] = res
    return res

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

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
dp=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)

def dfs(s):
  if edge[s]:
    for i in edge[s]:
      if dp[i]:dp[s]=max(dp[s],dp[i]+1)
      else:dp[s]=max(dp[s],dfs(i)+1)
    return dp[s]
  else:return 0
for i in range(n):
  dfs(i)
print(max(dp))

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


def solve0(N, M, edges):
    path = edges.copy()
    exists = 1
    for i in range(2, M + 1):
        next_path = defaultdict(set)
        for v1 in path:
            for v2 in path[v1]:
                if edges[v2]:
                    next_path[v1].update(edges[v2])
                    exists = i
                    
        if exists != i:
            
            break
        path = next_path
    return exists


def solve(N, M, edges):
    longest = {}

    def get_longest(start):
        if longest.get(start) != None:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


def solve(N, M, edges):
    import numba
    longest = [-1] * (N + 1)

    def intlist(xs):
        if xs:
            return list(xs)
        else:
            return numba.typed.List()

    edges = [intlist(edges[k]) for k in range(N + 1)]
    @numba.njit
    def get_longest(start, edges):
        if longest[start] != -1:
            return longest[start]

        ret = 0
        for v in edges[start]:
            x = get_longest(v, edges) + 1
            if x > ret:
                ret = x
        longest[start] = ret
        return ret

    ret = 0
    for v in range(N + 1):
        x = get_longest(v, edges)
        if x > ret:
            ret = x
    return ret


def solve(N, M, edges):
    longest = [-1] * (N + 1)

    for i in range(N + 1):
        if not edges[i]:
            longest[i] = 0

    def get_longest(start):
        next = edges[start]
        for v in next:
            if longest[v] == -1:
                longest[v] = get_longest(v)

        ret = max(longest[v] for v in next) + 1
        return ret

    for i in range(N + 1):
        if longest[i] == -1:
            longest[i] = get_longest(i)

    return max(longest[v] for v in edges)


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


def _test():
    """
    
    
    

    
    
    

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
from collections import defaultdict, deque

def topological_sort(vertex:list, edge:list):
    graph = {i: [] for i in vertex}
    for i, j in edge:
        graph[i].append(j)
        
    inp_cnt = defaultdict(int)
    outs = defaultdict(list)
    for inp, out in edge:
        inp_cnt[out] += 1
        outs[inp].append(out)

    result = []
    queue = deque([i for i in vertex if inp_cnt[i]==0])
    while queue:
        v = queue.popleft()
        result.append(v)
        for v2 in outs[v]:
            inp_cnt[v2] -= 1
            if inp_cnt[v2] == 0:
                queue.append(v2)
    return result

N, M = map(int, input().split())
vertex = list(range(1, N+1))
edge = [list(map(int, input().split())) for _ in range(M)]
graph = {i: [] for i in vertex}
for i, j in edge:
    graph[i].append(j)

sorted_vertecies = topological_sort(vertex, edge)
dp = [0] * (N+1)
for i in sorted_vertecies:
    ends = graph[i]
    for j in ends:
        dp[j] = max(dp[j], dp[i] + 1)
print(max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges)]

nodes = [[] for _ in range(edges)]

for i in range(vertices):
    start, end = map(int, input().split())
    nodes[end -1].append(start-1)

for i in range(edges):
    if not len(nodes[i]):
        dp[i] = 0
def find(arr):
    if not len(arr):
        return 0
    for x in arr:
        if dp[x] is None:
            dp[x] = find(nodes[x])
    return 1 + max(dp[x] for x in arr)

for i in range(edges):
    dp[i] = find(nodes[i])

print(max(dp))

Solution (Python):
from collections import deque

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


grafo = [[] for i in range(n+1)]

num_adj = [0] * (n+1)

for i in range(m):
    u, v = map(int,input().split())
    grafo[u].append(v)
    num_adj[v] += 1

q = deque()

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

dp = [0] * (n + 1)

while q:
    n = q.popleft()
    for s in grafo[n]:
        num_adj[s] -= 1

        if num_adj[s] == 0:
            q.append(s)
            dp[s] = dp[n] + 1

print(max(dp))

Solution (Python):
def main():
    n, adj = getInputs()
    sequence = getTopologicalSort(n, adj)

    distance = [-1] * n
    longest = -1

    for v in sequence:
        if len(adj[v]) == 0:
            distance[v] = 0
        else:
            for dest in adj[v]:
                distance[v] = max(distance[v], 1 + distance[dest])
                longest = max(longest, distance[v])

    print(longest)

def getTopologicalSort(n, adj):
    state = [0] * n
    toVisit = list(range(n))

    topologicalSort = []
    order = []

    while len(toVisit) > 0:
        curr = toVisit.pop()

        if state[curr] == 0:
            order.append(curr)
            state[curr] = 1

            foundNewDest = False
            for dest in adj[curr]:
                if state[dest] == 0:
                    toVisit.append(dest)
                    foundNewDest = True

            if not foundNewDest:
                while True:
                    v = order[-1]

                    allProcessed = True
                    for dest in adj[v]:
                        if state[dest] == 0:
                            allProcessed = False
                            break

                    if allProcessed:
                        state[v] = 2
                        topologicalSort.append(order.pop())

                    if len(order) == 0 or not allProcessed:
                        break

    return topologicalSort

def getInputs():
    n, m = map(lambda x: int(x), input().split())

    adj = []
    for i in range(n):
        adj.append([])

    for i in range(m):
        a, b = map(lambda x: int(x), input().split())
        adj[a - 1].append(b - 1)

    return n, adj

main()

Solution (Python):
def main():
    n, adj = getInputs()
    sequence = getTopologicalSort(n, adj)

    distance = [-1] * n
    longest = -1

    for v in sequence:
        if len(adj[v]) == 0:
            distance[v] = 0
        else:
            for dest in adj[v]:
                distance[v] = max(distance[v], 1 + distance[dest])
                longest = max(longest, distance[v])

    print(longest)

def getTopologicalSort(n, adj):
    state = [0] * n
    toVisit = list(range(n))

    topologicalSort = []
    order = []

    while len(toVisit) > 0:
        curr = toVisit.pop()

        if state[curr] == 0:
            order.append(curr)
            state[curr] = 1

            foundNewDest = False
            for dest in adj[curr]:
                if state[dest] == 0:
                    toVisit.append(dest)
                    foundNewDest = True

            if not foundNewDest:
                while True:
                    v = order[-1]

                    allProcessed = True
                    for dest in adj[v]:
                        if state[dest] == 0:
                            allProcessed = False
                            break

                    if allProcessed:
                        state[v] = 2
                        topologicalSort.append(order.pop())

                    if len(order) == 0 or not allProcessed:
                        break

    return topologicalSort

def getInputs():
    n, m = map(lambda x: int(x), input().split())

    adj = []
    for i in range(n):
        adj.append([])

    for i in range(m):
        a, b = map(lambda x: int(x), input().split())
        adj[a - 1].append(b - 1)

    return n, adj

main()