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



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

dp =[0] * (N + 1)
qs = [ list(map(int,input().split(" "))) for _ in range(M)]
for q in qs:
    x,y = q
    #dp[y] → yを終点としたlongest path
    dp[y] = max(dp[y],dp[x] + 1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
import math
import sys



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

dp =[0] * (N + 1)
for _ in range(M):
    x,y = list(map(int,input().split(" ")))
    #dp[y] → yを終点としたlongest path
    dp[y] = max(dp[y],dp[x] + 1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]

vs = set()
dvs = [0 for _ in range(N+1)]
def dfs_w(v, d):
    # dfs while版 
    stack = [v]
    path = []
    cd=ld= 0
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v in vs:
            p = stack.pop()
            dvs[-p] = max(dvs[-p], dvs[v]+1)
            continue
        if v < 0:
            c = path.pop()
            dvs[-v] = max(dvs[-v], dvs[c]+1)
            cd -= 1
        else:
            vs.add(v)
            path.append(v)
            ld = max(ld, cd)
            cd += 1
            for u in d[v]:
                stack += [-v, u]
        print(v, dvs)
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    d[a].add(b)

for i in range(N):
    i += 1
    if i in vs:
        continue
    dfs_w(i, d)
print(max(dvs))

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]

vs = set()
dvs = [0 for _ in range(N+1)]
def dfs_w(v, d):
    # dfs while版 
    vs.add(v)
    stack = [v]
    path = []
    cd=ld= 0
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            c = path.pop()
            dvs[-v] = max(dvs[-v], dvs[c]+1)
            cd -= 1
        else:
            path.append(v)
            ld = max(ld, cd)
            cd += 1
            for u in d[v]:
                if u in vs:
                    dvs[v] = max(dvs[v], dvs[u]+1)
                    continue
                vs.add(u)
                stack += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    d[a].add(b)

for i in range(N):
    i += 1
    if i in vs:
        continue
    dfs_w(i, d)
print(max(dvs))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [0] * (N + 1)
e = dd(list)
inc = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  inc[v] += 1
def topologically(n, e, inc):
  res = []
  s = []
  c = 0
  many = 0
  for i in range(1, n + 1):
    if inc[i] == 0:
      s.append(i)
      c += 1
  many = c > 1
  while len(s):
    p = s.pop()
    res.append(p)
    for q in e[p]:
      inc[q] -= 1
      if inc[q] == 0:
        s.append(q)
    many = many or ((len(s) - c) > 0)
    c = len(s)
  return res + [many]
