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:
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(int(max(dp)))

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:
import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

dp=[-1]*n  
  
def dfs(i):
  temp=0
  if dp[i]!=-1:
    return dp[i]
  for nv in g[i]:
    if dp[nv]!=-1:
      temp=max(temp,dfs(nv)+1)
  dp[i]=temp  
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
#dp[i]: end to i maxpath
dp = np.zeros((N+1),dtype=int)
for i in range(M):
    x,y = map(int, input().split())
    dp[y] =max(dp[y], dp[x]+1)
print(np.max(dp))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n,m=reads()
link=[[]for i in range(n)]
for i in range(m):
  x,y=reads()
  link[x-1].append(y-1)
print(link)
@lru_cache(None)
def dp(k):
  res=0
  for ele in link[k]:
    res=max(res,dp(ele)+1)
  return res
res=1
for i in range(n)  :
  res=max(res,dp(i))
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    out_degree = [0]*N
    max_path = 0
    G = defaultdict(list)
    for _ in range(M):
        x, y = read_ints()
        x -= 1
        y -= 1
        out_degree[x] += 1
        G[y].append(x)
    Q = [(i, 0) for i, degree in enumerate(out_degree) if degree == 0]
    while len(Q):
        node, path = Q.pop()
        max_path = max(max_path, path)
        while len(G[node]):
            parent = G[node].pop()
            out_degree[parent] -= 1
            if out_degree[parent] == 0:
                Q.append((parent, path+1))
    return max_path


if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    out_degree = [0]*N
    max_path = 0
    G = defaultdict(list)
    for _ in range(M):
        x, y = read_ints()
        x -= 1
        y -= 1
        out_degree[x] += 1
        G[y].append(x)
    Q = [(i, 0) for i, degree in enumerate(out_degree) if degree == 0]
    while len(Q):
        node, path = Q.pop()
        max_path = max(max_path, path)
        for parent in G[node]:
            out_degree[parent] -= 1
            if out_degree[parent] == 0:
                Q.append((parent, path+1))
    return max_path


if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

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

        passed = [graph[y]]
        while passed:
            nums = passed.pop(0)
            for n in nums:
                ans[n] = ans[n] + 1
                passed.append(graph[n])


print(max(ans))

Submission status: Wrong Answer

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

print(max(ans))

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] += 1
    d = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while d:
        i = d.popleft()
        for j in li[i]:
            deg[j] -= 1
            if deg[j] == 0:
                dp[j] = max(dp[j] ,dp[i] + 1)
                d.appendleft(j)
    print(max(dp))
a()

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] = 1
    d = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while d:
        i = d.popleft()
        for j in li[i]:
            deg[j] -= 1
            if deg[j] == 0:
                dp[j] = max(dp[j] ,dp[i] + 1)
                d.appendleft(j)
    print(max(dp))
a()

Submission status: Wrong Answer

Solution code:
import sys
import collections

rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] = 1
    deg = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while deg:
        i = deg.popleft()
        for j in li[i]:
            dpj = dp[j]
            dpi = dp[i]
            if dpj < dpi + 1:
                dpj = dpi + 1
            deg.appendleft(j)
    print(max(dp))
a()

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

N, M = map(int, rl().split())
li = [[] for _ in range(N)]
deg = [0] * N
for _ in range(M):
    a, b = map(int, rl().split())
    a -= 1
    b -= 1
    li[a].append(b)
    deg[b] = 1
deg = [i for i in range(N) if deg[i] == 0]
print(deg)
dp = [0] * N
for i in deg:
    for j in li[i]:
        if dp[j] < dp[i] + 1:
            dp[j] = dp[i] + 1
        deg.append(j)
print(dp)

Submission status: Wrong Answer

Solution code:
def main():
    N,M = map(int, input().split())
    # 町iまでの最長経路長dp[i]をメモ化再帰で
    INF = float('inf')
    dp = [0] * N
    for i in range(M):
        x,y = map(lambda x:x-1, map(int, input().split()))
        dp[y] = max(dp[y], dp[x]+1)
    print(max(dp))

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int,input().split())# 頂点数
X = [[] for i in range(N)] #辺リスト
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    #X[y-1].append(x-1) # 有向の場合は削除
    
def bfs(graph,dp,start): #def bfs(graph,start,limit):
    if start in dp:
        return dp[start]
    dist = [-1] * (N)
    dist[start]= 0
    q = deque([start])
    cnt = 0
    while q:
        x = q.popleft()
        if x in dp:
            dp[start] = cnt + dp[x]
            return cnt + dp[x]
        for i in graph[x]:
            #if dist[x] >= limit:
            #    break
            if dist[i] == -1:
                dist[i] = dist[x] + 1
                q.append(i)
                cnt += 1
    dp[start] = cnt
    return cnt

