Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    t = S()
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    for i in range(sl):
        for j in range(tl):
            if s[i] == t[j]:
                if i > 0 and j > 0:
                    rr[i][j] = rr[i-1][j-1] + 1
                else:
                    rr[i][j] = 1
                continue

            m = 0
            if i > 0:
                m = rr[i-1][j]
            if j > 0 and m < rr[i][j-1]:
                m = rr[i][j-1]
            rr[i][j] = m

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i])
            i -= 1
            j -= 1
            continue
        if rr[i][j] == 0:
            break
        if i > 0 and rr[i-1][j] == rr[i][j]:
            i -= 1
        else:
            j -= 1

    return ''.join(r[::-1])


print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = [c for c in S()]
    t = [c for c in S()]
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    for i in range(sl):
        for j in range(tl):
            if s[i] == t[j]:
                if i > 0 and j > 0:
                    rr[i][j] = rr[i-1][j-1] + 1
                else:
                    rr[i][j] = 1
                continue

            m = 0
            if i > 0:
                m = rr[i-1][j]
            if j > 0 and m < rr[i][j-1]:
                m = rr[i][j-1]
            rr[i][j] = m

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i])
            i -= 1
            j -= 1
            continue
        if rr[i][j] == 0:
            break
        if i > 0 and rr[i-1][j] == rr[i][j]:
            i -= 1
        else:
            j -= 1

    return ''.join(r[::-1])


print(main())
### BUGGY CODE ###

n=int(input())
l=sorted(list(map(int,input().split())))
l1=set(l)
c=0
for i in l1:
  if l.count(i)>=i:
    c+=l.count(i)-i
  else:
    c+=l.count(i)
print(c)

### FIXED CODE ###

from collections import defaultdict
l=defaultdict(int)
n=int(input())
l1=list(map(int,input().split()))
for i in l1:
  l[i]+=1
b=True
lset=set(l1)
answer=0
for i in lset:
  if l[i]!=i:
    if l[i]<i:
      answer+=l[i]
    else:
      answer+=min(l[i]-i,l[i])
print(answer)
### BUGGY CODE ###

S = input()
Q = int(input())
reverse = False
for i in range(Q):
    Query = input()
    T = int(Query[0])
    if T == 1:
        reverse = not reverse 
    else:
        F = int(Query[2])
        C = Query[4]
        if (F == 1 and reverse == False) or (F == 2 and reverse == True):
            S = C + S
        else:
            S = S + C

if reverse == True:
    S = S[::-1]


print(S)
print('\n')


### FIXED CODE ###

S = input()
Q = int(input())
front = ''
end = ''
reverse = False
for i in range(Q):
    Query = input()
    if Query[0] == '1':
        reverse = not reverse 
    else:
        if (Query[2] == '1' and reverse == False) or (Query[2] == '2' and reverse == True):
            front = Query[4] + front
        else:
            end = end + Query[4]

S = front + S + end
if reverse == True:
    S = S[::-1]


print(S)
print('\n')
### BUGGY CODE ###

input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

def lcm(a, b):
  return a*b/gcd(a, b)

