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:
import sys
sys.setrecursionlimit(10**5+10)
def memo(v):
    if dp[v]!=-1:return dp[v]
    ans = 0
    for next_v in g[v]:
        ans = max(ans,memo(next_v)+1)
    dp[v] = ans
    print("dp={}".format(dp))
    return ans

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

ans = 0
for v in range(1,n+1):
    ans = max(ans, memo(v))
    
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

x_list = []
y_list = []
for i in range(M):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

dp = [0]*(N+1)
for i in range(M):
    dp[y_list[i]] = max(dp[y_list[i]], dp[x_list[i]]+dp[y_list[i]], dp[x_list[i]]+1)

print(max(dp))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

x_list = []
y_list = []
for i in range(M):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

dp = [0]*(N+1)
for i in range(M):
    dp[y_list[i]] = max(dp[y_list[i]], dp[x_list[i]]+1)

print(max(dp))

Submission status: Wrong Answer

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

def main(n,m,g):
    d = [-1 for i in range(n)]
    visited = [False for i in range(n)]
    temp = [[] for i in range(n)]
    ans = 0
    #print(g)
    #print(visited)
    for i in range(n):
        if d[i] != -1:
            continue
        q = [[i,-1]]
        prev = [-1]
        while q:
            idx = q.pop(-1)
            #print(idx,temp,q)
            if not visited[idx[0]]:
                visited[idx[0]] = True
                if g[idx[0]]:
                    prev.append(idx[0])
                    for j in g[idx[0]]:
                        q.append([j,idx[0]])
                else:
                    d[idx[0]] = 0
                    temp[idx[1]].append(0)
                    if idx[1]==-1:
                        break
                    if prev[-1]!=-1 and q:
                        #print(q)
                        if q[-1][1]==idx[1]:
                            continue
                    bef = prev.pop(-1)
                    q.append([bef,prev[-1]])
            else:
                if d[idx[0]] == -1:
                    d[idx[0]] = 1 + max(temp[idx[0]])
                    if idx[1]!=-1:
                        temp[idx[1]].append(d[idx[0]])
                else:
                    if idx[1]!=-1:
                        temp[idx[1]].append(d[idx[0]])
                    if prev[-1]!=-1 and q:
                        #print(q)
                        if q[-1][1]==idx[1]:
                            continue
                if idx[1]==-1:
                    break
                bef = prev.pop(-1)
                q.append([bef,prev[-1]])   
        ans = max(ans,d[i])
    print(ans)                     
                

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

Submission status: Wrong Answer

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

def main(n,m,g):
    d = [-1 for i in range(n)]
    visited = [False for i in range(n)]
    temp = [[] for i in range(n)]
    ans = 0
    #print(g)
    #print(visited)
    for i in range(n):
        if d[i] != -1:
            continue
        q = [[i,-1]]
        prev = [-1]
        while q:
            idx = q.pop(-1)
            #print(idx,temp,q)
            if not visited[idx[0]]:
                visited[idx[0]] = True
                if g[idx[0]]:
                    prev.append(idx[0])
                    for j in g[idx[0]]:
                        q.append([j,idx[0]])
                else:
                    d[idx[0]] = 0
                    temp[idx[1]].append(0)
                    if idx[1]==-1:
                        break
                    if prev[-1]!=-1 and q:
                        #print(q)
                        if q[-1][1]==idx[1]:
                            continue
                    bef = prev.pop(-1)
                    q.append([bef,prev[-1]])
            else:
                if d[idx[0]] == -1:
                    d[idx[0]] = 1 + max(temp[idx[0]])
                    if idx[1]!=-1:
                        temp[idx[1]].append(d[idx[0]])
                else:
                    if idx[1]!=-1:
                        temp[idx[1]].append(d[idx[0]])
                    if prev[-1]!=-1 and q:
                        #print(q)
                        if q[-1][1]==idx[1]:
                            continue
                if idx[1]==-1:
                    break
                bef = prev.pop(-1)
                q.append([bef,prev[-1]])   
    print(max(max(d),0))                     
                

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

Submission status: Wrong Answer

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