res = topologically(N, e, inc)
for i in range(N):
  for q in e[i]:
    dp[q] = max(dp[q], dp[i] + 1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  dp[v] = max(dp[v], dp[u] + 1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
L=[[]for i in range(N+1)]
S=[0 for i in range(N+1)]
for i in range(M):
    x,y=map(int,input().split())
    L[x].append(y)
    S[y]+=1
#print(L)
#print(S)
start=[]
for i in range(1,N+1):
    if S[i]==0:
        start.append(i)
D=[0 for i in range(N+1)]
for s in start:
    Q=[]
    for i in range(len(L[s])):
        Q.append([L[s][i],D[s]+1])
    #print(Q)
    for i in range(10**6):
        if i==len(Q):
            break
        if D[Q[i][0]]<Q[i][1]:
            D[Q[i][0]]=Q[i][1]
            for j in range(len(L[Q[i][0]])):
                if D[L[Q[i][0]][j]]<Q[i][1]+1:
                    Q.append([L[Q[i][0]][j],Q[i][1]+1])
print(max(D))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

que = deque(i for i in range(N) if deg[i] == 0)
while que:
    v = que.pop()
    for u in E[v]:
        deg[u] -= 1
        if deg[u] == 0:
            que.append(u)
            dp[u] = max(dp[u], dp[v] + 1)

print(max(dp))

Submission status: Wrong Answer

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

path = [[] for _ in range(N)]
pin = [0]*N
for _ in range(M):
  ip,op = map(int,input().split())
  pin[op-1]+=1
  path[ip-1].append(op-1)

cur = []
for i in range(N):
  if pin[i]==0:
    cur.append(i)

ans = 0
while cur:
  ans += 1
  nxt = []
  for ip in cur:
    for op in path[ip]:
      pin[op] -= 1
      if pin[ip]==0 and not(op in nxt):
        nxt.append(op)
  cur = [x for x in nxt]
print(ans-1)

Submission status: Wrong Answer

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

path = [[] for _ in range(N)]
pin = [0]*N
for _ in range(M):
  ip,op = map(int,input().split())
  pin[op-1]+=1
  path[ip-1].append(op-1)

cur = []
for i in range(N):
  if pin[i]==0:
    cur.append(i)

ans = 0
while cur:
  ans += 1
  nxt = []
  for ip in cur:
    for op in path[ip]:
      pin[ip] -= 1
      if pin[ip]==0 and not(op in nxt):
        nxt.append(op)
  cur = [x for x in nxt]
print(ans-1)

Submission status: Wrong Answer

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

path = [[] for _ in range(N)]
pin = [0]*N
for _ in range(M):
  ip,op = map(int,input().split())
  pin[op-1]+=1
  path[ip-1].append(op-1)

cur = []
for i in range(N):
  if pin[i]==0:
    cur.append(i)

ans = 0
while cur:
  ans += 1
  nxt = []
  for ip in cur:
    for op in path[ip]:
      pin[ip] -= 1
      if pin[ip]==0 and not(op in nxt):
        nxt.append(op)
  cur = [x for x in nxt]
print(ans)

Submission status: Wrong Answer

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

DP = [0]*(100010)

#0
EnterList = [0]*N
SortList = []

#1

for i in range(M):
    EnterList[y[i]-1] += 1


while(1):
    #2
    CurrentNode = []

    for i in range(N):
        if EnterList[i] == 0:
            CurrentNode.append(i)

    #3
    for i in range(len(CurrentNode)):
        SortList.append(CurrentNode[i])

    #4
    for i in range(N):
        if i in CurrentNode:
            EnterList[i] -= 1

    #5
    for i in range(M):
        if x[i]-1 in CurrentNode:
            EnterList[y[i]-1] -= 1

    print(EnterList)


    if max(EnterList) < 0:
        break


def chmax(a, b):
    if a < b:
        a = b
    return a

for i in range(M):
    DP[y[i]] = chmax(DP[y[i]], DP[x[i]] + 1)

print(max(DP))

Submission status: Wrong Answer

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

DP = [0]*(100010)

def chmax(a,b):
    if a < b:
        a = b
    return a

for i in range(M):
    DP[y[i]] = chmax(DP[y[i]],DP[x[i]]+1)

print(max(DP))

Submission status: Wrong Answer

Solution code:
def tpsort(n,lst):
    parent=[0]*(n+1)
    child=[[] for _ in range(n+1)]
    for p,c in lst:
        child[p].append(c)
        parent[c]+=1
    ans=[]
    que=[]
    for i in range(1,n+1):
        if parent[i]==0:
            que.append(i)
    while que:
        h=que.pop()
        ans.append(h)
        for u in child[h]:
            parent[u]-=1
            if parent[u]==0:
                que.append(u)
    return ans
N,m=map(int,input().split())
data=[list(map(int,input().split())) for i in range(m)]
t=[[] for i in range(N+1)]
for p,c in data:
    t[p].append(c)
s=tpsort(N,data)
dp=[0]*(N+1)
for v in s:
    for r in t[v]:
        dp[r]=dp[v]+1
print(max(dp))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
data=[list(map(int,input().split())) for i in range(m)]
dp_front=[0]*(n+1)
dp_back=[0]*(n+1)
for i in range(m):
    x,y=data[i]
    dp_back[y]=max(dp_back[y],dp_back[x]+1)
    dp_front[x]=max(dp_front[x],dp_front[y]+1)
ans=0
for i in range(1,n+1):
    ans=max(ans,dp_front[i]+dp_back[i])
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
dp = [0]*n
for _ in range(m):
    x,y = LI()
    x -= 1
    y -= 1
    dp[y] = max(dp[y],dp[x] + 1)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N,M = [int(x) for x in input().split()]
E ={i: [] for i in range(1, N+1)}
for _ in range(M):
  u,v = [int(x) for x in input().split()]
  E[u].append(v)
  E[v].append(u)
#print(E)
dp =[-1]*(N+1)
visited = {i: False for i in range(1, N+1)}
counter = 0
while False in visited.values():
    stk = [(list(visited.values()).index(False) + 1, -1)]
    dp[list(visited.values()).index(False)+1] = max(0,dp[list(visited.values()).index(False)+1])
    while stk:
        #print(stk)
        v, p = stk.pop()
        #print(v,p)
        if visited[v]:
            continue
        visited[v] = True
        dp[v] = max(dp[p]+1,dp[v])
        for u in E[v]:
            if u != p:
                stk.append((u, v))
print(max(dp))

Submission status: Wrong Answer

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

dp=[[0]*N for i in range(M+1)]

for i in range(M):
    dp[i+1][li[i][1]-1] = max(dp[i][li[i][1]-1],dp[i][li[i][0]-1]+1)

ans = 0
for i in range(N):
    ans = max(ans,dp[M][i])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split( ))
Edg = [[] for _ in range(n)]
#rev_Edg =  [[] for _ in range(n)]

Visited = [0]*n
Root_check = [1]*n
Dist = [0]*n
for i in range(m):
    v1,v2 = map(int, input().split( ))
    v1-=1
    v2-=1
    Edg[v1].append(v2)
    Root_check[v2] = 0
    
Roots = []
for i in range(n):
    if Root_check[i] == 1:
        Roots.append(i)
Q = deque()
for r in Roots:
    Q.append(r)
    while len(Q) > 0:
        v = Q.popleft()
        for w in Edg[v]:
            Dist[w] = Dist[v] +1
            Q.append(w)

print(max(Dist))

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split( ))
Edg = [[] for _ in range(n)]
#rev_Edg =  [[] for _ in range(n)]
In_Leaf = []
Visited = [0]*n
Root_check = [1]*n
Dist = [0]*n
for i in range(m):
    v1,v2 = map(int, input().split( ))
    v1-=1
    v2-=1
    Edg[v1].append(v2)
    #rev_Edg[v2].append[v1]
    In_Leaf.append(v2)