dp = {}
ans = 0
for i in range(N):
    ans = max(ans,bfs(X,dp,i))
#print(dp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
dit = [0]*N
st = [[] for _ in range(N)]
re = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    st[x].append(y)
    re[y].append(x)
def dfs(u):
    if len(re[u]) == 0:
        return
    li = re[u]
    for j in li:
        if dit[j] < dit[u]+1:
            dit[j] = dit[u]+1
            dfs(j)
        else:
            return
for i in range(N):
    if len(st[i]) != 0:
        continue
    else:
        dfs(i)
print(max(dit))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
dit = [0]*N
st = [[] for _ in range(N)]
re = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    st[x].append(y)
    re[y].append(x)
def dfs(u):
    if len(re[u]) == 0:
        return
    li = re[u]
    for j in li:
        if dit[j] < dit[u]+1:
            dit[j] = dit[u]+1
            dfs(j)
        else:
            return
for i in range(N):
    if len(st[i]) != 0:
        continue
    else:
        dfs(i)
print(max(dit))

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    input_edges = [0]*N
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        input_edges[v] += 1
    queue = deque()
    for i, input_edge in enumerate(input_edges):
        if input_edge == 0:
            queue.appendleft(i)
    topological_sorted = []
    while queue:
        v = queue.pop()
        topological_sorted.append(v)
        for other_side in e[v]:
            input_edges[other_side] -= 1
            if input_edges[other_side] == 0:
                queue.appendleft(other_side)
    dp = [10 ** 9] * N
    dp[topological_sorted[0]] = 0
    for v in topological_sorted:
        for other_side in e[v]:
            dp[other_side] = min(dp[v] + 1, dp[other_side])
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

n, m = map(int, input().split())
xy = []
node = defaultdict(int)
branch = defaultdict(list)
dp = [0]*(n+1) 

for _ in range(m):
    x, y = map(int, input().split())
    xy.append([x, y])
    node[y] += 1 #入り込むノードの数
    branch[x].append(y) # 枝分かれ先


res = []
queue = deque([i for i in range(1, n+1) if node[i]==0])
while queue:
    v = queue.popleft()
    res.append(v)
    
    for u in branch[v]:
        node[u] -= 1
        if node[u] == 0:
            queue.append(u)

for i in range(m):
    dp[xy[i][1]] = max(dp[xy[i][1]], dp[xy[i][0]]+1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

n, m = map(int, input().split())
xy = []
node = defaultdict(int)
branch = defaultdict(list)
dp = [0]*(n+1) 

for _ in range(m):
    x, y = map(int, input().split())
    xy.append([x, y])
    node[y] += 1 #入り込むノードの数
    branch[x].append(y) # 枝分かれ先


res = []
queue = deque([i for i in range(1, n+1) if node[i]==0])
while queue:
    v = queue.popleft()
    res.append(v)
    
    for u in branch[v]:
        node[u] -= 1
        if node[u] == 0:
            queue.append(u)

for i in range(m):
    dp[xy[i][1]] = max(dp[xy[i][1]], dp[xy[i][0]]+1)
print(dp[res[-1]])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
adj=defaultdict(list)
deg=[0]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    adj[x].append(y)
    deg[y]+=1

dist=[0]*(n+1)

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

while que:
    v=que.pop()
    for i in adj[v]:
        deg[i]-=1
        if deg[i]==0:
            que.append(i)
            dist[i]=max(dist[i],dist[v]+1)

print(max(dist))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
adj=defaultdict(list)
deg=[0]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    adj[x].append(y)
    deg[y]+=1

dist=[0]*(n+1)

que=[]
for i in range(n+1):
    if deg[i]==0:
        que.append(i)

while que:
    v=que.pop()
    for i in adj[v]:
        deg[i]-=1
        if deg[i]==0:
            que.append(i)
            dist[i]=max(dist[i],dist[v]+1)

print(max(dist))

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w=1):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

n,m=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(m)]

edgenum=[0]*(n+1)
edge=[[] for i in range(n+1)]

for i in range(m):
    x,y=xy[i]
    edgenum[x]+=1
    edge[y].append(x)
# print(edgenum)
# print(edge)

d=deque()
itta=[0]*(n+1)
for i in range(n):
    i+=1
    if edgenum[i]==0:
        d.append(i)
# print(d)

while d:
    now=d.popleft()
    if edgenum[now]==0:
        for i in edge[now]:
            edgenum[i]-=1
            d.append(i)
            itta[i]=max(itta[i],itta[now]+1)
# print(itta)
print(max(itta))

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w=1):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