def main(n,m,g):
    d = [-1 for i in range(n)]
    visited = [False for i in range(n)]
    temp = [[] for i in range(n)]
    ans = 0
    #print(g)
    #print(visited)
    for i in range(n):
        if d[i] != -1:
            continue
        q = [[i,-1]]
        prev = [-1]
        while q:
            idx = q.pop(-1)
            #print(idx,temp,q)
            if not visited[idx[0]]:
                visited[idx[0]] = True
                if g[idx[0]]:
                    prev.append(idx[0])
                    for j in g[idx[0]]:
                        q.append([j,idx[0]])
                else:
                    d[idx[0]] = 0
                    temp[idx[1]].append(0)
                    if idx[1]==-1:
                        break
                    if prev[-1]!=-1 and q:
                        #print(q)
                        if q[-1][1]==idx[1]:
                            continue
                    bef = prev.pop(-1)
                    q.append([bef,prev[-1]])
            else:
                if d[idx[0]] == -1:
                    d[idx[0]] = 1 + max(temp[idx[0]])
                    temp[idx[1]].append(d[idx[0]])
                else:
                    temp[idx[1]].append(d[idx[0]])
                    if prev[-1]!=-1 and q:
                        #print(q)
                        if q[-1][1]==idx[1]:
                            continue
                if idx[1]==-1:
                    break
                bef = prev.pop(-1)
                q.append([bef,prev[-1]])   
        ans = max(ans,d[i])
    print(ans)                     
                

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

Submission status: Wrong Answer

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

def main(n,m,g):
    d = [-1 for i in range(n)]
    visited = [False for i in range(n)]
    temp = [[] for i in range(n)]
    ans = 0
    #print(g)
    #print(visited)
    for i in range(n):
        if d[i] != -1:
            continue
        q = [[i,-1]]
        prev = [-1]
        while q:
            idx = q.pop(-1)
            #print(idx,temp,q)
            if not visited[idx[0]]:
                visited[idx[0]] = True
                if g[idx[0]]:
                    prev.append(idx[0])
                    for j in g[idx[0]]:
                        q.append([j,idx[0]])
                else:
                    d[idx[0]] = 0
                    temp[idx[1]].append(0)
                    if idx[1]==-1:
                        break
                    if prev[-1]!=-1 and q:
                        #print(q)
                        if q[-1][1]==idx[1]:
                            continue
                    bef = prev.pop(-1)
                    q.append([bef,prev[-1]])
            else:
                if d[idx[0]] == -1:
                    d[idx[0]] = 1 + max(temp[idx[0]])
                if idx[1]==-1:
                    break
                temp[idx[1]].append(d[idx[0]])
                bef = prev.pop(-1)
                q.append([bef,prev[-1]])   
        ans = max(ans,d[i])
    print(ans)                     
                

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
if __name__=='__main__':
	N, M=list(map(int,input().split()))
	paths=[[0 for i in range(N)] for j in range(N)]
	for i in range(M):
		p,q=list(map(int,input().split()))
		paths[p-1][q-1] =1
	for j in range(N):
		for i in range(N):
			if i != j and paths[i][j] !=0:
				Max =0
				for k in range(N):
					if k !=i:
						Max=max(Max,paths[k][i]+1)
					else:
						continue
				paths[i][j]=Max
				for l in range(N):
					if l != j and l !=i and paths[j][l] !=0:
						paths[j][l] =max(paths[j][l],paths[i][j]+1)
			else:
				continue
	print(max(list(map(max,paths))))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
N,M=map(int, input().split())
G = {i: [] for i in range(1, N+1)}
deg = [0]*(N+1)
for _ in range(M):
    x,y=map(int,input().split())
    G[x].append(y)
    deg[y] += 1

from collections import deque, defaultdict
S = [i for i in range(1, N+1) if deg[i]==0]
dp = [0]*(N+1)

def topological_sort(adj, indeg):
    """
    幅優先探索によるトポロジカルソート
    O(|V|+|E|)

    adj: 隣接リスト
    indeg: 各ノード入次数を管理するリスト

    ret: トポロジカルソートされたリスト
    """
    is_visited = [0]*(N+1)
    ret = []

    def bfs(s):
        """
        sからBFSする
        """
        queue = deque([s])
        is_visited[s] = 1
        while queue:
            u = queue.popleft()
            # queueには入次数0のノードが入っているのでretに追加
            # ret.append(u)

            for v in adj[u]: # uの子ノードを探索
                indeg[v] -= 1 #探索したら子の次数を減らす
                if (indeg[v] == 0) and (not is_visited[v]):
                    # 入次数0かつ未訪問なら
                    queue.append(v)
                    dp[v] = max(dp[v], dp[u]+1)
                    is_visited[v] = 1
    
    for u in range(1, N+1):
        if (indeg[u]==0) and (not is_visited[u]):
            # 流入0かつ未訪問なら
            bfs(u) # uからBFS
    
    # return ret