In_Leaf.sort()

for v in In_Leaf:
    Root_check[v] = 0
Roots = []
for i in range(n):
    if Root_check[i] == 1:
        Roots.append(i)
Q = deque()
for r in Roots:
    Q.append(r)
    while len(Q) > 0:
        v = Q.popleft()
        for w in Edg[v]:
            Dist[w] = Dist[v] +1
            Q.append(w)

print(max(Dist))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
dp = [0] * (N+1)
max_len = 0
for _ in range(M):
  _from, _to = map(int, input().split())
  dp[_to] = max(dp[_to], dp[_from] + 1)
  max_len = max(max_len, dp[_to])
print(max_len)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
dp = [0] * (N+1)
max_len = 0
for _ in range(M):
  _from, _to = map(int, input().split())
  dp[_to] = dp[_from] + 1
  max_len = max(max_len, dp[_to])
print(max_len)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = [0] * (n+1)
e = [0] * (n+1)
for i in range(m):
    x, y = map(int, input().split())
    s[x] = max(s[x], s[y] + 1)
    e[y] = max(e[y], e[x] + 1)

print(max(sum(se) for se in zip(s, e)))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = [0] * (n+1)
e = [0] * (n+1)
for i in range(m):
    x, y = map(int, input().split())
    s[x] = max((1, s[x], s[y] + 1))
    e[y] = max((1, e[y], e[x] + 1))

print(max(max(s), max(e)))

Submission status: Wrong Answer

Solution code:
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    revgraph = collections.defaultdict(list)

    yset = set()
    xset = set()
    for _ in range(M):
        x, y = map(int, input().split())
        graph[x].append(y)
        revgraph[y].append(x)
        yset.add(y)
        xset.add(x)

    cur1, cur2 = set(), set()
    d1 = dict()
    d2 = dict()
    for y in range(1, N+1):
        if y not in yset:
            cur1.add(y)
            d1[y] = 0
        if y not in xset:
            cur2.add(y)
            d2[y] = 0

    while cur1:
        temp = set()
        for x in cur1:
            for y in graph[x]:
                if y not in d1:
                    d1[y] = d1[x] + 1
                    temp.add(y)
                else:
                    d1[y] = max(d1[y], d1[x] + 1)
        cur1 = temp

    while cur2:
        temp = set()
        for x in cur2:
            for y in revgraph[x]:
                if y not in d2:
                    d2[y] = d2[x] + 1
                    temp.add(y)
                else:
                    d2[y] = max(d2[y], d2[x] + 1)
        cur2 = temp

    max_l = 0
    for i in range(1, N+1):
        if i in d1 and i in d2:
            max_l = max(max_l, d1[i] + d2[i])
        elif i in d1:
            max_l = max(max_l, d1[i])
        elif i in d2:
            max_l = max(max_l, d2[i])
    return max_l

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

Submission status: Wrong Answer

