Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
L = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    A = a - 1
    B = b - 1
    L[A].append(B)
    L[B].append(A)
BFS = list()
BFS.append([0])
ans = [[] for i in range(n - 1)]
while [] in ans:
    BFS.append([])
    for i in BFS[-2]:
        for j in L[i]:
            BFS[-1].append(j)
            ans[j - 1].append(i + 1)
            L[j].remove(i)
print('Yes')
for k in range(len(ans)):
    print(ans[k][0])

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
bridge = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    bridge[a - 1].append(b - 1)
    bridge[b - 1].append(a - 1)
queue = deque([0])
ans = [[] for i in range(n)]
ans[0].append('god')
while queue:
    now = queue.popleft()
    for factor in bridge[now]:
        if not (ans[factor]):
            ans[factor].append(now)
            queue.append(factor)
print('Yes')
for i in range(1, len(ans)):
    print(ans[i][0]+1)
a = int(input())
b = int(input())
al = [1,2,3]

remain = al.remove(a)
remain = al.remove(b)
print(remain[0])




### FIXED CODE ###

a = int(input())
b = int(input())
al = [1,2,3]

al.remove(a)
al.remove(b)
print(al[0])
N = int(input())
A = list(map(int, input().split()))

X = [-1, -1, -1]
ans = 1
for a in A:
    t = X.count(a-1)
    ans = ans * t % 1000000007
    X[X.index(a-1)] += 1
print(ans)


### FIXED CODE ###

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

X = [-1, -1, -1]
ans = 1
for a in A:
    t = X.count(a-1)
    ans = ans * t % 1000000007
    if a-1 not in X:
        print(0)
        exit()
    idx = X.index(a-1)
    X[idx] += 1
print(ans)
K,X=(int,input().split())
if 500*K>=X:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

K,X=map(int,input().split())
if 500*K >=X:
    print("Yes")
else:
    print("No")
from networkx import*
#print(max(map(len,connected_components(Graph(map(str.split,[*open(0)][1:]))))))
#(n,m),*t=map(str.split,open(0));print(max(map(len,connected_components(Graph(t[:int(m)])))))
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
G = Graph(edges)
ccs = connected_components(G)
ans = max(map(len, ccs))
print(ans)


### FIXED CODE ###

from networkx import*
_,*t=map(str.split,open(0))
print(max(1,1,*map(len,connected_components(Graph(t)))))
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))

case = [0] * (N + 1)
case[0] = 1
if not 1 in A:
    case[1] = 1

if A[0]==1:
    j=1
    flag=True
else:
    j=0
    flag=False
for x in range(2, N + 1):
    if x==A[j]:
        case[x] = 0
        j=(j+1)%M
        flag=True
    elif flag==True:
        case[x] = case[x - 2]
        flag=False
    else:
        case[x] = case[x - 1] + case[x - 2]
        flag=False