L = int(lcm(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    for i in range(N):
        for j in range(M):
            if((i-1)*k/N+1 == (j-1)*k/M+1):
                if(S[i-1] != T[j-1]):
                    flag = 0
                    count += 1
                    break
        if(flag == 0):
            break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1


### FIXED CODE ###

input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

def lcm(a, b):
  return a*b/gcd(a, b)

L = int(lcm(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    starti = 0
    startj = 0
    for i in range(starti, N):
        for j in range(startj, M):
            hoge = i*k/N+1
            fuga = j*k/M+1
            if(hoge < fuga):
                startj = j - 1
                break
            elif(hoge == fuga):
                if(S[i] != T[j]):
                    flag = 0
                    count += 1
                    break
        if(flag == 0):
            break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import collections
import sys
 
input=sys.stdin.readline
 
N=int(input())
l=[]
clist=[]
 
for i in range(N):
    l.append(list(input().replace("\n","")))
    l[i]=collections.Counter(l[-1])
    #clist.append(collections.Counter(list(input().replace("\n",""))))#ここは普通に入れてfor文でcounterする
 
count=0
 
for i in range(N):
    for j in range(i+1,N):
        if l[i]==l[j]:
            count+=1
            
print(count)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import collections 
 
N=int(input())
l=[]
 
for i in range(N):
    l.append(list(input()))
    l[i].sort()
    l[i]="".join(l[i])
    
clist=list(collections.Counter(l).values())

count=0
for c in clist:
    count+=int(c*(c-1)//2)
    
print(count)
### BUGGY CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
ans = ''
i = S
j = T
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
print(ans)

### FIXED CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
ans = ''
i = S
j = T
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,T,*ab = map(int, read().split())

    AB = []
    for a, b in zip(*[iter(ab)]*2):
        AB.append((a, b))

    AB.sort()
    
    dp = [[0] * (T+1) for _ in range(N+1)]

    ans = 0
    for i in range(N):
        w_i, v_i = AB[i]
        for j in range(T):
            if j < w_i:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j - w_i] + v_i, dp[i][j])
        
        ans = max(ans, dp[i][T-1] + v_i)
    
    print(ans)
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,T,*ab = map(int, read().split())

    AB = []
    for a, b in zip(*[iter(ab)]*2):
        AB.append((a, b))

    AB.sort()
    
    dp = [[0] * (T+1) for _ in range(N+1)]

    ans = 0
    for i in range(N):
        w_i, v_i = AB[i]
        for j in range(T):
            if j < w_i:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j - w_i] + v_i, dp[i][j])
        
        ans = max(ans, dp[i][T-1] + v_i)
    
    print(ans)
    

if __name__ == "__main__":
    main()
### BUGGY CODE ###

from itertools import permutations, combinations


def solve(string):
    n, a, b, c, *l = map(int, string.split())
    ans = 3000
    for _l in permutations(l):
        for i, j, k in combinations(range(1, len(l) + 1), 3):
            tmp = 10 * (i - 1) + abs(a - sum(_l[:i])) + 10 * (j - i - 1) + abs(
                b - sum(_l[i:j])) + 10 * (k - j - 1) + abs(c - sum(_l[j:k]))
            if tmp < ans:
                ans = tmp
    return str(ans)


if __name__ == '__main__':
    n, a, b, c = map(int, input().split())
    print(solve('{} {} {} {}\n'.format(n, a, b, c) + '\n'.join([input() for _ in range(n)])))


### FIXED CODE ###

from itertools import permutations


def solve(string):
    n, a, b, c, *l = map(int, string.split())
    ans = 3000

    for _l in permutations(l):
        for i in range(1, len(l) - 1):
            for j in range(i + 1, len(l)):
                for k in range(j + 1, len(l) + 1):
                    tmp = 10 * (i - 1) + abs(a - sum(_l[:i])) + 10 * (j - i - 1) + abs(
                        b - sum(_l[i:j])) + 10 * (k - j - 1) + abs(c - sum(_l[j:k]))
                    if tmp < ans:
                        ans = tmp
    return str(ans)


if __name__ == '__main__':
    n, a, b, c = map(int, input().split())
    print(solve('{} {} {} {}\n'.format(n, a, b, c) + '\n'.join([input() for _ in range(n)])))
### BUGGY CODE ###

import sys
import heapq
import operator as op

def dijkstra(graph, start):
    dist = [float("inf") for _ in range(len(graph))]
    dist[start] = 0
    prev = [None for _ in range(len(graph))]
    q = list(zip(dist, range(len(graph))))
    heapq.heapify(q)

    while q != []:
        du, u = heapq.heappop(q)
        for v, d in filter(lambda x: x[1] < float("inf"), zip(range(len(graph)), graph[u])):
            if dist[v] > du + d:
                dist[v] = du + d
                prev[v] = u
                heapq.heappush(q, (dist[v], v))

    return dist, prev

n, m, s, t = map(int, next(sys.stdin).split(" "))

u = [0 for _ in range(m)]
v = [0 for _ in range(m)]
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
matrix = [[None for _ in range(n)] for _ in range(n)]

yen_graph = [[float("inf") for _ in range(n)] for _ in range(n)]
snuke_graph = [[float("inf") for _ in range(n)] for _ in range(n)]

for i in range(m):
    u, v, a, b = map(int, next(sys.stdin).split(" "))
    yen_graph[u-1][v-1] = yen_graph[v-1][u-1] = a
    snuke_graph[u-1][v-1] = snuke_graph[v-1][u-1] = b

yen_costs, _ = dijkstra(yen_graph, s-1)
snuke_costs, _ = dijkstra(snuke_graph, t-1)
remain = list(map(op.add, yen_costs, snuke_costs))

for i in range(n):
    print(10**15 - min(remain[i:]))


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from itertools import accumulate
 
def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float("inf")):
    inf = float("inf")
    vertices = [inf] * n
    vertices[start] = 0
    q, rem = [(0, start)], n - 1
 
    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1
 
        dests = ((i, n) for i, n in enumerate(edges[v]) if n != default_value)\
            if adj_matrix else edges[v]
 
        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))
 
    return vertices
 