Solution code:
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    revgraph = collections.defaultdict(list)

    yset = set()
    xset = set()
    for _ in range(M):
        x, y = map(int, input().split())
        graph[x].append(y)
        revgraph[y].append(x)
        yset.add(y)
        xset.add(x)

    cur1, cur2 = set(), set()
    d1, d2 = dict(), dict()
    for y in range(1, N+1):
        if y not in yset:
            cur1.add(y)
            d1[y] = 0
        if y not in xset:
            cur2.add(y)
            d2[y] = 0

    while cur1:
        temp = set()
        for x in cur1:
            for y in graph[x]:
                if y not in d1:
                    d1[y] = d1[x] + 1
                    temp.add(y)
                else:
                    d1[y] = max(d1[y], d1[x] + 1)
        cur1 = temp

    while cur2:
        temp = set()
        for x in cur2:
            for y in revgraph[x]:
                if y not in d2:
                    d2[y] = d2[x] + 1
                    temp.add(y)
                else:
                    d2[y] = max(d2[y], d2[x] + 1)
        cur2 = temp

    max_l = 0
    for i in range(1, N+1):
        if i in d1 and i in d2:
            max_l = max(max_l, d1[i] + d2[i])
    return max_l

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = [0] * (n+1)
e = [0] * (n+1)
for i in range(m):
    x, y = map(int, input().split())
    s[x] = max(s[x], s[y] + 1)
    e[y] = max(e[y], e[x] + 1)

