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

import collections
N=int(input())
x=list(map(int,input().split()))
c=collections.Counter(x)
t=[2**i for i in range(len(str(bin(max(x)*2))[2:])+1)[::-1]]
count=0
x.sort()
for i in range(len(x))[::-1]:
    for j in range(len(t)):
        if t[j]-x[i] in c.keys():
            if t[j] < x[i]:
                break
            if t[j]-x[i] == x[i]:
                if c[x[i]] >= 2:
                    c[x[i]] -= 2
                    count +=1
            else:
                if c[t[j]-x[i]]>0 and c[x[i]]>0:
                    c[t[j]-x[i]] -= 1
                    c[x[i]] -= 1
                    count+=1
print(count)

### FIXED CODE ###

import collections
N=int(input())
x=list(map(int,input().split()))
c=collections.Counter(x)
t=[2**i for i in range(len(str(bin(max(x)*2))[2:])+1)[::-1]]
count=0
start=0
x.sort()
for i in range(len(x))[::-1]:
    for j in range(start,len(t)):
        if t[j] > 2*x[i]:
            start = j
        if t[j] < x[i]:
            break
        if t[j]-x[i] in c.keys():
            if t[j]-x[i] == x[i]:
                if c[x[i]] >= 2:
                    c[x[i]] -= 2
                    count +=1
            else:
                if c[t[j]-x[i]]>0 and c[x[i]]>0:
                    c[t[j]-x[i]] -= 1
                    c[x[i]] -= 1
                    count+=1
print(count)
### BUGGY CODE ###

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

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

for d in range(1, N + 1):
    for i in range(N - d + 1):
        j = i + d
        if (N-d) % 2 == 1:
            dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])
        else:
            dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])

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


### FIXED CODE ###

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

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

for d in range(1, N + 1):
    for i in range(N - d + 1):
        j = i + d
        if (N-d) % 2 == 1:
            dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])
        else:
            dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])

ans = dp[0][N]
print(ans)
### BUGGY CODE ###

s=input()
c=0
k=1
while(k!=0):
    k=0
    b=s.replace('10','')
    c+=len(s)-len(b)
    k=len(s)-len(b)
    s=b
    b=s.replace('01','')
    c+=len(s)-len(b)
    k+=len(s)-len(b)
    s=b
print(c)

### FIXED CODE ###

s=input()
o=s.count('1')
z=s.count('0')
print(2*min(o,z))
### BUGGY CODE ###

X,Y = map(int,input().split())
X_ = X
while X_ <= 10**18:
  X_ += X
  if X%Y != 0:
    print(X)
    exit()

print(-1)

### FIXED CODE ###

X,Y = map(int,input().split())
X_ = X
while X_ <= 10**9:
  if X == Y:
    print(-1)
    exit()
  X_ += X
  if X%Y != 0:
    print(X)
    exit()

print(-1)
### BUGGY CODE ###