n, m, s, t = map(int, input().split())
s, t = s-1, t-1
yen = [[] for _ in [0]*n]
sno = [[] for _ in [0]*n]
for l in sys.stdin.readlines():
    u, v, a, b = map(int, l.strip().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    sno[u-1].append((v-1, b))
    sno[v-1].append((u-1, b))
 
yen = dijkstra(n, yen, s)
sno = dijkstra(n, sno, t)
result = list(accumulate([y+s for y, s in zip(yen, sno)][::-1], min))
money = 10**15
for n in result[::-1]:
    print(money-n)
### BUGGY CODE ###

from collections import defaultdict
def main():
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % sum(list(map(int, bin(n)[2:])))) + 1
    def rev(i):
        if X[i] == '0':
            b = m + j
            print(d[b % (c + 1)] + 1 if b != 0 else 0)
        else:
            b = m - j
            print(d[b % (c - 1)] + 1 if b != 0 else 0)

    n = int(input())
    X = list(input())
    d = defaultdict(int)
    d[0] = 0
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    j = 1 << n - 1
    for i in range(n):
        rev(i)
        j = j >> 1

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    jp, jm = 1, 1
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        if X[i] == '0':
            mod = c + 1
            ans[i] = f((mp + jp) % mod) + 1
        else:
            ans[i] = f((mm - jm + mod) % mod) + 1 if (mod := c - 1) != 0 else 0
        jp, jm = (jp << 1) % (c + 1), (jm << 1) % (c - 1) if c - 1 != 0 else 0
    [print(a) for a in ans]
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# D
h, w, d = map(int, input().split())
points = [[0]*2 for i in range(h*w + 1)]
for h_i in range(h):
    a_row = [int(i) for i in input().split()]
    for r_i, a in enumerate(a_row):
        points[a][0] = h_i
        points[a][1] = r_i

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    ans = 0
    while l != r:
        next_l = l + d
        ans += abs(points[l][0] - points[next_l][0]) + abs(points[l][1] - points[next_l][1])
        l = next_l
    print(ans)

### FIXED CODE ###

# D
h, w, d = map(int, input().split())
points = [[0]*2 for i in range(h*w)]
cost = [0]* (h*w)
for h_i in range(h):
    a_row = [int(i) for i in input().split()]
    for r_i, a in enumerate(a_row):
        points[a-1][0] = h_i
        points[a-1][1] = r_i
for i in range(d, (h*w)):
    cost[i] = cost[i-d] + abs(points[i][0]-points[i-d][0]) + abs(points[i][1]-points[i-d][1])
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cost[r-1] - cost[l-1])
### BUGGY CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
dp=[[10**9+1]*(h+1) for i in range(n+1)]
for i in dp:
  i[0]=0

for i in range(n):
  for j in range(h+1):
    if j-ab[i][0]>=0:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-ab[i][0]]+ab[i][1],(j//ab[i][0]+1)*ab[i][1])
    else:
      dp[i+1][j]=min(dp[i][j],ab[i][1])
print(dp[-1][h])

### FIXED CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
dp=[[10**9+1]*(h+1) for i in range(n+1)]
for i in dp:
  i[0]=0

for i in range(n):
  for j in range(h+1):
    if j-ab[i][0]>=0:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-ab[i][0]]+ab[i][1],(j//ab[i][0]+1)*ab[i][1])
    else:
      dp[i+1][j]=min(dp[i][j],ab[i][1])
print(dp[-1][h])
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for _ in range(2)]
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for i in range(l):
        for j in range(13):
            if s[i] != "?":
                num = int(s[i])
                dp[use][(j*10+num)%13] += dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
        for j in range(13):
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    ans = [0 for _ in range(13)]
    MOD = 10**9+7
    ans[0] = 1
    
    for st in s:
        dp = [0 for _ in range(13)]
        for i in range(13):
            dp[(10*i)%13] = ans[i]%MOD
        dp += dp
        if st != "?":
            for i in range(13):
                num = int(st)
                ans[i] = dp[i+13-num]
        else:
            for i in range(13):
                ans[i] = sum(dp[i+4:i+14])
    
    print(ans[5]%MOD)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np

i = list(map(int, input().split()))
N = i[0]
M = i[1]

ans = np.array(range(N + 1))

for i in range(M):
	l = list(map(int, input().split()))
	ans = ans[ans >= l[0]]
	ans = ans[ans <= l[1]]

print(ans.shape[0])

### FIXED CODE ###

import numpy as np

i = list(map(int, input().split()))
N = i[0]
M = i[1]

l = np.array([list(map(int, input().split())) for i in range(M)])

limit1 = max(l[:, 0])
limit2 = min(l[:, 1])

print(max(limit2 - limit1 + 1, 0))
### BUGGY CODE ###

x = int(input())

# x^5−y^5=(x−y)(x^4+x3^y+x^2y^2+xy^3+y^4)
# x-yをみつける x-y = d[i]
# と思ったができない
# ひょっとして総当りで間に合うのでは

