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: Wrong Answer

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
z=[0]*(N+1)
key=[0]*(N+1)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=set(i for i in range(1,N+1))
while len(n)>0:
    for i in n:
        if i not in y:
            n.remove(i)
            for j in range(M):
                if i==x[j]:
                    if z[y[j]]<=z[x[j]]:
                        z[y[j]]=z[x[j]]+1
                    x[j],y[j]=0,0
            break
print(z)

Submission status: Wrong Answer

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
z=[0]*(N+1)
key=[0]*(N+1)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=[i for i in range(1,N+1)]
while len(n)>0:
    for i in n:
        key=[0]*(N+1)
        if i not in y:
            n.remove(i)
            for j in range(M):
                if i==x[j]:
                    if key[y[j]]==0:
                        z[y[j]]=z[x[j]]+1
                        key[y[j]]=1
                    x[j],y[j]=0,0
            break
print(max(z))

Submission status: Wrong Answer

Solution code:
N, M = map(int,raw_input().split())
gra = [set() for n in range(N)]

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  start.discard(y-1)

mem = [None for n in range(N)]
q = list(start)
for i in q : mem[i] = 0

longest = 0
while q :
  cur = q.pop()
  longest = max(longest, mem[cur])
  
  for nxt in gra[cur] :
    if mem[nxt] is not None : 
      longest = max(longest, mem[cur] + mem[nxt])
      continue
    mem[nxt] = mem[cur] + 1
    q.append(nxt)