def sol():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    d=[float('inf')]*n
    d[0]=0
    for i in range(1,n):
        d[i]=min(d[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
    print(d[n-1])
sol()

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        d[i+j]=min(d[i+j],d[i]+abs(h[i+j]-h[i]))
print(d[-1])
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split(' ')))
    H = list(map(int, input().split(' ')))
    dp = [0 for _ in range(N)]
    for i in range(1, N):
        dp[i] = abs(H[i] - H[i - 1]) + dp[i - 1]
        for d in range(2, K + 1):
            if i - d < 0:
                break
            dp[i] = min([
                dp[i],
                abs(H[i] - H[i - d]) + dp[i - d]
            ])
    print(dp[N - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    N, K = list(map(int, input().split(' ')))
    H = np.array(list(map(int, input().split(' '))))
    dp = np.full(N, 10 ** 10)
    dp[0] = 0
    for i in range(1, N):
        dp[i:(i + K)] = np.fmin(dp[i:(i + K)], dp[i - 1] + np.abs(H[i:(i + K)] - H[i - 1]))
    print(int(dp[N - 1]))


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

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        # 重要、最大値の上限はできる限り正確に見積もる
        up = min((i+j+1)*80+1, ma-k)
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        # h,w == 1の場合も考慮する、一応...
        elif i == 0:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
print(DP[-1][-1].index(1))

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
A=[a for a in A if a<K]
from collections import defaultdict
N=len(A)
bord=-1
can={0}
now=0
for i in range(N):
    flag=False
    for j in range(K-A[i],K):
        if j in can:
            flag=True
            break
    if flag:
        bord=i
    canc=can.copy()
    for x in canc:
        if x+A[i]<K:
            can|={x+A[i]}
print(N-bord-1)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
S=0
ans=0
for a in A:
    if S+a<K:
        S+=a
        ans+=1
    else:ans=0
print(ans)
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input()) 
    # int型のリスト
    A = list(map(int, input().rstrip().split(' ')))
    #print(A)
    ans = 0

    for i, a in enumerate(A):
        target = A[i+a:]
        #print(target)
        for j, b in enumerate(target):
            if j  == b:
                #print(a, b)
                ans += 1
    print(ans)

### FIXED CODE ###

import collections

if __name__ == "__main__":
    N = int(input()) 
    # int型のリスト
    A = list(map(int, input().rstrip().split(' ')))
    #print(A)
    
    # #TLE
    # ans = 0
    # for i, a in enumerate(A):
    #     target = A[i+a:]
    #     #print(target)
    #     for j, b in enumerate(target):
    #         if j  == b:
    #             #print(a, b)
    #             ans += 1
    # print(ans)
    
    L = [i+A[i] for i in range(N)]
    R = [i-A[i] for i in range(N)]
    c_l = collections.Counter(L)
    c_r = collections.Counter(R)
    #print(L)
    #print(c_l)
    #print(R)
    #print(c_r)
    ans = 0
    for k, v in c_l.items():
        v_ = c_r.get(k, 0)
        ans += v * v_
    print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
c = 0
for i in range(n-1):
  for j in range(i+1, n):
    k = j*2-i
    if k >= n:
        continue
    if len(set([s[i], s[j], s[k]]))==3:
      c += 1
print(r*g*b-c)


### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
c = 0
for i in range(N-2):
  for j in range(i+1,(i+N+1)//2):
    k = j*2-i
    if len(set([S[i], S[j], S[k]]))==3:
      c += 1
print(r*g*b-c)
### BUGGY CODE ###

n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(m)]
ds={} # ds[(l,r)]:rがlのどれだけ右にいるか
dr={} # dr[i]:r=iのヒントのlの集合
import sys
sys.setrecursionlimit(10**7)
def add(l,r,d):
  if (l,r) in ds and ds[(l,r)]!=d:
    print('No')
    #print(ds)
    exit()
  ds[(l,r)]=d
  if r in dr:
    dr[r].add(l)
  else:
    dr[r]=set([l])
  if l in dr:
    for i in dr[l]:
      add(i,r,ds[(i,l)]+d)

for l,r,d in lrd:
  add(l,r,d)

print('Yes')
#print(ds)


### FIXED CODE ###

n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(m)]
g=[[] for _ in range(n)]
for l,r,d in lrd:
  g[l-1].append([d,r-1])
  g[r-1].append([-d,l-1])

no_seen=set(range(n))
inf=float('inf')
dst=[inf]*n
while no_seen:
  todo=[[0,no_seen.pop()]]
  #print(todo)
  while todo:
    d,t=todo.pop()
    no_seen.discard(t)
    l=g[t]
    for di,ti in l:
      if dst[ti]!=inf and dst[ti]!=d+di:
        print('No')
        exit()
      elif dst[ti]!=inf and dst[ti]==d+di:
        pass
      else:
        todo.append([d+di,ti])
        dst[ti]=d+di

print('Yes')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Aug  2 21:11:34 2020