for i in range(x):
    tmpx = i
    tmpy = i**5 - x
    if isinstance(tmpy, int) and tmpx**5 - tmpy**5 == x:
        print(tmpx, tmpy)
        exit()
print(0 / 0)


### FIXED CODE ###

# 暴力即可
# 範囲指定 A=100 B=-100で20000000000とかになるしどっちも|100|程度でいいのではないか
# なんか足りんみたい（なんで？）なので4X^2<=10^9なる最大のXを求めよう
# 2X = 1000ちょい だから500くらいあればいいのか
# 1000^2なので時間的には間に合いそう
x = int(input())
for a in range(-500, 501):
    for b in range(-500, 501):
        if a**5 - b**5 == x:
            print(a, b)
            exit()
print(3 / 0)  # はい
### BUGGY CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))

ma=0
for i in range(n-k+1):
       s=sum(P[i:i+k])
       if ma<s:
              ma=s
print((ma+k)/2)
       

### FIXED CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))

S=[0]*(n+1)
S[1]=P[0]
for i in range(2,n+1):
        S[i]=S[i-1]+P[i-1]
ma=0
for i in range(k,n+1):
       s=S[i]-S[i-k]
       if ma<s:
              ma=s
print((ma+k)/2)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())

alist = sorted(list(map(int, input().split())))

for _ in range(m):
  b, c = map(int, input().split())
  idx = bisect.bisect_right(alist,c)
  if idx-1 <= b:
    alist = [c for _ in range(idx)] + alist[idx:]
  else:
    alist = [c for _ in range(b)] + alist[b:idx] + alist[idx:]
  alist.sort() 
print(sum(alist))

### FIXED CODE ###

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

CB = []
for _ in range(M):
  b,c = map(int,input().split())
  CB.append([c,b])
CB.sort(reverse=True)

num = 0
ans = 0 
for c,b in CB:
  for bi in range(b):
    if num >= N: break
    if num > N or c<=A[num]:
      break
    else:
      num += 1
      ans += c
print(ans+sum(A[num:]) if num != N else ans)
### BUGGY CODE ###

S = input()
for q in range(int(input())):
    T = input().rstrip().split()
    if T[0] == "1":
        S = S[::-1]
    else:
        F,C = T[1],T[2]
        if F == "1":
            S = C + S
        else:
            S += C
print(S)

### FIXED CODE ###

B = input()
order = True
F = ""
for q in range(int(input())):
    T = input().rstrip().split()
    if T[0] == "1":
        order ^= True
    else:
        f,c = T[1],T[2]
        if not((f == "1") ^ order):
            F += c
        else:
            B += c
    #print(F,B)
F = F[::-1]+B
if not order:
    F = F[::-1]
print(F)
### BUGGY CODE ###

import fractions
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a1=a[0]
  for i in a:
    a1=(i*a1)//fractions.gcd(i,a1)
  x=[a1//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

import fractions
from functools import reduce
def main():
  _=input()
  a=tuple(map(int,input().split()))
  fgcd=fractions.gcd
  def lcm_base(x, y):
    return (x * y) // fgcd(x, y)
  def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
  q=lcm(a)
  x=[q//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
graph = defaultdict(list)
for a, b in L:
    graph[a-1].append(b-1)
ans = 0
dist = [0] * N

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


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
gout = [[] for i in range(N)]
deg = [0] * N

for i in range(M):
    x, y = MAP()
    gout[x-1].append(y-1)
    deg[y-1] += 1
# only no_children 
topo = [v for v in range(N) if deg[v] == 0]
path_len = [0] * N
ans = 0
q = deque(topo)
# 子を持たない子スタート
while q:
    v = q.popleft()
    for t in gout[v]:
        # 親の子，vのカウントを減らす
        deg[t] -= 1
        # それでそれ以外の子がいなくなったら，
        # トポロジカルソートではスタックに積む
        if deg[t] == 0:
            q.append(t)
            path_len[t] = path_len[v] + 1
            ans = path_len[t]
print(ans)
### BUGGY CODE ###

inf = float('inf')

N,W = map(int,input().split())
w, v = [], []
for _ in range(N):
    wi, vi = map(int,input().split())
    w.append(wi)
    v.append(vi)

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        if j - w[i-1] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
        else:
            dp[i][j] = dp[i-1][j]

ans = dp[N][W]
print(ans)

### FIXED CODE ###

N,W = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
# dp[i+1][w] i+1番目まで品物を選んで重さwのときの価値の最大値
# dp[0] = [0]*(W+1)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if  w - info[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w-info[i][0]] + info[i][1],dp[i][w])
        else:    
            dp[i+1][w] = dp[i][w]
print(dp[N][W])