print longest

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp_s=[0 for _ in range(n+1)]
dp=[0 for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    dp_s[x]=max(dp_s[x],1+dp_s[y])
    dp[y]=max(dp[y],dp[x]+dp_s[x])
print(max(dp))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[0 for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    dp[y]=max(dp[y],dp[x]+1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    V, E = map(int, input().split())
    # is_visited = [False] * V
    indeg = [0] * V  # 流入量
    # 隣接リスト
    G = defaultdict(lambda: [])

    for i in range(E):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        G[s].append(t)
        indeg[t] += 1

    # print(G, indeg, is_visited)
    # out = []
    dp = [0] * V

    def bfs(s):
        q = deque()
        q.append(s)
        # is_visited[s] = True
        while q:
            u = q.popleft()
            # out.append(u)
            # print(u, out)
            for v in G[u]:
                indeg[v] -= 1
                dp[v] = max(dp[v], dp[u] + 1)
                if indeg[v] == 0:  # and (not is_visited[v]):
                    q.append(v)
                    # is_visited[v] = True

    def topological():
        for u in range(V):
            if indeg[u] == 0:  # and (not is_visited[u]):
                bfs(u)

        print(max(dp))

    topological()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    V, E = map(int, input().split())
    is_visited = [False] * V
    indeg = [0] * V  # 流入量
    # 隣接リスト
    G = defaultdict(lambda: [])

    for i in range(E):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        G[s].append(t)
        indeg[t] += 1

    # print(G, indeg, is_visited)
    out = []
    dp = [0] * (10 ** 5 + 100)

    def bfs(s):
        q = deque()
        q.append(s)
        is_visited[s] = True
        while q:
            u = q.popleft()
            out.append(u)
            # print(u, out)
            for v in G[u]:
                indeg[v] -= 1
                if indeg[v] == 0:  # and (not is_visited[v]):
                    q.append(v)
                    is_visited[v] = True
                dp[v] = max(dp[v], dp[u] + 1)

    def topological():
        for u in range(V):
            if indeg[u] == 0:  # and (not is_visited[u]):
                bfs(u)

        print(max(dp))

    topological()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    V, E = map(int, input().split())
    is_visited = [False] * V
    indeg = [0] * V  # 流入量
    # 隣接リスト
    G = defaultdict(lambda: [])

    for i in range(E):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        G[s].append(t)
        indeg[t] += 1

    # print(G, indeg, is_visited)
    out = []
    dp = [0] * (10 ** 5 + 100)

    def bfs(s):
        q = deque()
        q.append(s)
        is_visited[s] = True
        while q:
            u = q.popleft()
            out.append(u)
            # print(u, out)
            for v in G[u]:
                indeg[v] -= 1
                if indeg[v] == 0:  # and (not is_visited[v]):
                    q.append(v)
                    is_visited[v] = True
                    dp[v] = max(dp[v], dp[u] + 1)

    def topological():
        for u in range(V):
            if indeg[u] == 0:  # and (not is_visited[u]):
                bfs(u)

        print(max(dp))

    topological()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    V, E = map(int, input().split())
    is_visited = [False] * V
    indeg = [0] * V  # 流入量
    # 隣接リスト
    G = defaultdict(lambda: [])

    for i in range(E):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        G[s].append(t)
        indeg[t] += 1

    # print(G, indeg, is_visited)
    out = []
    dp = [0] * (10 ** 5 + 100)

    def bfs(s):
        q = deque()
        q.append(s)
        is_visited[s] = True
        while q:
            u = q.popleft()
            out.append(u)
            # print(u, out)
            for v in G[u]:
                indeg[v] -= 1
                if (indeg[v] == 0) and (not is_visited[v]):
                    q.append(v)
                    is_visited[v] = True
                    dp[v] = max(dp[v], dp[u] + 1)

    def topological():
        for u in range(V):
            if (indeg[u] == 0) and (not is_visited[u]):
                bfs(u)

        print(max(dp))

    topological()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
L = []
DP = [0 for _ in range (N + 1)]
for _ in range(M):
    p = list(map(int,input().split()))
    DP[p[1]] = max (DP[p[1]], DP[p[0]] + 1)
# DP[i] = 各頂点(i番目)の最大値 
# あるpath p が k -> l に張ってるなら
# DP[l] = max (DP[l], DP[k] + 1)
ans = 0
for i in range (N+1):
    ans = max(ans, DP[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(m)]
# dp[i+1][j]:i個目までの頂点を考えた時の点jで終わる有向パスの最長の長さ

dp=np.zeros(n+1,np.int64)
for xyi in xy:
      dp[xyi[1]]=max(dp[xyi[0]]+1,dp[xyi[1]])
print(np.max(dp))

Submission status: Wrong Answer

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


def read():
    N, M = map(int, input().strip().split())
    E_out = [list() for i in range(N)]
    E_in = [list() for i in range(N)]
    for i in range(M):
        x, y = map(int, input().strip().split())
        E_out[x-1].append(y-1)  # x -> E_out[x]
        E_in[y-1].append(x-1)   # E_in[x] -> x
    return N, M, E_in, E_out


def solve(N, M, E_in, E_out):
    dp = [0 for i in range(N)]
    q = deque()
    for x in range(N):
        if len(E_out[x]) == 0:
            q.append(x)
    while q:
        x = q.pop()
        for y in E_in[x]:
            dp[y] = dp[x] + 1
            q.append(y)
    return max(dp)


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

Submission status: Wrong Answer

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


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


def solve(N, M, E_in, E_out):
    dp = [0 for i in range(N)]
    for i in range(N):
        for e_in in E_in[i]:
            dp[i] = max(dp[i], dp[e_in] + 1)
        for e_out in E_out[i]:
            dp[e_out] = max(dp[e_out], dp[i] + 1)
    return max(dp)


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

Submission status: Wrong Answer

Solution code:
#input
N, M = map(int, input().split())
x, y = [0]*M, [0]*M
for i in range(M):
    x[i], y[i] = map(int, input().split())

#output
#便宜的にすべての点を-1しておく。
#dp[i]を頂点iから始まるpathで最長の長さとする。
#dp[i] = max(dp[v]+1)(vは頂点iから到達できる任意の頂点)
z = [[]] * N
for xitem in x:
    z[xitem-1] = [yitem-1 for i, yitem in enumerate(y) if x[i] == xitem]

dp = [0] * N

for i in range(N):
    for v in z[i]:
        dp[i] = max(dp[i], dp[v]+1)

print(max(dp)+1)

Submission status: Wrong Answer

Solution code:
def main():
  n, m = map(int, input().split())
  tree_from = [[] for _ in range(n)]
  tree_to = [[] for _ in range(n)]
  for i in range(m):
    x, y = map(int, input().split())
    tree_from[y-1].append(x-1)
    tree_to[x-1].append(y-1)
  
  dp = [0]*n
  for i in range(n):
    for value in tree_from[i]:
      if dp[i] < dp[value]+1:
        dp[i] = dp[value]+1
    for value in tree_to[i]:
      if dp[value] < dp[i]+1:
        dp[value] = dp[i]+1
  print(max(dp))

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ans = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    ans[y - 1] = max(ans[y - 1], ans[x - 1] + 1)

print(max(ans))

Submission status: Wrong Answer

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

dist = [0]*n
for v, v2 in edges:
    if dist[v2] <= dist[v]-1:
        continue
    dist[v2] = dist[v]-1

print(-min(dist))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edges = []
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges.append((x, y))

dist = [0]*n
for v, v2 in edges:
    if dist[v2] <= dist[v]-1:
        continue
    dist[v2] = dist[v]-1

print(-min(dist))

Submission status: Wrong Answer

Solution code:
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
S = [i for i in range(n) if I[i] == 0]
L = [0 for i in range(n)]
while S:
    i = S.pop()
    while G[i]:
        j = G[i].pop()
        I[j] -= 1
        if I[j] == 0:
            S.append(j)
            L[j] = max(L[j], L[i]+1)
print(max(L))

Submission status: Wrong Answer

Solution code:
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()
L = [LIST() for i in range(M)]
graph = defaultdict(list)
for a, b in L:
    graph[a-1].append(b-1)
ans = 0
dist = [0] * N

for i in range(N):
    q = [i]
    while q:
        a = q.pop()
        for node in graph[a]:
            if dist[a] + 1 > dist[node]:
                dist[node] = dist[a] + 1
                ans = dist[node]
                q.append(node)
    # if ans < max(dist):
    #     ans = max(dist)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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)
topo = [[topo[0],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]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

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

#dp = dp2(0, 2, N)
dp = [[0, []] for i1 in range(N+1)]


for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    if dp[x[i][1]][1] != []:
        for a in dp[x[i][1]][1]:
            dp[a][0] = max(dp[x[i][1]][0] + 1, dp[a][0])

#print(dp)
print(max([row[0] for row in dp]))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  dp[b-1]=max(dp[b-1],dp[a-1]+1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import numpy as np
n,m = mi()
dp = [[0]*2 for i in range(n)]
dp = np.array(dp)
for i in range(m):
    x,y = mi()
    x,y = x-1,y-1
    if dp[y][1]==0:
        dp[x][1] = max(1,dp[x][1])
    else:
        dp[x][1] = max(dp[x][1],dp[y][1]+1)

    if dp[x][0]==0:
        dp[y][0] = max(1,dp[y][0])
    else:
        dp[y][0] = max(dp[y][0],dp[x][0]+1)


print(max(dp[:,0]+dp[:,1]))

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = [int(i) for i in input().split()]
rec = {i: 0 for i in range(1, n+1)}
paths = {}
for _ in range(m):
    f, t = [int(i) for i in input().split()]
    if f not in paths:
        paths[f] = set()
    paths[f].add(t)

# 1 ~ n のそれぞれからスタート
for i in range(1, n+1):
    stack = deque()
    # 現在位置と経路の長さ
    stack.append((i, 0))
    while stack:
        now, length = stack.pop()
        # 記録済みならその値を使用
        if rec[now] > 0:
            length = length + rec[now]
            rec[i] = length
            continue
        # 行き止まりなら記録して終了
        if paths.get(now) is None or len(paths[now]) == 0:
            rec[i] = max(rec[i], length)
            continue
        # そうでなければ、次へ進む
        for j in paths[now]:
            stack.append((j, length+1))

print(max(rec.values()))

Submission status: Wrong Answer

Solution code:
inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [0]*N

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]

    dp[y-1] = max(dp[y-1], dp[x-1]+1)

print(max(dp))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
adj = {}
indegrees = [0 for _ in range(n+1)]
for _ in range(m):
  cur, nxt = map(int, input().split())
  adj[cur] = adj.get(cur, []) + [nxt]
  indegrees[nxt] += 1
  
stack = []
for i in range(1, n+1):
  if indegrees[i] == 0:
    stack.append(i)
    
dp = [0 for _ in range(n+1)]
    
while stack:
  cur = stack.pop()
  for nxt in adj.get(cur, []):
    indegrees[nxt] -= 1
    if indegrees[nxt] == 0:
      stack.append(nxt)
    dp[nxt] = dp[cur] + 1
print(max(dp))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	if visit[node] ==  False:
		# for i in adj[node]:
			# top_sort(i)
		stack.append(node)
		visit[node] = True
for a in range(N):
	if visit[a] == False:
		top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	if visit[node] ==  False:
		for i in adj[node]:
			top_sort(i)
		stack.append(node)
		visit[node] = True
# for a in range(N):
	# top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	if visit[node] ==  False:
		for i in adj[node]:
			top_sort(i)
		# stack.append(node)
		visit[node] = True
# for a in range(N):
	# top_sort(a)
stack.reverse()
# for p in stack:
# 	for q in adj[p]:
# 		dp[q] = max(dp[q], dp[p] + 1)
# # print(dp)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	# dp[y-1] = 1
# visit = [False for n in range(N + 1)]
# stack = []
# def top_sort(node):
# 	if visit[node] ==  False:
# 		for i in adj[node]:
# 			top_sort(i)
# 		stack.append(node)
# 		visit[node] = True
# for a in range(N):
# 	top_sort(a)
# stack.reverse()
# for p in stack:
# 	for q in adj[p]:
# 		dp[q] = max(dp[q], dp[p] + 1)
# # print(dp)
print(max(dp))

Submission status: Wrong Answer

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

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

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

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

print(max(dp))

Submission status: Wrong Answer

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

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

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


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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
infi=10**10
#topological sort
#通常のグラフ構成のグラフ
graph1=[[]for _ in range(n+1)]
#入ってくる辺の数を記録するグラフ
graph2=[ 0 for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    graph1[x].append(y)
    graph2[y]+=1
#start地点になるのは入ってくる辺の数が0の点
start=[]
for i in range(1,n+1):
    if graph2[i]==0:
        start.append(i)
start2=start[::]
#start地点から
#①topoリストに加える
#②隣接点の入ってくる辺の数を減らす
#③入ってくる辺の数が0になったらstartに加える
#を繰り返す
#※今回はtopoに加えるのは本質ではない。
#topoに加えていく順序で見ていきながら距離を入れていく。
# topo=[]
dist=[infi]*(n+1)
for i in start:
    dist[i]=0
while start:
    a=start.pop()
    kyori=dist[a]
#     topo.append(a)
    for b in graph1[a]:
        graph2[b]-=1
        if graph2[b]==0:
            start.append(b)
            dist[b]=min(dist[b],dist[a]+1)
print(max(dist[1:]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))

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

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

queque = []
for i in range(n):
    queque += [(i, t) for t in edges[i]]
    while len(queque) > 0:
        from_node, to_node = queque.pop(0)
        dp[i][to_node] = max(dp[i][to_node], dp[from_node][to_node] + 1)
        queque += [(to_node, t) for t in edges[to_node]]

print(max(max(dp)))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque


def solve():
    N, M = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    G = defaultdict(list)
    in_edge = [0] * N
    for x, y in zip(m, m):
        G[y-1].append(x-1)
        in_edge[x-1] += 1

    dp = [0] * N
    q = deque(i for i, x in enumerate(in_edge) if not x)
    q_enqueue = q.append
    q_dequeue = q.popleft
    print(in_edge)
    while(q):
        x = q_dequeue()
        for j in G[x]:
            in_edge[j] -= 1
            dp_x = dp[x]
            if not in_edge[j]:
                q_enqueue(j)
                if dp[j] < dp_x + 1:
                    dp[j] = dp_x + 1
    return max(dp)


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	n,m=map(int,input().split())
	
	dp=[0]*(n+1)
	li=[]
	for i in range(m):
		x,y=map(int,input().split())
		li.append((x,y))
		dp[y]=max(dp[y],dp[x]+1)
	
	ans=max(dp)
	while True:
		for x,y in li:
			dp[y] = max(dp[y], dp[x] + 1)
		if max(dp)==ans:
			break
		else:
			ans=max(dp)
		
		
		
	
	print(ans)
	
	
	
	
	
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	n,m=map(int,input().split())
	
	dp=[0]*(n+1)
	
	for i in range(m):
		x,y=map(int,input().split())
		dp[y]=max(dp[y],dp[x]+1)
	
	print(max(dp))
	
	
	
	
	
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))
move.sort(key=itemgetter(0))

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

def findpath(now_x):
    if now_x <= done_n:
        return dp[now_x]
    for x,y in move:
        if now_x == x:
            dp[now_x] = max(dp[now_x],findpath(y) + 1)
        if now_x < x:
            break
    return dp[now_x]

maxpath = 0
for do_n in range(1,N+1):
    done_n = do_n - 1
    maxpath = max(maxpath,findpath(do_n))
    print(dp)

print(maxpath)

Submission status: Wrong Answer

Solution code:
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))

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

def findpath(now_x):
    #if now_x <= done_n:
    #    return dp[now_x]
    for x,y in move:
        if now_x == x:
            dp[now_x] = max(dp[now_x],findpath(y) + 1)
    return dp[now_x]

maxpath = 0
for do_n in range(1,N+1):
    done_n = do_n - 1
    maxpath = max(maxpath,findpath(do_n))
    print(dp)

print(maxpath)

Submission status: Wrong Answer

Solution code:
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))

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