print(case[N] % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
A = [1] * (N + 1)
ans = [0] * (N + 1)
ans[0] = 1
for _ in range(M):
    A[int(input())] = 0
for i in range(1, N + 1):
    ans[i] = (ans[i - 2] * A[i - 2] + ans[i - 1] * A[i - 1]) % 1000000007

print(ans[N])
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    S = input()
    K = int(input())
    last = ""
    a = 0
    if len(S) == 1:
        print(K // 2)
        return
    for s in S:
        if s == last:
            a += 1
            last = ""
        else:
            last = s
    b = 0
    if S[0] == S[-1]:
        if S[0:2] == S[-2:] and len(S) > 2:
            k = 0
            while True:
                if S[k] == S[len(S) - k - 1]:
                    k += 1
                else:
                    break
            b = k % 2
        else:
            if S[1] == S[0] or S[-2] == S[0]:
                b = 0
            else:
                b = 1

    print(a * K + b * (K - 1))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    S = input()
    K = int(input())
    last = ""
    a = 0
    A = set(list(S))
    if len(S) == 1:
        print(K // 2)
        return

    elif len(A) == 1:
        if len(S) % 2 == 1:
            a = K % 2
            print(len(S) * (K // 2) + (len(S) // 2) * a)
        else:
            a = K % 2
            print(len(S) * (K // 2) + (len(S) // 2) * a)
    else:
        for s in S:
            if s == last:
                a += 1
                last = ""
            else:
                last = s
        if S[0] != S[-1]:
            print(a * K)
        elif len(S) == 2:
            print(a * K)
        else:
            x = 0
            y = 0
            for i in range(len(S) // 2):
                if S[i] == S[0]:
                    x += 1
            for j in range(len(S) // 2):
                if S[len(S) - j - 1] == S[-1]:
                    y += 1

            if x % 2 == 1 and y % 2 == 1:
                b = 1
            else:
                b = 0

            print(a * K + b * (K - 1))


if __name__ == "__main__":
    main()
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
nizi = [0] * (max(A)+1)
for i in range(len(A)):
    # print(A[i], A)
    nizi[A[i]] += 1
sumall = sum(A)
for q in range(Q):
    B, C = map(int, input().split())
    sumall += (C-B) * nizi[B]
    nizi[C] =+ nizi[B]
    nizi[B] = 0
    print(sumall)

### FIXED CODE ###



N = int(input())
A = list(map(int, input().split()))
Q = int(input())
nizi = [0] * (10**5+1)
for i in range(len(A)):
    # print(A[i], A)
    nizi[A[i]] += 1
sumall = sum(A)
for q in range(Q):
    # print(nizi)
    B, C = map(int, input().split())
    sumall += (C-B) * nizi[B]
    nizi[C] += nizi[B]
    nizi[B] = 0
    print(sumall)
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()

d = Counter(readInts())

d = [i for i in sorted(d.items(), reverse=True) if i[1]>=2]

if len(d)==0:
	print(0)
	exit()
elif len(d)==1:
	if d[0][1]>=4:
		pass
	else:
		print(0)
		exit()
if d[0][1]>=4:
	print(int(d[0][0])**2)
else:
	print(int(d[0][0])*int(d[1][0]))


### FIXED CODE ###

from collections import defaultdict
from collections import deque
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

w,h,x,y = readInts()

if x==w/2 and y==h/2:
	d = 1
else:
	d = 0

print(w*h/2,d)
"""
Writer: SPD_9X2
https://atcoder.jp/contests/apc001/tasks/apc001_e

厳密な照明は難しいが…
直径を取る
直径の端点からbfs

全ての頂点に関して、部分木に少なくとも一つのアンテナを持つかのフラグを管理
子の数をkとする。その内x個がtrueの場合、k-1-x個のアンテナを追加。自分のflagをtrueにする
子がfalseで、子が0 or 1つしかない場合のみfalse継続

簡単な木では最適になることを実験したがどうだろうか…？
"""

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis,now

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    lis[a].append(b)
    lis[b].append(a)

td,tp,stp = NC_Dij(lis,0)


ans = 0

def dfs(v,p):

    x = 0
    c = 0
    retflag = False
    for nex in lis[v]:

        if nex != p:
            c += 1
            have = dfs(nex,v)
            retflag = have or retflag
            if have:
                x += 1

    if c-1-x > 0:
        retflag = True
    global ans
    ans += max(0,c-1-x)

    return retflag

dfs(stp,stp)
print (ans+1)



### FIXED CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/apc001/tasks/apc001_e

厳密な照明は難しいが…
直径を取る
直径の端点からbfs

全ての頂点に関して、部分木に少なくとも一つのアンテナを持つかのフラグを管理
子の数をkとする。その内x個がtrueの場合、k-1-x個のアンテナを追加。自分のflagをtrueにする
子がfalseで、子が0 or 1つしかない場合のみfalse継続

簡単な木では最適になることを実験したがどうだろうか…？
"""
import sys
sys.setrecursionlimit(3*10**5)

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis,now

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    lis[a].append(b)
    lis[b].append(a)

td,tp,stp = NC_Dij(lis,0)


ans = 0

def dfs(v,p):

    x = 0
    c = 0
    retflag = False
    for nex in lis[v]:

        if nex != p:
            c += 1
            have = dfs(nex,v)
            retflag = have or retflag
            if have:
                x += 1

    if c-1-x > 0:
        retflag = True
    global ans
    ans += max(0,c-1-x)

    return retflag

dfs(stp,stp)
print (ans+1)
def curserch(N,k,t,P,n):
    g = 0
    t = t+1
    P[k]["d"] = t
    for i in range(1,n+1):
        if N[k][i]==1 and P[i]["d"]==0:
            P[i]["f"] = g = curserch(N,i,t,P,n)
    if g !=0:
        return g+1
    else:
        return t+1

n = int(input())
A = [[0 for j in range(n+1)] for i in range(n+1)]


for i in range(n):
    vec = input().split()
    u = int(vec[0])
    k = int(vec[1])
    nodes = vec[2:]
    for i in range(int(k)):
        v = int(nodes[i])
        A[u][v] = 1

P=[{"d":0} for i in range(n+1)]
P[1]["f"] = curserch(A,1,0,P,n)
j=1
for i in range(1,n+1):
    print(i,P[i]["d"],P[i]["f"]) 

### FIXED CODE ###

T = [0]

def curserch(N,k,T,P,n):
    T[0] = T[0]+1
    P[k]["d"] = T[0]
    for i in range(1,n+1):
        if N[k][i]==1 and P[i]["d"]==0:
            curserch(N,i,T,P,n)
            T[0] = T[0]+1
            P[i]["f"]=T[0]


n = int(input())
A = [[0 for j in range(n+1)] for i in range(n+1)]


for i in range(n):
    vec = input().split()
    u = int(vec[0])
    k = int(vec[1])
    nodes = vec[2:]
    for i in range(int(k)):
        v = int(nodes[i])
        A[u][v] = 1

P=[{"d":0} for i in range(n+1)]
for i in range(1,n+1):
    if P[i]["d"]==0:
        curserch(A,i,T,P,n)
        T[0] = T[0]+1
        P[i]["f"]=T[0]
for i in range(1,n+1):
    print(i,P[i]["d"],P[i]["f"])
n=int(input())
a=list(map(int,input().split()))
b=[]
sum_=0
for i in a:
  sum_+=i
  b.append(sum_a)
ans=10**18
for i in range(n-1):
  ans=min(ans,abs(b[-1]-b[i]))
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
sum_=0
for i in a:
  sum_+=i
  b.append(sum_)
ans=10**18
for i in range(n-1):
  ans=min(ans,abs(b[-1]-b[i]*2))
print(ans)
a,b,c=input().split()
while(c>0):
  while(a>0):
    a-=1
  while(b>0):
    b-=1
print(a," ",b)
  

### FIXED CODE ###

a, b, k = map(int, input().split())
if (a, b) == (0, 0):
    print(0, 0)
    exit(0)
if a - k < 0:
    print(0, max(0, b - (k-a)))
else:
    print(a-k, b)
a, b, c = map(int, input().split())
from math import factorial
N = 10**9+7
def combinations_count(n, r, N):
    ''' 組み合わせ '''
    return (factorial(n) // (factorial(n - r) * factorial(r)) ) % N

lis = list(range(1, a+1))
lis.remove(a)
lis.remove(b)

data1 = list(map(combinations_count, lis))
print(lis)
print(combinations_count(5, 2, N))

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,a,b = nm()
mod = 10**9 + 7
s = pow(2,n,mod) - 1

def fur(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod) % mod

print((s - fur(n,a) - fur(n,b)) % mod)
n = int(raw_input())
ans = []
for i in range(n):
	marks = map(float, raw_input().split())
	AB = (marks[1] - marks[3]) / (marks[0] - marks[2])
	CD = (marks[5] - marks[7]) / (marks[4] - marks[6])
	if AB == CD:
		print 'YES'
	else:
		print 'NO'

### FIXED CODE ###

for i in range(int(input())):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    if abs((y1 - y2) * (x3 - x4) - (y3 - y4) * (x1 - x2)) < 1.e-10:
        print('YES')
    else:
        print('NO')
c11,c12,c13=map(int,input().split())
c21,c22,c23=map(int,input().split())
c31,c32,c33=map(int,input().split())
if (c11-c12==c21-c22==c31-c32 and c12-c13==c22-c23==c32-c33 and c13-c11==c23-c21==c33-c31 and c11-c21==c12-c22==c13-c23 and c21-c31==c22-c32==c23-c33 and c31-c11==c32-c12==c33-c13 :
    print("Yes")
else:
    print("No")

### FIXED CODE ###

c11,c12,c13=map(int,input().split())
c21,c22,c23=map(int,input().split())
c31,c32,c33=map(int,input().split())
if (c11-c12==c21-c22==c31-c32 and c12-c13==c22-c23==c32-c33 \
and c13-c11==c23-c21==c33-c31 and c11-c21==c12-c22==c13-c23 \
and c21-c31==c22-c32==c23-c33 and c31-c11==c32-c12==c33-c13) :
    print("Yes")
else:
    print("No")
n = int(input())
D1D2 = [map(int, input().split()) for _ in range(5)]
D1,D2 = [list(i) for i in zip(*D1D2)]
count = 0

for i in range(n-1):
  if D1[i] == D2[i]:
    count += 1
  else:
    count *= 0

if count >= 3:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = int(input())
d = [list(map(int,input().split())) for i in range(n)]
count = 0

# [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6]]

for i in d:
  if i[0] == i[1]:
    count += 1
  else:
    count = 0
  if count == 3:
    print('Yes')
    exit()
print('No')
S = input()
print(min((abs(753 - int(S[i:i+3])) for i in range(len(S)-2))))


### FIXED CODE ###

x = int(input())

if x in (7, 5, 3):
  print("YES")
else:
  print("NO")
from itertools import accumulate
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

asum = list(accumulate(a))
bsum = list(accumulate(b))

ans, j = 0, m-1
for i in range(n):
    if asum[i] > k:
        break
    while bsum[j] > k - asum[i]:
        j -= 1
    ans = max(ans, i+1+j+1)
print(ans)

### FIXED CODE ###

from itertools import accumulate
import bisect
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.insert(0,0)
b.insert(0,0)

asum = list(accumulate(a))
bsum = list(accumulate(b))

ans = 0
for i, v in enumerate(asum):
    if v > k:
        break
    index = bisect.bisect_right(bsum, k-v)
    ans = max(ans, i + index-1)
print(ans)
max_score = 0
total = int(input())
now = 0
count = 0 
i = 0
number_list = list(map(int,input().split(" ")))
while i == 0:
    if number_list[now] >= number_list[now+1] and now+1 != total-1:
        count += 1
        now += 1
    elif number_list[now] >= number_list[now+1] and now+1 == total-1:
        count += 1
        now += 1
        if max_score < count:
            max_score = count
        break
    elif number_list[now] < number_list[now+1] and now+1 == total-1:
        break
    else:
        now += 1
        if max_score < count:
            max_score = count
            count = 0
        else:
            count = 0
            continue
print(max_score)

### FIXED CODE ###

max_score = 0
total = int(input())
now = 0
count = 0 
i = 0
if total == 1:
    print(0)
    exit()
number_list = list(map(int,input().split(" ")))
while i == 0:
    if number_list[now] >= number_list[now+1] and now+1 != total-1:
        count += 1
        now += 1
    elif number_list[now] >= number_list[now+1] and now+1 == total-1:
        count += 1
        now += 1
        if max_score < count:
            max_score = count
        break
    elif number_list[now] < number_list[now+1] and now+1 == total-1:
        break
    else:
        now += 1
        if max_score < count:
            max_score = count
            count = 0
        else:
            count = 0
            continue
print(max_score)
in_ = input()
n, k = in_.split()

if ((n - 1) <= 0):
  print("NO")
  exit()

if (1 <= (n - 1) / k):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

in_ = input()
n, k = map(int, in_.split())

if (k == 1):
    print("YES")
    exit()

if ((n % 2) == 1):
    n += 1

if (2 <= (n / k)):
    print("YES")
else:
    print("NO")
n, y = map(int, input().split())
lists=[]
lists_2=[]
for i in range(n+1):
  for j in range(n+1-i):
    lists.append([i, j, n-i-j])

for k in lists:
  if 10000*k[0] + 5000*k[1] + 1000*k[2] == y:
    lists_2.append(k)

if len(k) == 0:
  print('-1 -1 -1')
else:
  print(lists_2[0][0],lists_2[0][1],lists_2[0][2])

### FIXED CODE ###

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

k = 0
for i in range(min(n,y//10000),-1,-1):
  for j in range(n+1-i):
    if 10000*i + 5000*j + 1000*(n-i-j) == y:
      print(i, j, n-i-j)
      k += 1
      exit()
      
if k == 0:
  print('-1 -1 -1')
import math

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

a = A[0]

for i in range(1, N):
    a = int((a * A[i]) / math.gcd(a, A[i]))

b = 0

for i in range(N):
    b += a // A[i]

print(a / b)


### FIXED CODE ###

import math

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

# num is numerator
# den is denominator
num, den = A[0], 0

for i in A:
    num = (num * i) // math.gcd(num, i)

for i in A:
    den += num // i

ans = num / den
print(ans)
length = int(input())
eles = list(map(int, input().split()))

for i in range(_length):
    val = _list[i]
    j = i - 1
    while j >= 0 and _list[j] > val:
        _list[j+1] = _list[j]
        j -= 1
    _list[j+1] = val
    print(*_list)

### FIXED CODE ###

length = int(input())
eles = [int(i) for i in input().split()]

for i in range(length):
    val = eles[i]
    j = i - 1
    while j >= 0 and eles[j] > val:
        eles[j+1] = eles[j]
        j -= 1
    eles[j+1] = val
    print(*eles)
def solve(): # 071C - Make a Rectangle
    n = int(input())
    sides = list(map(int, input().split(" ")))
    check_dual = {}
    possible_sides = []

    for i in sides:
        if i in check_dual:
            check_dual[i] += 1
        else:
            check_dual[i] = 1

    tmp_square = 0
    for k, v in check_dual.items():
        if v >= 4 and k > tmp_square:
            tmp_square = k
        elif v == 2 or v == 3:
            possible_sides.append(k)
        else:
            pass

    possible_sides.sort(reverse=True)
    if tmp_square == 0 and len(possible_sides) < 2:
        print(0)
    else:
        print(max(possible_sides[0] * possible_sides[1],
                  tmp_square ** 2))
solve()

### FIXED CODE ###

def solve(): # 071A - Meal Delivery
    x, A, B = list(map(int, input().split(" ")))
    da = abs(x - A)
    db = abs(x - B)
    if da > db:
        print("B")
    else:
        print("A")


solve()
n = int(input())
s = input()

def z_algorythm(s):
    n = len(s)
    LCP = [0]*n
    c = 0
    for i in range(1, n):
        if i + LCP[i-c] < c + LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and s[j] == s[i+j]:
                j += 1
                LCP[i] = j
                c = i
    LCP[0] = n
    return LCP

ans = 0
for i in range(n):
    LCP = z_algorythm(s[i:])
    for j, len in enumerate(LCP):
        tmp = min(len, j)
        ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    check = set()
    for i in range(N - x + 1):
        check.add(S[i: i + x])
        if S[i + x: i + 2 * x] in check:
            ok = x
            break
    else:
        ng = x

print(ok)
n=int(input())
if n%2==1:print(0)
ans=0
else:
  for i in range(1,26):
    ans+= n//(5**i)
print(ans)

### FIXED CODE ###

n=int(input())
if n%2==1:print(0)

else:
  ans=0
  for i in range(100):
    ans+= n//(10*5**i)
  print(ans)
import numpy

inp=input().split(" ")
n=int(inp[0])
m=int(inp[1])
inh=input().split(" ")
for i in range(len(inh)):
  inh[i]=int(inh[i])
pairs=numpy.zeros(2*m,dtype=">i4").reshape(-1,2)
for i in range(m):
  a=input().split(" ")
  pairs[i][0]=int(a[0])
  pairs[i][1]=int(a[1])
lists=[[] for i in range(n+1)]
for i in range(len(pairs)):
  lists[pairs[i][0]-1].append(pairs[i][1])
  lists[pairs[i][1]-1].append(pairs[i][0])
for i in range(len(lists)):
  if len(lists[i]) <= 1:
    lists[i]=list(set(lists[i]))
count=0
for i in range(len(lists)):
  if len(lists[i])==0:
    count+=1
    continue
  for j in range(len(lists[i])):
    if inh[i] <= inh[lists[i][j]]:
      break
    if j == len(lists[i])-1:
      count+=1
print(count)

### FIXED CODE ###

import numpy

inp=input().split(" ")
n=int(inp[0])
m=int(inp[1])
inh=input().split(" ")
for i in range(len(inh)):
  inh[i]=int(inh[i])
pairs=numpy.zeros(2*m,dtype=">i4").reshape(-1,2)
for i in range(m):
  a=input().split(" ")
  pairs[i][0]=int(a[0])
  pairs[i][1]=int(a[1])
lists=[[] for i in range(n)]
for i in range(len(pairs)):
  lists[pairs[i][0]-1].append(pairs[i][1]-1)
  lists[pairs[i][1]-1].append(pairs[i][0]-1)
for i in range(len(lists)):
  lists[i]=list(set(lists[i]))
count=0
for i in range(len(lists)):
  if len(lists[i])==0:
    count+=1
    continue
  for j in range(len(lists[i])):
    if inh[i] <= inh[lists[i][j]]:
      break
    if j == len(lists[i])-1:
      count+=1
print(count)
N=int(input())
m
change=int(N%1000)+1-N
print(change)


### FIXED CODE ###

N = int(input())
if (N % 1000 == 0):
    m = (int(N/1000))
else:
    m=(int(N/1000)+1)
change=1000*m-N
print(change)
import sys
import numpy as np

def solve(S):
	M = 2019
	t = 1
	ans = 0
	c = np.zeros(M, dtype=np.int64)
	c[0] = 1
	r = 0
	for d in S:
		r = (d * t + r) % M
		ans += c[r]
		c[r] += 1
		t = t * 10 % M
	return ans



def cc_export():
	from numba.pycc import CC
	cc = CC('my_module')
    S = np.array([], dtype=np.int32)
	cc.export('solve', numba.i8(numba.typeof(S)))(solve)
	cc.compile()

if __name__ == '__main__':
	import sys
	if sys.argv[-1] == 'ONLINE_JUDGE':
		cc_export()
		exit(0)
	from my_module import solve
	S = sys.stdin.buffer.readline().decode('utf-8').rstrip()
	S = np.array([int(d) for d in S[::-1]], dtype=np.int32)
	print(solve(S))


### FIXED CODE ###

import sys

M = 2019
S = sys.stdin.readline().rstrip()
N = len(S)

dmod = [0] * (N + 1)
amod = [0] * (N + 1)
tenmod = 1
prev_amod = 0
mcnt = [0] * 2019
ans = 0
for i in range(N, -1, -1):
    d = ord(S[i]) - ord("0") if i < N else 0
    dmod[i] = d * tenmod % M
    amod[i] = (dmod[i] + prev_amod) % M
    ans += mcnt[amod[i]]
    mcnt[amod[i]] += 1
    tenmod = tenmod * 10 % M
    prev_amod = amod[i]
print(ans)
s = list(input())
t = list(input())
 
p = s.sort()
q = t.sort()
r = q.reverse()
 
if (p < r):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = list(input())
t = list(input())

s.sort()
t.sort()
t.reverse()

if (s < t):
  print('Yes')
else:
  print('No')
from functools import reduce

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

P = reduce(lambda a,b:a*b,As)

print(P/sum([P/a for a in As]))

### FIXED CODE ###

from functools import reduce

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

P = reduce(lambda a,b:a*b,As)

print(P/sum([P/a for a in As]))
L=int(input())
A=[int(input()) for i in range(L)]
su=sum(A)
#print(A)

DP=[[0 for i in range(5)] for j in range(L)]

DP[1]=[A[0],min(A[0],A[0]%2),min(A[0],A[0]%2,(A[0]+1)%2),min(A[0],A[0]%2,(A[0]+1)%2),min(A[0],A[0]%2,(A[0]+1)%2)]

for i in range(2,L):
    mod=A[i]%2
    if A[i]==0 :
        mod=2
    DP[i][0]+=DP[i-1][0]+A[i]
    DP[i][1]+=min(DP[i-1][0],DP[i-1][1])+mod
    DP[i][2]+=min(DP[i-1][j] for j in range(3))+(mod+1)%2
    DP[i][3]+=min(DP[i-1][j] for j in range(4))+mod
    DP[i][4]+=min(DP[i-1][j] for j in range(5))+A[i]

#print(DP)
print(min(DP[L-1]))


### FIXED CODE ###

L=int(input())
A=[int(input()) for i in range(L)]
su=sum(A)
#print(A)

DP=[[0 for i in range(5)] for j in range(L+1)]

mod=A[0]%2
if A[0]==0 :
    mod=2
DP[1]=[A[0],min(A[0],mod%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2)]

for i in range(2,L+1):
    mod=A[i-1]%2
    if A[i-1]==0 :
        mod=2
    DP[i][0]+=DP[i-1][0]+A[i-1]
    DP[i][1]+=min(DP[i-1][0],DP[i-1][1])+mod
    DP[i][2]+=min(DP[i-1][j] for j in range(3))+(mod+1)%2
    DP[i][3]+=min(DP[i-1][j] for j in range(4))+mod
    DP[i][4]+=min(DP[i-1][j] for j in range(5))+A[i-1]

#print(DP)
print(min(DP[L]))