n,m=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(m)]

edgenum=[0]*(n+1)
edge=[[] for i in range(n+1)]

for i in range(m):
    x,y=xy[i]
    edgenum[x]+=1
    edge[y].append(x)
# print(edgenum)
# print(edge)

d=deque()
itta=[0]*(n+1)
for i in range(n):
    i+=1
    if edgenum[i]==0:
        d.append(i)
# print(d)

while d:
    now=d.popleft()
    if edgenum[now]==0:
        for i in edge[now]:
            edgenum[i]-=1
            d.append(i)
            itta[i]=itta[now]+1
# print(itta)
print(max(itta))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[0]*n #頂点iにつくまでの本数
    for _ in range(2):
        for i in range(n):
            for g in graph[i]:
                dp[g]=max(dp[g],dp[i]+1)
    print(max(dp))


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G
# CreatedDate:  2020-05-18 17:21:29 +0900
# LastModified: 2020-05-19 01:02:19 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd
def chmax(s,t):
    if s<t:
        return t
    else:
        return s


def longest_path(ans_list,node_list,lon_path):
    while ans_list:
        u = ans_list.pop()
        for v,_from in enumerate(node_list):
            if u in _from and lon_path[v]<lon_path[u]+1:
                lon_path[v]=lon_path[u]+1
    print(max(lon_path))

def main():
    n,m = map(int,input().split())
    node_list = [[] for _ in range(n+1)]
    to_count = [0]*(n+1)
    for _ in range(m):
        s,t = map(int,input().split())
        node_list[s].append(t)
        to_count[t]+=1
    q = [ i for i,x in enumerate(to_count) if x==0]
    q.pop(0)
    distance = [0]*(n+1)
    ans_list = []
    while q:
        u = q.pop()
        for v in node_list[u]:
            to_count[v]-=1
            if to_count[v]==0:
                q.append(v)
                distance[v]=chmax(distance[v],distance[u]+1)
        ans_list.append(u)
    print(max(distance))
#    longest_path(ans_list,node_list,lon_path)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G
# CreatedDate:  2020-05-18 17:21:29 +0900
# LastModified: 2020-05-19 00:55:24 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd
def longest_path(ans_list,node_list,lon_path):
    while ans_list:
        u = ans_list.pop()
        for v,_from in enumerate(node_list):
            if u in _from and lon_path[v]<lon_path[u]+1:
                lon_path[v]=lon_path[u]+1
    print(max(lon_path))

def main():
    n,m = map(int,input().split())
    node_list = [[] for _ in range(n+1)]
    to_count = [0]*(n+1)
    for _ in range(m):
        s,t = map(int,input().split())
        node_list[s].append(t)
        to_count[t]+=1
    q = [ i for i,x in enumerate(to_count) if x==0]
    q.pop(0)
    distance = [0]*(n+1)
    ans_list = []
    while q:
        u = q.pop()
        for v in node_list[u]:
            to_count[v]-=1
            if to_count[v]==0 and distance[v]<distance[u]+1:
                q.append(v)
                distance[v]=distance[u]+1
        ans_list.append(u)
    print(max(distance))
#    longest_path(ans_list,node_list,lon_path)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G
# CreatedDate:  2020-05-18 17:21:29 +0900
# LastModified: 2020-05-19 00:50:51 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd
def longest_path(ans_list,node_list,lon_path):
    while ans_list:
        u = ans_list.pop()
        for v,_from in enumerate(node_list):
            if u in _from and lon_path[v]<lon_path[u]+1:
                lon_path[v]=lon_path[u]+1
    print(max(lon_path))

def main():
    n,m = map(int,input().split())
    node_list = [[] for _ in range(n+1)]
    to_count = [0]*(n+1)
    for _ in range(m):
        s,t = map(int,input().split())
        node_list[s].append(t)
        to_count[t]+=1
    q = [ i for i,x in enumerate(to_count) if x==0]
    q.pop(0)
    distance = [0]*(n+1)
    ans_list = []
    while q:
        u = q.pop()
        for v in node_list[u]:
            to_count[v]-=1
            if to_count[v]==0:
                q.append(v)
                distance[v]=distance[u]+1
        ans_list.append(u)
    print(max(distance))
#    longest_path(ans_list,node_list,lon_path)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G
# CreatedDate:  2020-05-18 17:21:29 +0900
# LastModified: 2020-05-19 00:47:26 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd
def longest_path(ans_list,node_list,lon_path):
    while ans_list:
        u = ans_list.pop()
        for v,_from in enumerate(node_list):
            if u in _from:
                lon_path[v]=lon_path[u]+1
    print(max(lon_path))

