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:



Sample input:
4 5
1 2
1 3
3 2
2 4
3 4


Sample output:
3

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

g = {i:[] for i in range(1, 110000)}
g2 = {i:[] for i in range(1, 110000)}
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)
    g2[y].append(x)

def dp2(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    
    for i in g2[v]:
        max_len = max(max_len, dp2(i) + 1)
    done[v] = 1
    memo[v] = max_len
    return max_len
    
    
def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

g = {i:[] for i in range(110000)}
g2 = {i:[] for i in range(110000)}
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)
    g2[y].append(x)

def dp_2(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    
    for i in g2[v]:
        max_len = max(max_len, dp2(i) + 1)
    done[v] = 1
    memo[v] = max_len
    return max_len
    
    
def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

g = defaultdict(list)
g2 = defaultdict(list)
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)
    g2[y].append(x)

def dp2(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    
    for i in g2[v]:
        max_len = max(max_len, dp2(i) + 1)
    done[v] = 1
    memo[v] = max_len
    return max_len
    
    
def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

g = defaultdict(list)
g2 = defaultdict(list)
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)
    g2[y].append(x)

def dp_2(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    
    for i in g2[v]:
        max_len = max(max_len, dp(i) + 1)
    done[v] = 1
    memo[v] = max_len
    return max_len
    
    
def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

g = defaultdict(list)
done = [0] * (N+50)
memo = [0] * (N+50)
for x, y in xy:
    g[x].append(y)

def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

g = defaultdict(list)
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)

def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

g = defaultdict(list)
done = [0] * (N+1)
memo = [0] * (N+1)

for x, y in xy:
    g[x].append(y)

def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
    return max_len

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

Submission status: Runtime Error

Solution code:
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 + 1)]
    for x, y in xy:
        G[x - 1].append(y - 1)

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

    print(max(DP))


if __name__ == '__main__':
    main()