print(max(max(s), max(e)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    n, m = map(int, input().split())
    e = [[]for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        e[a].append(b)

    dp = [-1 for i in range(n)]
    def f(i):
        if dp[i] != -1:
            return dp[i]
        ret = 0
        for v in e[i]:
            ret = max(ret, f(v) + 1)
        dp[i] = ret
        return dp[i]

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

als=[]
for i in range(m):
  als.append(xy[i])
  x,y=xy[i]
  for al in als:
    if al[-1]==x:
      al.append(y)
    if al[0]==y:
      al.insert(x,0)
print(max(als, key=lambda x: len(x)))

Submission status: Wrong Answer

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

G = []
for _ in xrange(M):
    G.append(map(int, raw_input().split()))

dp = [0]*(N+1)

for eg in G:
    dp[eg[1]] = max(dp[eg[0]]+1, dp[eg[1]])
for eg in G:
    dp[eg[1]] = max(dp[eg[0]]+1, dp[eg[1]])

print max(dp)

Submission status: Wrong Answer

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

G = []
for _ in xrange(M):
    G.append(map(int, raw_input().split()))

dp = [0]*(N+1)

for eg in G:
    dp[eg[1]] = max(dp[eg[0]]+1, dp[eg[1]])

print max(dp)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT
def main():
    import sys
    from collections import deque
    N,M=list(map(int,sys.stdin.readline().strip().split(' ')))
    checked=[1]*(N+1)
    checked[0]=0
    graph2=[[] for i in xrange(N+1)]
    for _ in xrange(M):
        a,b=list(map(int,sys.stdin.readline().strip().split(' ')))
        checked[a]=0
        graph2[b]+=[a]

    dp=[0]*(N+1)
    q=deque([])
    for i in xrange(N):
        if checked[i]==1:
            q+=[i]
    MAX=0    
    while q:
        node=q.popleft()
        for i in xrange(len(graph2[node])):
            adj=graph2[node][i]
            dp[adj]=max(dp[adj],dp[node]+1)
            MAX=max(MAX,dp[adj])
            if checked[adj]==0:
                q+=[adj]
    sys.stdout.write(str(MAX))
main()

Submission status: Wrong Answer

Solution code:
# @author 

import sys

class GLongestPath:
    def solve(self):
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)
        from collections import defaultdict
        n, m = [int(_) for _ in input().split()]
        self.adj = defaultdict(list)
        self.par = defaultdict(list)
        self.dp = [0] * (n + 1)
        self.done = [0] * (n + 1)
        in_deg = [0] * (n + 1)
        for i in range(m):
            u, v = [int(_) for _ in input().split()]
            self.adj[u].append(v)
            self.par[v].append(u)
            in_deg[v] += 1

        for i in sorted([i for i in range(1, n + 1)], key=lambda v:in_deg[v]):
            for x in self.par[i]:
                self.dp[i] = max(self.dp[i], self.dp[x] + 1)
        print(max(self.dp))

solver = GLongestPath()
input = sys.stdin.readline

solver.solve()

Submission status: Wrong Answer

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
N, M = [int(_) for _ in input().split()]

# 隣接関係は隣接リストで管理する
lst_edge = [[] for _ in range(N)]

for _ in range(M):
  x, y = map(int, input().split()) 
  # 0スタートに全て置き換える
  lst_edge[x-1].append(y-1)
  print(lst_edge)
        
# dp[v] := ノードvを始点とした時の有向パスの長さの最大値
# -1 未訪問で初期化。
dp = [-1] * N

# メモ化再帰
def rec(v):
  # 既に更新済み
  if dp[v] != -1:
    return dp[v]
  ans = 0
  lst_nv = lst_edge[v]
  for nv in lst_nv:
    ans = max(ans, rec(nv) + 1)
  dp[v] = ans
  return dp[v]
    
# 全ての点に対して更新する
ans = 0
for v in range(N):
  ans = max(ans, rec(v))
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
INF = float('inf')
N,M = map(int,input().split())

d_from = defaultdict(lambda:[])
d_to = defaultdict(lambda:[])

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

dp = [-INF]*N
for i in range(N):
    if d_from[i] == []:
        dp[i] = 0
        que = deque([])
        while d_to[i]:
            j = d_to[i].pop()
            dp[j] = max(dp[i]+1,dp[j])
            que.append(j)
        while que:
            j = que.popleft()
            while d_to[j]:
                k = d_to[j].pop()
                dp[k] = max(dp[j]+1,dp[k])
                que.append(k)
print(max(dp))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
INF = float('inf')
N,M = map(int,input().split())

d_from = defaultdict(lambda:[])
d_to = defaultdict(lambda:[])

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

dp = [-INF]*N
for i in range(N):
    if d_from[i] == []:
        dp[i] = 0
        que = deque([])
        while d_to[i]:
            j = d_to[i].pop()
            dp[j] = max(dp[i]+1,dp[j])
            que.append(j)
        while que:
            j = que.pop()
            while d_to[j]:
                k = d_to[j].pop()
                dp[k] = max(dp[j]+1,dp[k])
                que.append(k)
print(max(dp))

Submission status: Wrong Answer

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

xy = [[] for i in range(N+1)]
now = [i for i in range(1,N+1)]

aaa = [0]*M

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

for i in set(aaa):
    now.remove(i)

dp = [0]*(N+1)

next = []

while M > 0:
    for i in now:
        for x, y in xy[i]:
            dp[x] = max(dp[y]+1, dp[x])
            next.append(x)
            M -= 1
        
        now = set(next)
        next = []
        
print(max(dp))

Submission status: Wrong Answer

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

xy = [[] for i in range(N+1)]
now = [i for i in range(1,N+1)]

aaa = [0]*M

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

for i in set(aaa):
    now.remove(i)

dp = [0]*(N+1)

next = []

while M > 0:
    for i in now:
        for x, y in xy[i]:
            dp[x] = max(dp[y]+1, dp[x])
            next.append(x)
            M -= 1
        
        now = next
        next = []
        
print(max(dp))

Submission status: Wrong Answer

Solution code:
# 動的計画法のテーブルを用意
# dp(n) は頂点nを始点として時の最大有効パスの長さ

def get_inputs():
    N, M = map(int, input().split())
    
    # グラフgを初期化
    g = [[] for _ in range(N)]
    
    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)
    
    return N, M, g


def getlp(x):
    global dp, g
    
    if dp[x] != -1:
        pass
    elif len(g[x]) == 0:
        dp[x] = 0
    else:
        mxp = 0
        for y in g[x]:
            yp = getlp(y)
            if yp > mxp:
                mxp = yp
        dp[x] = mxp + 1
    
    return dp[x]


N, M, g = get_inputs()

# dp = [-1] * N
ans = 0
# for x in range(N):
#     ans = max(ans, getlp(x))

print(ans)

Submission status: Wrong Answer

Solution code:
def g():
    N, M = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(M)]
    memo = {}

    def g2(x):
        if x in memo:
            return memo[x]
        else:
            r = 0
            for xx, yy in xy:
                if x == xx:
                    r = max(r, g2(yy) + 1)
            memo[x] = r
        return r

    return g2(1)


if __name__ == '__main__':
    ans = g()
    print(ans)

Submission status: Wrong Answer

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

dp_head = [0] * (n + 1)
dp_tail = [0] * (n + 1)

longest = 0

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

    dp_head[x] = max(dp_head[x], dp_head[y] + 1)
    dp_tail[y] = max(dp_tail[y], dp_tail[x] + 1)

    longest = max(longest, dp_tail[x] + dp_head[y] + 1)