def findpath(now_x):
    if now_x <= done_n:
        return dp[now_x]
    for x,y in move:
        if now_x == x:
            dp[now_x] = max(dp[now_x],findpath(y) + 1)
    return dp[now_x]

maxpath = 0
for do_n in range(1,N+1):
    done_n = do_n - 1
    maxpath = max(maxpath,findpath(do_n))
    print(dp)

print(maxpath)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline  #文字列入力では注意！
from copy import deepcopy
from functools import lru_cache
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
s = set()
for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    s.add(y)
    graph[x].append(y)

@lru_cache(maxsize = None)
def dfs(x):
    print(x,graph[x])
    if not graph[x]:
        return 0
    stack = deepcopy(graph[x])
    ret = 0
    while stack:
        now = stack.pop(0)
        ret = max(ret,dfs(now)+1)
    return ret

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,m=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(m)]
length=[0]*(n+1)
for i in range(m):
    x,y=xy[i]
    length[y]=max(length[y],length[x]+1)
print(max(length))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

n,m = mii()

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

for i in range(m):
    x,y = mii()
    dp[y] = max(dp[x]+1,dp[y])

print(max(dp))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 24 14:37:00 2020

@author: matsui
"""

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

g=dict()
h=[0]*(N+1)
for i in range(1,N+1):
    g[i]=[]
  
for i in range(M):
    x,y=map(int,input().split())
    g[x].append(y)
    h[y]+=1
     
st=[]

for i in range(1,N+1):
    if h[i]==0: 
        st.append(i)
    
ans=[]
dp=[0]*(N+1)

while(len(st)):
    i=st[0]
    st.remove(st[0])
    
    ans.append(i)
    
    for j in g[i]:
        h[j]-=1
        if h[j]==0: 
            st.append(j)
            if dp[i]+1>dp[j]: 
                dp[j]=dp[i]+1
        
print(ans)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
dp = [0 for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x,y = x-1,y-1
    dp[y] = max(dp[x]+1,dp[y])
print(max(dp))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
res ={}
for _ in range(m):
    x,y = input().split()
    res[x] = res.get(x,[]) + [y]
memo = {} #nodeを始点としたパスの最長長さ
def dfs(node):
    if node in memo:
        return memo[node]
    a = 0
    for n in res.get(node,[]):
        a = max(a,dfs(n)+1)
    memo[node] = a
    return memo[node]

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N,M = map(int, input().split())
t_table = {}
for i in range(M):
	x,y = map(int, input().split())
	if x-1 in t_table: t_table[x-1].append(y-1)
	else: t_table[x-1] = [y-1]
mem = np.zeros(N, dtype='int32')
ans = 0
ccheck = [True for _ in range(N)]
NodeList = np.array([i for i in range(N)])
while True:
	p_mem = mem.copy()
	p_cnt = np.zeros(N, dtype='int32')
	for i in NodeList[ccheck]:
		if i in t_table :
			p_cnt[t_table[i]] = 1
	mem+=p_cnt
	ccheck = (mem!=p_mem)
	if((mem==p_mem).all()):
	 	print(ans)
	 	break
	ans += 1