exit()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def main():
    def DFS(v):
        if DP[v] != -1: return DP[v]

        res = 0
        for i in G[v]:
            res = max(res, DFS(i) + 1)

        DP[v] = res
        return res


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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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  # sys.maxsize # float("inf")


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(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> 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 = True
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',
    #     "i4(i4,i4,i4[:])")(solve)
    # cc.export(
    #     'get_longest',
    #     "i4(i4,i4[:],i4[:],i4[:],i4[:])")(get_longest)
    # cc.compile()
    _test()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

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

    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


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(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> 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',
    #     "i4(i4,i4,i4[:])")(solve)
    # cc.export(
    #     'get_longest',
    #     "i4(i4,i4[:],i4[:],i4[:],i4[:])")(get_longest)
    # cc.compile()
    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":
        # -p: pure python mode
        # if not -p, import compiled module
        # from my_module import solve  # pylint: disable=all
        import

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

    main()

Submission status: Runtime Error

Solution code:
def main():
    def DFS(v):
        if DP[v] != -1: return DP[v]

        res = 0
        for i in G[v]:
            res = max(res, DFS(i) + 1)

        DP[v] = res
        return res


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

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

    DP = [-1] * N

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

    print(ans)


if __name__ == '__main__':
    main()

exit()

Submission status: Runtime Error

Solution code:
def main():
    def DFS(v):
        if DP[v] != -1: return DP[v]

        res = 0
        for i in G[v]:
            res = max(res, DFS(i) + 1)

        DP[v] = res
        return res


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

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

    DP = [-1] * N

    for v in range(N):
        DFS(v)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
"""
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(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> 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":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()
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(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> 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":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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  # sys.maxsize # float("inf")


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.int16)
    next = np.zeros(M + 1, np.int16)
    head = np.zeros(N + 1, np.int16)
    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.int16(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(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> 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":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
# Longest path
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))

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def dfs(root,g,dist,seen):
    if root in seen: return
    seen.add(root)
    for i in g.get(root,[]):
        dist[i]=max(dist.get(i,0),dist.get(root,0)+1)
        indeg[i]-=1
        if indeg[i]==0:
            dfs(i,g,dist,seen)
def buildg(n,e):
    d=defaultdict(list)
    for i in e:
        d[i[0]].append(i[1])
    return d
if __name__=='__main__':
    n,ec=map(int,input().split())
    indeg=[0]*(n+1)
    e=[]
    for i in range(ec):
        e.append(tuple(map(int,input().split())))
        indeg[e[-1][1]]+=1
    g=buildg(n,e)
    dist={}
    seen=set()
    for i in range(1,n+1):
        if indeg[i]==0 and i not in seen:
            dfs(i,g,dist,seen)
    maxx=0
    for i in dist:
        maxx=max(maxx,dist[i])
    print(maxx)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def dfs(root,g,dist,c,seen):
    if root in seen: return
    seen.add(root)
    for i in g[root]:
        dist[i]=max(dist.get(i,0),dist.get(root,0)+1)
        indeg[i]-=1
        if indeg[i]==0:
            dfs(i,g,dist,c+1,seen)
def buildg(n,e):
    d=defaultdict(list)
    for i in e:
        d[i[0]].append(i[1])
    return d
if __name__=='__main__':
    n,ec=map(int,input().split())
    indeg=[0]*(n+1)
    e=[]
    for i in range(ec):
        e.append(tuple(map(int,input().split())))
        indeg[e[-1][1]]+=1
    g=buildg(n,e)
    dist={}
    seen=set()
    for i in range(1,n+1):
        if indeg[i]==0 and i not in seen:
            dfs(i,g,dist,0,seen)
    maxx=0
    for i in dist:
        maxx=max(maxx,dist[i])
    print(maxx)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def dfs(root,g,dist,c,seen):
    if root in seen: return
    seen.add(root)
    for i in g[root]:
        dist[i]=max(dist.get(i,0),c)
        indeg[i]-=1
        if indeg[i]==0:
            dfs(i,g,dist,c+1,seen)
def buildg(n,e):
    d=defaultdict(list)
    for i in e:
        d[i[0]].append(i[1])
    return d
if __name__=='__main__':
    n,ec=map(int,input().split())
    indeg=[0]*(n+1)
    e=[]
    for i in range(ec):
        e.append(tuple(map(int,input().split())))
        indeg[e[-1][1]]+=1
    g=buildg(n,e)
    dist={}
    seen=set()
    for i in range(1,n+1):
        if indeg[i]==0 and i not in seen:
            dfs(i,g,dist,1,seen)
    maxx=0
    for i in dist:
        maxx=max(maxx,dist[i])
    print(maxx)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def solve(root,g,maxx,c,dp):
    if (root,c) in dp: return
    maxx[0]=max(maxx[0],c)
    dp.add((root,c))
    for i in g[root]:
        solve(i,g,maxx,c+1,dp)
    return

def buildg(n,e):
    d=defaultdict(list)
    for i in e:
        d[i[0]].append(i[1])
    return d
if __name__=='__main__':
    n,ec=map(int,input().split())
    e=[]
    for i in range(ec):
        e.append(tuple(map(int,input().split())))
    g=buildg(n,e)
    out=[0]*(n+1)
    q=[]
    for i in range(1,n+1):
        if out[i]==0:
            q.append(i)
    maxx=[0]
    for i in q:
        solve(i,g,maxx,0,set())
    print(maxx[0])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache
@lru_cache(maxsize = None)

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
@lru_cache(maxsize = None)
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))

Submission status: Runtime Error

Solution code:
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(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

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

Submission status: Runtime Error

Solution code:
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 = [0 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

for i in range(N):
    dp[i] = -1
res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))

graph = {i:{} for i in range(n+1)}

visited = [0 for i in range(n+1)]
dp = [0 for i in range(n+1)]


for i in range(m):
    x, y = list(map(int, input().split()))

    graph[x][y] = 1


def dfs(node, graph):
    visited[node] = 1

    for i in graph[node].keys():
        if visited[i] != 1:
            dfs(i, graph)
        
        dp[node] = max(dp[node], 1 + dp[i])

for ele in range(1, n+1):
    if visited[ele] != 1:
        dfs(ele, graph)

# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))

graph = {i:{} for i in range(n+1)}
visited = {i:0 for i in range(n+1)}

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


for i in range(m):
    x, y = list(map(int, input().split()))

    graph[x][y] = 1


def dfs(node, graph):
    visited[node] = 1

    for i in graph[node].keys():
        if visited[i] != 1:
            dfs(i, graph)
        
        dp[node] = max(dp[node], 1 + dp[i])

for ele in range(1, n+1):
    if visited[ele] != 1:
        dfs(ele, graph)

# print(dp)
ans = 0 
    
for i in range(1, n+1):   
    ans = max(ans, dp[i])

print(ans)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))

graph = {i:{} for i in range(n+1)}
visited = {i:0 for i in range(n+1)}

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


for i in range(m):
    x, y = list(map(int, input().split()))

    graph[x][y] = 1


def dfs(node, graph):
    visited[node] = 1

    for i in graph[node].keys():
        if visited[i] != 1:
            dfs(i, graph)
        
        dp[node] = max(dp[node], 1 + dp[i])

for i in range(1, n+1):
    if visited[i] != 1:
        dfs(i, graph)

# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))

graph = {i:{} for i in range(1, n+1)}
visited = {i:0 for i in range(n+1)}

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


for i in range(m):
    x, y = list(map(int, input().split()))

    graph[x][y] = 1

# print(graph)


def dfs(node, graph):
    visited[node] = 1

    for i in graph[node].keys():
        if visited[i] != 1:
            dfs(i, graph)
        
        dp[node] = max(dp[node], 1 + dp[i])

for i in range(1, n+1):
    if visited[i] != 1:
        dfs(i, graph)

print(max(dp))

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
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)



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

print(max(dp))

Submission status: Runtime Error

Solution code:
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges+1)]

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

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)



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

print(max(dp))

Submission status: Runtime Error

Solution code:
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges+1)]

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

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


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)



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

print(max(dp))