def main():
    n,m = map(int,input().split())
    node_list = [[] for _ in range(n+1)]
    to_count = [0]*(n+1)
    for _ in range(m):
        s,t = map(int,input().split())
        node_list[s].append(t)
        to_count[t]+=1
    q = [ i for i,x in enumerate(to_count) if x==0]
    q.pop(0)
    distance = [0]*(n+1)
    ans_list = []
    while q:
        u = q.pop()
        for v in node_list[u]:
            to_count[v]-=1
            if to_count[v]==0:
                q.append(v)
                distance[v]=distance[u]+1
        ans_list.append(u)
    print(max(distance))
#    longest_path(ans_list,node_list,lon_path)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G
# CreatedDate:  2020-05-18 17:21:29 +0900
# LastModified: 2020-05-19 00:41:40 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd
def longest_path(ans_list,node_list,lon_path):
    while ans_list:
        u = ans_list.pop()
        for v,_from in enumerate(node_list):
            if u in _from:
                lon_path[v]=lon_path[u]+1
    print(max(lon_path))

def main():
    n,m = map(int,input().split())
    node_list = [[] for _ in range(n+1)]
    to_count = [0]*(n+1)
    for _ in range(m):
        s,t = map(int,input().split())
        node_list[s].append(t)
        to_count[t]+=1
#    print(node_list)
#    print(to_count)
    q = [ i for i,x in enumerate(to_count) if x==0]
    q.pop(0)
#    print(q)
    ans_list = []
    while q:
        u = q.pop()
        for v in node_list[u]:
            to_count[v]-=1
            if to_count[v]==0:
                q.append(v)
        ans_list.append(u)
#    print(ans_list)
    lon_path = [0]*(n+1)
    longest_path(ans_list,node_list,lon_path)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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


d = [0] * n

def dfs(v,edge):
    global depth
    depth = 0
    for next_v in edge[v]:
        if d[next_v] == 0:
            dfs(next_v,edge)
        depth = max(depth,d[next_v])
    depth += 1 
    d[v] = depth

for i in range(n):
    dfs(i,edge)
print(max(d)-1)

Submission status: Wrong Answer

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

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


d = [0] * n

def dfs(v,edge):
    global depth
    depth = 0
    for next_v in edge[v]:
        if d[next_v] == 0:
            dfs(next_v,edge)
        else:
            depth = max(depth,d[next_v])
    depth += 1 
    d[v] = depth

for i in range(n):
    dfs(i,edge)
print(max(d)-1)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, m = IN()
	#s = input()
	nokori = [0]*n
	max_path_from = [0]*n
	path = []
	tl = [[] for _ in range(n)]
	for _ in range(m):
		f, t = IN()
		f,t=f-1, t-1
		path.append((f,t))
		nokori[t] += 1
		tl[f].append(t)
	sl=[i for i, v in enumerate(nokori) if v == 0]
	pa(tl)
	pa(sl)
	pa(nokori)
	pa('____')
	mp=0
	while len(sl) > 0:
		for v in sl:
			next_l = []
			for t in tl[v]:
				pa(t)
				nokori[t]-= 1
				if nokori[t]==0:
					next_l.append(t)
		sl = next_l
		mp+=1
		pa(sl)
		pa(nokori)
		pa('___')
	print(mp-1)
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  graph[x-1].append(y-1)
dp = [0]*(n)
 
done = []
def dfs(i):
    if dp[i] != 0:
        return dp[i]
    elif i in done:
        done.pop()
        if dp[i] < len(done):dp[i] = len(done)
        return len(done)
    else:
        for j in graph[i]:
            if not(j in done):
                done.append(i)
                dfs(j)
        if dp[i] < len(done):dp[i] = len(done)
        if done:done.pop()
        return len(done)
 
for i in range(n):  
    dfs(i)
print(max(dp))

Submission status: Wrong Answer

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

DP.sort()
print(DP[N-1][0])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
dp = [0] * (n+1)
fr = {i:[] for i in range(1, n+1)}
rv = {i:[] for i in range(1, n+1)}
for i in range(m):
    x, y = map(int, input().split())
    fr[x].append(y)
    rv[y].append(x)
dc = {key for key, value in rv.items() if not value}
ndc = {key for key, value in rv.items() if value}
cnt = 0
while ndc and cnt <= 100:
    cnt += 1
    tmp_set = set()
    for i in ndc:
        rv_set = set(rv[i])
        if rv_set <= dc:
            dp[i] = max([j for index, j in enumerate(dp) if index in rv_set] + [0]) + 1
            tmp_set.add(i)
    dc |= tmp_set
    ndc -= tmp_set
print(max(dp))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
length=defaultdict(int)

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
print(q)
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))