topological_sort(G, deg)
print(max(dp))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())  #vertices,edges
graph=[[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    graph[x-1][y-1]=1
dp=[0 for _ in range(n)]
for ver in range(n):
    for i in range(n):
        if graph[ver][i]==1:
            dp[ver]=max(dp[ver],1+dp[i])
print(max(dp)+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
e1=[]
e2=[]
for i in range(m):
    t1,t2=map(int,input().split())
    e1.append(t1)
    e2.append(t2)
dp=[0 for i in range(n+1)]
ans=0
for i in range(m):
    dp[e2[i]]=max(dp[e2[i]],1+dp[e1[i]])
    ans=max(ans,dp[e2[i]])
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [-1]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    #    x.append(x_in)
    #    y.append(y_in)
    d.append((x_in, y_in))

memo = [-1] * (n + 1)
ans = -1


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in, y_in in d:
            if x_in == i:
                tmp = dp(y_in) + 1
                if tmp > ret:
                    ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i in x:
    if memo[i] == -1:
        dp(i)

print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())

G=[[] for _ in range(N)]
G2 = [[] for _ in range(N)]
for i in range(M):
  x,y=map(int,input().split())
  x -= 1
  y -= 1
  G[x].append(y)
  G2[y].append(x)
  
start_list=[]
for i in range(N):
  if len(G[i])==0:
    start_list.append(i)
    
from collections import deque

def bfs(s):
    seen = [0]*(N+1)
    d = [0]*(N+1)
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G2[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
        else:
          d[b] = max(d[b],d[a]+1)
    return d
  
ans = 0
for start in start_list:
  d = bfs(start)
  ans = max(ans, max(d))
  
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
dp = [0] * (n+1)
x, y = [], []
for i in range(m):
    xx, yy = map(int, input().split())
    x.append(xx); y.append(yy)
for i in x:
    dp[i] += 1
for i in range(m):
    xx, yy = x[i], y[i]
    dp[xx] = max(dp[xx], dp[yy]+1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
  
memo = [0] * n

for i in range(m):
  xi, yi = map(int, input().split())
  xi, yi = xi - 1, yi - 1
  memo[yi] = max(memo[yi], memo[xi] + 1)
  
print(max(memo))

Submission status: Wrong Answer

Solution code:
import collections
import sys
sys.setrecursionlimit(10**6)
def dp(node,cache,edge):
  if node in cache:
    return cache[node]
  lcl_max=0
  for child in edge[node]:
    cache[child]=dp(child,cache,edge)
    lcl_max=max(lcl_max,1+cache[child])
  return lcl_max
 
max_dis=0
cache,edge={},collections.defaultdict(list)
n,m=map(int,input().split())
for _ in range(m):
  a,b=map(int,input().split())
  edge[a].append(b)
for node in range(1,n+1):
  max_dis=max(max_dis,dp(node,cache,edge))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
to = [False]*N
for i in range(M):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  to[b-1] = True

ans = 0
length = [0]*N
for i in range(N):
  if to[i]==False:
    d = deque()
    d.append([i,0])
    while len(d)>0:
      v,cnt = d.popleft()
      for w in edge[v]:
        length[w] = cnt+1
        d.append([w,cnt+1])
ans = max(length)
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(num):
    if dp[num] != -1:
        return dp[num]

    res = 0
    for obj in G[num]:
        res = max(res, dfs(obj) + 1)

    dp[num] = res
    return res


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

dp = [-1] * N
G = {i:[] for i in range(N)}

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[list(map(int,input().split())) for _ in range(m)]
edge=sorted(edge,key=lambda x:x[0])
dp=[0]*(n+1)
for _ in range(10):
  for a,b in edge:
    dp[b]=max(dp[b],dp[a]+1)
print(max(dp))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

def judge(index):
  if dp[index] != -1:
    return dp[index]
  else:
    edges = 0
    for i in nodes[index]:
      edges = max(edges, 1+judge(i))
    dp[index] = edges
    print(index,dp)
    return edges

answer = 0
for i in range(N):
  answer = max(answer, judge(i))
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
from collections import defaultdict


g = None


@lru_cache(100000)
def f(x):
    ret = 0
    for y in g[x]:
        ret = max(ret, f(y) + 1)
    return ret

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, M = map(int, input().split())
    dp = [0] * (N+1)

    for _ in range(M):
        x, y = map(int, input().split())
        if x != y:
            dp[y] = max(dp[y],dp[x]+1)
    print(max(dp))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, M = map(int, input().split())
    dp = [0] * (N+1)

    for _ 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:
import sys
readline = sys.stdin.readline
def LPP():
    n, m = map(int, readline().split())
    edges = []
    for _ in range(m):
        temp = list(map(int, readline().split()))
        edges.append(temp)
    edges.sort(key=lambda x: x[0])
    i = 0
    maxi = 0
    while i < len(edges):
        temp_edge = edges[i].copy()
        j = 0
        while j < len(edges):
            if len(edges[j:]) < maxi:
                break
            if edges[j][0] == temp_edge[-1]:
                temp_edge.append(edges[j][1])
                j = 0
            else:
                j += 1
        i += 1
        maxi = max(maxi, len(temp_edge))
        temp_edge.clear()
    print(maxi-1, end="")

LPP()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
dp = {}

for i in range(M):
    Start_Point,Stop_Point =  map(int,input().split())
    if Start_Point in dp.keys():
        if Stop_Point in dp.keys():
            dp[Stop_Point] = max(dp[Start_Point] + 1,dp[Stop_Point])
        else:
            dp[Stop_Point] = dp[Start_Point] + 1
    else:
        dp[Stop_Point] = 1
    
print(max(dp.values()))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
dp = {}

for i in range(M):
    Start_Point,Stop_Point =  map(int,input().split())
    if Start_Point in dp.keys():
        if Stop_Point in dp.keys():
            dp[Stop_Point] = max(dp[Start_Point] + 1,dp[Stop_Point])
        else:
            dp[Stop_Point] = dp[Start_Point] + 1
    else:
        dp[Stop_Point] = 1
    
   
print(max(dp.values()))

Submission status: Wrong Answer

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

for i in range(M):
    Start_Point,Stop_Point =  map(int,input().split())
    Max_Number = max(dp[Start_Point - 1])
    dp[Stop_Point - 1][Start_Point - 1] = Max_Number + 1

print(max(map(lambda x:max(x),dp)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)
# 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)
print(graph)
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: Wrong Answer

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

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

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


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
                    # debug(": i, v1, next_path[v1]", i, v1, next_path[v1])
        if exists != i:
            # no more pathes
            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):
        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
"""


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(T1)
    >>> 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: Wrong Answer

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

    def get_longest(start):
        next = edges.get(start)
        if not next:
            longest[start] = 0
            return 0

        for v in next:
            if longest.get(v) == None:
                longest[v] = get_longest(v)

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve(g,indeg,outdeg):
    select=1
    selectin=indeg[1]
    selectout=outdeg[1]
    for i in range(1,n+1):
        if outdeg[i]<selectout and indeg[i]>=selectin:
            select=i
            selectin=indeg[i]
            selectout=outdeg[i]
    c=0
    seen=set()
    maxx=0
    while select!=None:
        seen.add(select)
        c+=1
        maxx=max(maxx,c)
        for i in g[select]:
            outdeg[i]-=1
        temp=None
        for i in g[select]:
            if not temp and i not in seen:
                temp=i
                tempin=indeg[i]
                tempout=outdeg[i]
            elif i not in seen and outdeg[i]<tempout and indeg[i]>=tempin:
                temp=i
                tempin=indeg[i]
                tempout=outdeg[i]
        if temp==None:
            c=0
            for i in range(1,n+1):
                if not temp and i not in seen:
                    temp=i
                    tempin=indeg[i]
                    tempout=outdeg[i]
                elif i not in seen and outdeg[i]<tempout and indeg[i]>=tempin:
                    temp=i
                    tempin=indeg[i]
                    tempout=outdeg[i]
        select=temp
    return maxx-1
        
def buildg(n,e):
    d=defaultdict(list)
    for i in e:
        d[i[1]].append(i[0])
    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)
    outdeg=[0]*(n+1)
    indeg=[0]*(n+1)
    for i in e:
        indeg[i[1]]+=1
        outdeg[i[0]]+=1
    print(solve(g,indeg,outdeg))

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n, adj, sequence = getInputs()

    distance = [-1] * n

    toVisit = deque(sequence)

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

        if len(adj[curr]) == 0:
            distance[curr] = 0
        else:
            for dest in adj[curr]:
                if distance[dest] >= 0:
                    if (1 + distance[dest]) > distance[curr]:
                        distance[curr] = 1 + distance[dest]
                else:
                    toVisit.append(curr)
                    break

    print(max(distance))

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

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

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

        requirements[a - 1][1] += 1

    requirements.sort(key=(lambda x: x[1]))
    sequence = map(lambda x: x[0], requirements)

    return n, adj, sequence

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n, adj, sequence = getInputs()

    distance = [-1] * n

    toVisit = deque(sequence)

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

        if len(adj[curr]) == 0:
            distance[curr] = 0
        else:
            for dest in adj[curr]:
                if distance[dest] >= 0:
                    distance[curr] = max(distance[curr], 1 + distance[dest])
                else:
                    toVisit.append(curr)
                    break

    print(max(distance))

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

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

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

        requirements[a - 1][1] += 1

    requirements.sort(key=(lambda x: x[1]))
    sequence = map(lambda x: x[0], requirements)

    return n, adj, sequence

main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
    N,M=tuple(map(int,sys.stdin.readline().split()))
    dp=[0 for _ in range(N+1)]
    for _ in [0]*M:
        x,y=tuple(map(int,sys.stdin.readline().split()))
        dp[y]=max(dp[y],dp[x]+1)
    print(max(dp))
if __name__=='__main__':main()

Submission status: Wrong Answer

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


def dfs(v, parent):
    if dist[parent] < dist[v]+1:
        dist[parent] = dist[v]+1
    visited[v] = 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)


dist = [0]*n
visited = [0]*n

for i in range(n):
    if visited[i]:
        continue
    dfs(i, -1)

print(max(dist))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(N+2)]
deg = [0] * (N+2)
for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    deg[y] += 1
G[0] = list(range(1, N+1))
for i in range(1, N+1): 
    G[i].append(N+1)
deg[N+1] = N


from collections import deque
topo = [0] + list(v for v in range(1, N+2) if deg[v] == 0)
deq = deque(topo)

while deq:
    v = deq.popleft()
    for t in G[v]:
        deg[t] -= 1
        if deg[t] == 0:
            topo.append(t)
            deq.append(t)

dp = [-1] * (N+2)
for v in topo:
    for t in G[v]:
        dp[t] = max(dp[t], dp[v] + 1)

print(dp[-1] - 1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(N+2)]
deg = [0] * (N+2)
for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    deg[y] += 1
G[0] = list(range(1, N+1))
for i in range(1, N+1): 
    G[i].append(N+1)
deg[N+1] = N


from collections import deque
topo = list(v for v in range(N+2) if deg[v] == 0)
deq = deque(topo)

while deq:
    v = deq.popleft()
    for t in G[v]:
        deg[t] -= 1
        if deg[t] == 0:
            topo.append(t)
            deq.append(t)

dp = [-1] * (N+2)
for v in topo:
    for t in G[v]:
        dp[t] = max(dp[t], dp[v] + 1)

print(dp[-1] - 1)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
  print(3)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

# 隣接リストを作成
adjacencyList = [[0] for i in range(N)]

# 距離の情報
dp = [0] * N

# 入次数　（いりじすう）
deg = [0] * N

for _ in range(M):
    v, nv = map(int, input().split())
    adjacencyList[v-1].append(nv-1)
    #　入次数に1を足す
    deg[nv-1] += 1
    
queue = []

# BFS探索
# 入次数がゼロの頂点から探索を始める
for v in range(N):
    if deg[v] == 0:
        queue.append(v)

while queue:
    # 現在の頂点をqueueからpop
    v = queue.pop(0)
    for nv in adjacencyList[v]:
        # 探索済みの頂点の入次数を減らす
        deg[nv] -= 1
        
        # 完全に探索済みの頂点の入次数がゼロの時、経路の距離を出発点から計算
        if deg[nv] == 0:
            # 頂点をqueueに追加する
            queue.append(nv)
            dp[nv] = max(dp[v] + 1, dp[nv])
            
print(max(dp))