print(longest)

Submission status: Wrong Answer

Solution code:
def sub():
    N, M = [int(e) for e in input().split()]
    
    class ListDict(dict):
        def __missing__(self, key):
            self[key] = []
            return self[key]
    

    d_h2t = ListDict()
    d_t2h = ListDict()
    tails = []
    for _ in range(M):
        h, t = [int(e) for e in input().split()]
        d_h2t[h].append(t)
        d_t2h[t].append(h)
        tails.append(t)
    tails = set(tails)
    starts = [ i for i in range(1, N+1) if i not in tails]
    
    dp_table = [0 for i in range(N+1)]
    buf_order = []
    while len(starts) > 0:
        s = starts.pop()
        buf_order.append(s)
        tt_s = d_h2t[s]
        del d_h2t[s]
        [d_t2h[t].remove(s) for t in tt_s]
        for t in tt_s:
            if len(d_t2h[t]) == 0:
                del d_t2h[t]
                starts.append(t)
                dp_table[t] = max(dp_table[t], dp_table[s]+1)
    print(max(dp_table))    

if __name__ == "__main__":
    sub()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def MI(): return map(int, input().split())


def LI(): return list(mi())


def LI_(): return [int(x) - 1 for x in input().split()]


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [li() for _ in range(n)]


def LLIN_(n: int): return [li_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x, y = LI_()
        edge[x].append(y)

    def go_to_leaf(n):
        if dp[n] >= 0:
            return dp[n]
        ret = 0
        for y in edge[n]:
            ret = max(go_to_leaf(y) + 1, ret)
        dp[n] = ret
        return ret

    dp = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, go_to_leaf(i))
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int, input().split())
to_nodes = [[] for _ in range(N)] #終点ノード
deg = [0]*N #入力辺

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

st = deque()
push, pop = st.append, st.pop

for n in range(N):
    if deg[n] == 0:
        push(n) #入力辺が無く、最長パスの始点になりうる点を取得

dp = [0]*N
#print(deg,dp)
while st:
    n = pop()
    nodes = to_nodes[n]
    for ni in nodes:
        deg[ni] -= 1 #使ったエッジをグラフから削除する
        if deg[ni] == 0:
            push(ni)
            dp[ni] = max(dp[ni], dp[n] + 1)
        #print('n',n,'ni',ni,deg,dp)

print(max(dp))

'''''
@input
4 5
1 2
1 3
3 2
2 4
3 4
@output
[0, 2, 1, 2] [0, 0, 0, 0]
n 0 ni 1 [0, 1, 1, 2] [0, 0, 0, 0]
n 0 ni 2 [0, 1, 0, 2] [0, 0, 1, 0]
n 2 ni 1 [0, 0, 0, 2] [0, 2, 1, 0]
n 2 ni 3 [0, 0, 0, 1] [0, 2, 1, 0]
n 1 ni 3 [0, 0, 0, 0] [0, 2, 1, 3]
3
'''''

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
xv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

# iにいくまでの最長のパス
dp = [0] * (N+1)

for x, v in xv:
    dp[v] = max(dp[v], dp[x]+1)

print(max(dp))

Submission status: Wrong Answer

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

for x,y in XY:
    route[y] = max(route[x]+1,route[y])

print(max(route))

Submission status: Wrong Answer

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

for _ in range(m):
    x,y = map(int,input().split())
    route[y] = max(route[x]+1,route[y])
print(max(route))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

dp = [-1 for _ in range(N + 1)]

x_to_y = defaultdict(list)
y_to_x = defaultdict(list)
for x, y in XY:
    x_to_y[x].append(y)
    y_to_x[y].append(x)

# 終端をサーチ
ends = [x for x in range(1, N  +1) if x not in x_to_y.keys()]
starts = [y for y in range(1, N + 1) if y not in y_to_x.keys()]
print(y_to_x)

def search_next(current):
    # まだ探索していない前のノードがあればそちらを優先する
    for y in x_to_y[current]:
        if dp[y] == -1:
            continue

    for next_node in y_to_x[current]:
        dp[next_node] = max(dp[next_node], dp[current] + 1)
        search_next(next_node)


        

for end in ends:
    dp[end] = 0
    search_next(end)

print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)

d = [-1] * N


def dfs(u, d1):
    if d[i] != -1:
        return d[i]

    ma = 0
    for w in G[u]:
        ma = max(ma, dfs(w, d1 + 1)) + 1

    d[i] = ma
    return ma

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

print(ans)