@author: NEC-PCuser
"""

N = int(input())

s = input()

l = 0
r = len(s) - 1
count = 0
while True:
	flg = False
	for i in range(l, r):
		if (s[i] == 'W'):
			l = i + 1
			flg = True
			break
	for j in range(r, l - 1, -1):
		if (s[j] == 'R'):
			r = j - 1
			if flg:
				count += 1
			break
	if flg == False:
		break
print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Aug  2 21:11:34 2020

@author: NEC-PCuser
"""

N = int(input())

s = input()

l = 0
r = len(s) - 1
count = 0
while True:
	flg = False
	for i in range(l, r):
		if (s[i] == 'W'):
			l = i + 1
			flg = True
			break
	for j in range(r, l - 1, -1):
		if (s[j] == 'R'):
			r = j - 1
			if flg:
				count += 1
			break
	else:
		break
	if flg == False:
		break
print(count)
### BUGGY CODE ###


import bisect

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

point = ["x"] * N
lis = []
notend = []

for i in range(N):

    lis.append([])
    notend.append(i)


for i in range(M):

    L,R,D = map(int,input().split())

    lis[L-1].append([R-1,D])
    lis[R-1].append([L-1,-1 * D])

ans = "Yes"
Q = []

while True:

    if len(notend) > 0:
        Q.append(notend.pop(0))
    else:
        break

    nmin = 0
    nmax = 0

    while len(Q) > 0:

        q = Q.pop(0)
        if point[q] == "x":
            point[q] = 0

        for rd in lis[q]:

            ind = bisect.bisect_left(notend,rd[0])

            #print (ind,notend,rd[0])

            if len(notend) > ind and notend[ind] == rd[0]:
                del notend[ind]
                point[rd[0]] = point[q] + rd[1]
                nmin = min(nmin,point[rd[0]])
                nmax = max(nmin,point[rd[0]])
                Q.append(rd[0])

            elif point[rd[0]] != point[q] + rd[1]:
                ans = "No"
                break

        if ans == "No":
            break

    if nmax - nmin > 10 ** 9:
        ans = "No"

    if  ans == "No":
        break

print (ans)


### FIXED CODE ###

from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")
### BUGGY CODE ###

import numpy as np
from fractions import gcd

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

p=10**9+7
n = 10 ** 6  # N は必要分だけ用意する
#fact = [1, 1]  # fact[n] = (n! mod p)
#factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用 逆元

for i in range(2, n + 1):
    #fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    #factinv.append((factinv[-1] * inv[-1]) % p)
#a//gcd(a,b)*b

def lcm(a,b):
    g=gcd(a,b)
    #return ((a*b)*pow(g,p-2,p))%p
    return a//gcd(a,b)*b

LCM=1
for x in A:
    LCM=lcm(LCM,x)



#print(LCM)
ans=0
LCM%=p
for i in range(N):
    ans+=(LCM*inv[A[i]])%p
    #ans+=(LCM*pow(A[i],p-2,p))%p
    ans%=p
print(ans)

### FIXED CODE ###


#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return a//gcd(a,b)*b

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=1
#LCM%=mod
for a in A:
  LCM=lcm(LCM, a)
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

print(int(ans%mod))
### BUGGY CODE ###

import math

A, B = map(int, input().split())

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

cf = [1]
for i in range(2,max(A,B)+1):
    if A % i == 0 and B % i == 0 and is_prime(i):
        cf.append(i)

print(len(cf))

### FIXED CODE ###

import math

A, B = map(int, input().split())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A_prime = set(prime_factorize(A))
B_prime = set(prime_factorize(B))

res = A_prime & B_prime

print(len(res)+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import numpy as np

N,B = map(int,input().split())
X = np.array(input().split(), dtype=np.int64)

Xcum = X.cumsum()

coef = np.full(N,2,dtype=np.int64)
coef[0] = 5
coef[1] = 0

answer = 10**18
for n in range(1,N+1):
    # 往復回数
    x = Xcum[::-n]
    cost = x.sum()*2 + 3*x[0] + B*(N+n)
    if len(x) > 1:
        cost -= 2*x[1]
    if answer > cost:
        answer = cost

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import itertools

N,B = map(int,input().split())
X = [int(x) for x in input().split()]

Xcum = tuple(itertools.accumulate(X))

coef = [2] * N
coef[0] = 5
coef[1] = 0

answer = min(sum(x*y for x,y in zip(Xcum[::-n], coef[:1+(N-1)//n])) + B*(N+n) for n in range(1,N+1))
print(answer)
### BUGGY CODE ###

# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

def bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

def is_stable(_in, out):
    n = len(_in)
    for i in range(n):
        for k in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if _in[i][1] == _in[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True
n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
c = bubble_sort(a[:], n)
if b == c:
    print("Stable")
else:
    print("Not stable")
for i in b:
    print(*i)


### FIXED CODE ###

# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

def bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

def is_stable(_in, out):
    n = len(_in)
    for i in range(n):
        for k in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if _in[i][1] == _in[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True

n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
if n > 10000:
    print("Not stable")
else:
    c = bubble_sort(a[:], n)
    if b == c:
        print("Stable")
    else:
        print("Not stable")
for i in b:
    print(*i)
### BUGGY CODE ###

S = input()
Q = int(input())
I = 0
for i in range(Q):
    Query = input().split()
    if len(Query) == 1:
        I = I + 1
    if len(Query) == 3:
        if (int(Query[1]) + I) % 2 == 0:
            S = S + Query[2]
        else:
            S = Query[2] + S
if I % 2:
    S = S[::-1]
print(S)


### FIXED CODE ###

S = input()
Q = int(input())
I = 0
L = ''
R = ''
for i in range(Q):
    Query = input().split()
    if Query[0] == "1":
        I = I + 1
    else:
        if (int(Query[1]) + I) % 2 == 0:
            R = R + Query[2]
        else:
            L = L + Query[2]
L = L[::-1]
S = L + S + R

if I % 2:
    S = S[::-1]
print(S)
### BUGGY CODE ###

a,b = map(int, input().split())
def make_soinsu(n):
    ans_val = [1]    
    s = 2
    while (n!=1):
        if n % s == 0:
            ans_val.append(s)
            n /= s
            s = 2
        else:
            s += 1
    ans_val = set(ans_val) #ダブりは削除。ダブりを残す場合は消す(4の場合は1,2となり、2は二つでない。)
    return ans_val
a_list = make_soinsu(a)
b_list = make_soinsu(b)
ans = 0
for i in a_list:
    if i in b_list:
        ans+=1
print(ans)

### FIXED CODE ###

a,b = map(int, input().split())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
import collections
a_list = collections.Counter(prime_factorize(a)).keys()
b_list = collections.Counter(prime_factorize(b)).keys()
ans = 0
for i in a_list:
    if i in b_list:
        ans+=1
print(ans+1) #1が入っていないから
### BUGGY CODE ###

import numpy as np

h,w = map(int, input().split())
s = (np.array([input() for _ in range(h)]))
ans = [list() for i in range(h)]
for key_i,i in enumerate(s):
  m = 0
  for j in i:
    if j == ".":
      m += 1
    else:
      for k in range(m):
        ans[key_i].append(m)
      m = 0
      ans[key_i].append(m)
  for k in range(m):
    ans[key_i].append(m)

ans = np.array(ans)
ans = ans.T
ans2 = [list() for i in range(w)]
for key_i,i in enumerate(ans):
  m = 0
  for j in i:
    if j:
      m += 1
    else:
      for k in range(m):
        ans2[key_i].append(m)
      m = 0
      ans2[key_i].append(m)
  for k in range(m):
    ans2[key_i].append(m)
print(np.max(ans + ans2) - 1)
  
  

### FIXED CODE ###

import numpy as np 
H, W = map(int, input().split())
S = (np.array([list(input()) for _ in range(H)]) == '.')
 

up = np.zeros((H, W), dtype=int)
down = np.zeros((H, W), dtype=int)
left = np.zeros((H, W), dtype=int)
right = np.zeros((H, W), dtype=int)
 
for i in range(H):
    up[i] = (up[i-1] + 1) * S[i]
    down[-i-1] = (down[-i] + 1) * S[-i-1]
    
for i in range(W):
    left[:, i] = (left[:, i-1] + 1) * S[:, i]
    right[:, -i-1] = (right[:, -i] + 1) * S[:, -i-1]

print(np.max(up+down+left+right) - 3)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split( ))
Edg = [[] for _ in range(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] = max(Dist[w],Dist[v] +1)####
            Q.append(w)

print(max(Dist))


### FIXED CODE ###

import sys
from collections import deque
n, m = map(int, input().split( ))
Edg = [[] for _ in range(n)]
rev_Edg = [[] for _ in range(n)]
deg = [len(rev_Edg[i]) for i in range(n)]


Root_check = [1]*n
Dist = [0]*n
for i in range(m):
    v1,v2 = map(int, sys.stdin.readline().split( ))
    v1-=1
    v2-=1
    Edg[v1].append(v2)
    rev_Edg[v2].append(v1)
    deg[v2] += 1
    Root_check[v2] = 0
    

Q =deque()
for i in range(n):
    if Root_check[i] == 1:
        Q.append(i)

while len(Q) > 0:
    v = Q.popleft()
    for w in Edg[v]:
        Dist[w] = max(Dist[w],Dist[v] +1)####
        deg[w] -=1 ############
        if deg[w] == 0:##########
            Q.append(w)###########
            


print(max(Dist))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
r=a[:]
r.extend([i-1 for i in a])
r.extend([i+1 for i in a])

for i in r:
  x=0
  for ai in a:
    if ai==i or ai-1==i or ai+1==i:
      x+=1
  ans=max(ans,x)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
an = [0]*(max(a)+2)
for i in a:
  if i!=0:
    an[i-1]+=1
  an[i+1]+=1
  an[i]+=1
print(max(an))
### BUGGY CODE ###

from collections import defaultdict
inf = 10**10
A = input()
N = len(A)
abc = 'abcdefghijklmbopqrstuvwxyz'
s_to_i = [defaultdict(lambda:N) for _ in range(N+1)]
for x in abc:   
    s_to_i[-1][x] = N
for i in range(N)[::-1]:
    for x in abc:
        s_to_i[i][x] = s_to_i[i+1][x]
    s_to_i[i][A[i]] = i
def C(x, i):
    now = i
    for i in range(x):
        now = max(s_to_i[now].values())+1
        if now == N+1:
            return True
    return False
def bisect(i):
    ok = N+1
    ng = 0
    while ok-ng>1:
        mid = (ok+ng)//2
        if C(mid, i):
            ok = mid
        else:
            ng = mid
    return ok
dp = [bisect(i) for i in range(N+1)]
n = dp[0]
ans = []
now = 0
for i in range(n):
    for x in abc:
        tmp = now
        tmp = s_to_i[now][x]+1
        if tmp>N or dp[tmp] == n-i-1:
            ans.append(x)
            now = tmp
            break

print(*ans, sep = "")
    
        





### FIXED CODE ###

from collections import defaultdict
inf = 10**10
A = list(map(lambda x:ord(x)-ord('a'), list(input())))
N = len(A)
abc = 'abcdefghijklmbopqrstuvwxyz'
s_to_i = [[N]*26 for _ in range(N+1)]
for i in range(N)[::-1]:
    for x in range(26):
        s_to_i[i][x] = s_to_i[i+1][x]
    s_to_i[i][A[i]] = i
dp = [0]*(N+2)
dp[-2] = 1
for i in range(N)[::-1]:
    now = max(s_to_i[i])+1
    dp[i] = dp[now]+1
n = dp[0]
now = 0
ans = []
for i in range(n):
    for x in range(26):
        tmp = s_to_i[now][x]+1
        if dp[tmp] <= n-i-1:
            ans.append(chr(x+ord('a')))
            now = tmp
            break
print(*ans, sep = '')