Harryxun/stf_run huggingface dataset:
n, q = [int(i) for i in input().split()]
a1 = {}
a2 = {}
for _ in range(n - 1):
    x, y = [int(i) - 1 for i in input().split()]
    if x in a1:
        a1[x].append(y)
    else:
        a1[x] = [y]
    if x in a2:
        a2[x].append(y)
    else:
        a2[x] = [y]
root = [-1] * n


def c(ind=0, ro=-1):
    global root
    if root[ind] != -1:
        return 0
    root[ind] = ro
    if ind in a1:
        for i in a1[ind]:
            c(i, ind)
    if ind in a2:
        for i in a2[ind]:
            c(i, ind)


c()
p = [0] * n
for _ in range(q):
    x, y = [int(i) for i in input().split()]
    p[x - 1] += y
r = []
for i in range(n):
    j = i
    k = 0
    while True:
        k += p[j]
        if j == -1:
            break
        j = root[j]
    r.append(str(k))
print(" ".join(r))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


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


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))
import sys

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

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

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

L = lcm(N, M)
X = ["A"] * L

for i in range(N):
    index = i * (L // N)
    X[index] = S[i]

for i in range(M):
    index = i * (L // M) 
    if X[index] != "A" and X[index] != T[i]:
        print(-1)
        sys.exit()
    
print(L)

### FIXED CODE ###

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

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

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

L = lcm(N, M)
s = L // M
t = L // N

if S[::s] != T[::t]:
    L = -1
print(L)
n = int(input())
a = list(map(int, input().split()))

a.sort()
cur = a[0]
ans1 = 1
ans = 1

for i in range(max(a)+1):
    if a[i + 1] - a[i] <= 2:
        cur = a[i]
        ans1 = a.count(cur) + a.count(cur + 1) + a.count(cur + 2)

        if ans < ans1:
            ans = ans1
        ans1 = 0

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
max_a = max(a)

b = [0]*(max_a + 2)

for i in a:
    b[i] += 1

ans = 0
for i in range(max_a + 1):
    tmp = b[i-1] + b[i] + b[i+1]
    ans = max(ans, tmp)

print(ans)
a = input()
if a[2] ==a[3]:
    print ("Yes")
else:
    print ("No")

### FIXED CODE ###

a = input()
if a[2] ==a[3] and a[4]==a[5]:
    print ("Yes")
else:
    print ("No")
k = input()
if k % 2 == 0:
  print(k*k/4)
else:
  print((k//2)*((k//2)+1))

### FIXED CODE ###

k = int(input())
 
if k%2 == 0:
  print((k//2)**2)
else:
  print((k//2)*((k//2)+1))
s=int(input())
G =[s]
while all(G[i]!=G[-1] for i in range(len(G)-1)):
  if G[-1] % 2==0:
    G.append(int(x/2))
  else:
    G.append(int(3*x+1))
print(len(G))

### FIXED CODE ###

s=int(input())
G =[]
while (s not in G):
  G.append(s)
  if s % 2==0:
    s = int(s//2)
  else:
    s = int(3*s+1)
print(len(G)+1)
n, m = map(int, input().split())
xyz = [list(map(int, input().split())) for _ in range(n)]
ans = 0

for elem in combinations(xyz, m):
    x = abs(sum([e[0] for e in elem]))
    y = abs(sum([e[1] for e in elem]))
    z = abs(sum([e[2] for e in elem]))
    ans = max(ans, x + y + z)
print(ans)


### FIXED CODE ###

from itertools import product

n, m = map(int, input().split())
xyz = [list(map(int, input().split())) for _ in range(n)]
ans = 0

for e in product([1, -1], [1, -1], [1, -1]):
    xyz.sort(key=lambda v: (v[0] * e[0]) + (v[1] * e[1]) + (v[2] * e[2]))
    tmp = xyz[:m]
    ans = max(ans, abs(sum([e[0] for e in tmp])) + abs(sum([e[1] for e in tmp])) + abs(sum([e[2] for e in tmp])))
print(ans)
Cnd = list(map(int,input().split()))
Cnd = sorted(Cnd)
result = 'No'
if Cnd[0]=Cnd[1]+Cnd[2]:
	result ='Yes'
id Cnd[0]+Cnd[1]=Cnd[2]:
	result ='Yes'
print(result)

### FIXED CODE ###

Cnd = list(map(int,input().split()))
Cnd = sorted(Cnd)
result = 'No'
if Cnd[0]==Cnd[1]+Cnd[2]:
	result ='Yes'
if Cnd[0]+Cnd[1]==Cnd[2]:
	result ='Yes'
print(result)
import sys
input = sys.stdin.readline


def main():
    X = int(input().rstrip())
    B = -1
    for i in range(100):
        if X - 1 == i ** 5:
            A = i
            break

    print(A, B)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
 
def main():
    X = int(input().rstrip())
    f = 0
    for a in range(-150, 150):
        for b in range(-150, 150):
            i = a ** 5 - b ** 5
            if i == X:
                print(a, b)
                f = 1
                break
 
        if f:
            break
 
 
if __name__ == '__main__':
    main()
N = int(input())
D = list(map(int, input().split()))

M = int(input())
T = list(map(int, input().split()))

d = [0 for _ in range(200005)]

ans = "YES"

for i in range(N):
    d[D[i]] += 1

for i in range(M):
    # print(d[T[i]-1])
    d[T[i]] -= 1
    if d[T[i]] < 0:
        ans = "NO"
        break

print(ans)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
d = tuple(map(int, input().split()))
m = int(input())
t = tuple(map(int, input().split()))
l = defaultdict(int)
for x in d:
    l[x] += 1
for y in t:
    if l[y] == 0:
        print('NO')
        exit()
    l[y] -= 1
print('YES')
D, N = map(int,input().split())
ls = [0]*1000000
for i in range(1,10**6):
    if i % 100 == 0:
        ls[i] = 1
    if i % 10000 == 0:
        ls[i] = 2
ii = 0
for i in range(1,10**6):
    if ls[i] == D:
        ii += 1
    if ii == N:
        ans = i
        break
print(ans)

### FIXED CODE ###

D, N = map(int,input().split())
ls = [0]*2000000
for i in range(1,2*10**6):
    if i % 100 == 0:
        ls[i] = 1
    if i % 10000 == 0:
        ls[i] = 2
    if i % 1000000 == 0:
        ls[i] = 3
ii = 0
for i in range(1,2*10**6):
    if ls[i] == D:
        ii += 1
    if ii == N:
        ans = i
        break
print(ans)
# 整数の入力
N = int(input())
 
print( (10**(N-2) * N * (N-1) -7) / (10**9 + 7))

### FIXED CODE ###

# 整数の入力
N = int(input())
 
print((10 ** N - 2* 9 ** N + 8 ** N) % (10 ** 9 + 7))
X, Y = map(int, input().split())
for a in range(X+1):
    b = X - a
    if 2 * a + 4 * b == Y:
        print('Yes')
        exit()
print('No')X, Y = map(int, input().split())
for a in range(X+1):
    b = X - a
    if 2 * a + 4 * b == Y:
        print('Yes')
        exit()
print('No')

### FIXED CODE ###

X, Y = map(int, input().split())
for a in range(X+1):
    b = X - a
    if 2 * a + 4 * b == Y:
        print('Yes')
        exit()
print('No')
while True:
	students,places = map(int,raw_input().split())
	if students == 0 and places == 0:
		break
	res = dict(zip(range(1,places+1),[0]*places))
	for i in range(students):
		points = map(int,raw_input().split())
		for j in range(1,places+1):
			res[j] += points[j]
	for k,v in sorted(res.items(),key=lambda x:x[1], reverse=True):
		print k,
	print "\n"

### FIXED CODE ###

while True:
	students,places = map(int,raw_input().split())
	if students == 0 and places == 0:
		break
	res = dict(zip(range(places),[0]*places))
	for i in range(students):
		points = map(int,raw_input().split())
		for j in range(places):
			res[j] += points[j]
	for k,v in sorted(res.items(),key=lambda x:x[1], reverse=True):
		print k+1,
	print
b=input()
if b=="A":
    print "T"
if b=="T":
    print "A"
if b=="C":
    print "G"
if b=="G":
    print "C"

### FIXED CODE ###

b=raw_input()
if b=="A":
    print "T"
if b=="T":
    print "A"
if b=="C":
    print "G"
if b=="G":
    print "C"
N = int(input())
A = int(input())
B = int(input())
if N ==1:
    print("Hello World")
else:
    print(A+B)

### FIXED CODE ###

N = int(input())
if N == 1:
    print("Hello World")
elif N ==2:
    A = int(input())
    B = int(input())
    print(A+B)
x = int(input())
y = int(input())

print(x + y/2)

### FIXED CODE ###

x, y = tuple(map(int, input().split()))

print(int(x + y/2))
tmp = [int(i) for i in input().split(" ")]
n = tmp[0]
k = tmp[1]
a = [int(i) for i in input().split(" ")]
import numpy as np
uni, co = np.unique(a, return_counts=True)
ind = [np.sum(co[:uni.tolist().index(i)]) for i in a]
c = 0
a = np.array(a)
for i in range(len(a)):
    c += np.sum(a[i:]<a[i])
m = 10**9+7
tm = int(c)*int(k) % m
if k % 2 == 0:
    t = k * (k//2-1) + k//2
    t %= m
else:
    t = k * (k//2)
    t %= m
print((np.sum(ind)*t+tm) % m)

### FIXED CODE ###

tmp = [int(i) for i in input().split(" ")]
n = tmp[0]
k = tmp[1]
a = [int(i) for i in input().split(" ")]
import numpy as np
a = np.array(a)
uni = np.unique(a)
co = [np.sum(a==i) for i in uni]
ind = np.array([np.sum(co[:uni.tolist().index(i)]) for i in a]).astype(np.int32)
c = 0

for i in range(len(a)):
    c += np.sum(a[i:]<a[i])
m = 10**9+7
tm = int(c)*int(k) % m
if k % 2 == 0:
    t = k * (k//2-1) + k//2
    t %= m
else:
    t = k * (k//2)
    t %= m
print((int(np.sum(ind))*t+tm) % m)
from collections import Counter
n = int(input())
a = list()
for _ in range(n):
    a.append(list(map(int, input().split())))
if n in [1,2]:
    print(1)
else:
  a.sort()
    diff = list()
    for i in range(len(a) - 1):
        for j in range(i+1, len(a)):
            x = a[j][0]-a[i][0]
            y = a[j][1]-a[i][1]
            if x<0 and y<0:
                z = (-x,-y)
            elif x<0 and y>0:
                z = (-x,-y)
            else:
                z = (x,y)
            diff.append(z)
    t_diff = Counter(diff).most_common(1)[0][1]
    print(n-t_diff)


### FIXED CODE ###

n , k = map(int, input().split())
if k == 1:
  print(0)
else:
  print(n-k)
n=int(input())
T,X,Y=0,0,0

a='Yes'
for i in range(n):
    t,x,y=map(int,input().split())
    if abs(s-X)+abs(y-Y)>t-T or t%2!=(x+y)%2:
        a='No'
        break
    T,X,Y=t,x,y
print(a)


### FIXED CODE ###

N = int(input())
count = 0
T, X, Y = 0, 0, 0
for i in range(N):
    t, x, y = map(int, input().split())
    if abs(x-X)+abs(y-Y) <= t-T and t % 2 == (x+y) % 2:
        count += 1
    T, X, Y = t, x, y
if count==N:
    print('Yes')
else:
    print('No')
B = int(input(N))
C = int(input(A))
D = B % 500
if D > C:
  print(no)
else:
  print(yes)

### FIXED CODE ###

N=int(input())
A=int(input())

if N % 500 <= A:
  print("Yes")
else:
  print("No")
from fractions import gcd
import math
import numpy as np
N = list(map(int, input().split()))
g = gcd(N[0], N[1])
primes = np.ones(g+1)
primes[0:2] = 0
for i in range(2, int(math.sqrt(g))+1+1):
  if primes[i] and i * 2 < g + 1:
    primes[i*2::i] = 0

count = 0
for i in range(2,g+1):
  if primes[i] and g%i == 0:
    count += 1
print(count + 1)


### FIXED CODE ###

from fractions import gcd
import math
import numpy as np
N = list(map(int, input().split()))
g = gcd(N[0], N[1])

def factorize(g):
  factor = []
  for i in range(2, int(np.sqrt(g))+2):
    if g % i != 0:
      continue
    while g % i == 0:
      g //= i
    factor.append(i)
  if g != 1:
    factor.append(g)
  return factor
print(len(factorize(g))+1)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

diff = []
for i in range(M-1):
    diff.append(X[i+1] - X[i])

#print(diff)

if len(diff) == 0:
    print(0)
    exit()

diff.sort()
for i in range(N-1):
    diff.pop()

print(sum(diff))

### FIXED CODE ###


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

if N >= M:
    print(0)
    exit()

diff = []
for i in range(M-1):
    diff.append(X[i+1] - X[i])

#print(diff)

diff.sort()
for i in range(N-1):
    diff.pop()

print(sum(diff))
if __name__ == '__main__':
3    r = int(raw_input())
4
5    print 3*r*r

### FIXED CODE ###

if __name__ == '__main__':
    r = int(raw_input())
    print 3*r*r
n = int(input())
b = list(map(int, input().split()))
ans = 0
ans = b[0] + b[n-2]
for i in range(1, n-1):
  ans += min(b[i], b[i+1])
print(ans)

### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
ans = 0
ans = b[0] + b[n-2]
for i in range(1, n-1):
  ans += min(b[i-1], b[i])
print(ans)
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
import bisect as bi
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        i=abs(i)
        if i>0 : now*=i
        # if i<0 : now*=i
        if i==0 :return 0
        if now>0 : now%=mod
    return now

CH=A[:k]
NO=A[k:]
# G=seki(A[:k])

mod=10**9+7
# if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print((-seki(A[n-k:]))%mod) ;exit()
if n==k and len(A[bi.bisect_left(A,-1):])%2==1 :
    print((-seki(A))%mod) ;exit()
if sum([i<0 for i in A[:k]])%2==0 :
    print(seki(A[:k])%mod) ; exit()
if 0 in CH:
    print(0);exit()
  
# done=0 ; done2=0
# # ch=-73267983297 ; ch2=-9263498381621
# 
# for i in range(k-1,-1,-1):
#     if A[i]<0 and done==0:
#         for j in range(i+1,n):
#             if A[j]>=0: 
#                 # ch=G*A[j]//A[i]
#                 x1=A[j] ; y1=A[i]
#                 done=1
#                 break
#     if A[i]>0 and done2==0:
#         for j in range(i+1,n):
#             if A[j]<=0: 
#                 # ch2=G*A[j]//A[i]
#                 x2=A[j] ; y2=A[i]
#                 done2=1
#                 break
# #     if done==1 and done2==1 : break
# 
# G=seki(A[:k])
# G=-G
# if done and done2 :
#     if x1 * y2 > x2 * y1 :
#         print((G*x1//y1)%mod)
#     else:
#         print((G*x2//y2)%mod)
# elif done==1:
#     print((G*x1//y1)%mod)
# elif done2==1:
#     print((G*x2//y2)%mod)
        

done=0 ; done2=0
muri,muri2=0,0

x1,x2,y1,y2=0,0,0,0
if sum([i<0 for i in NO])==n-k : #NO全部-
    muri=1
if sum([i<0 for i in CH])==k : #CH全部-
    muri2=1
if muri==0:
    y1= [i for i in CH if i<0][-1]
    x1= [i for i in NO if i>0][0]
    done=1
if muri2==0:
    y2= [i for i in CH if i>0][-1]
    x2= [i for i in NO if i<0][0]
    done2=1
    
if done and done2:
    if x1 * y2 > x2 * y1 :
        print((-seki(CH)*x1//y1)%mod)
    else:
        print((-seki(CH)*x2//y2)%mod)
elif muri:
    print((-seki(CH)*x2//y2)%mod)
else:
    print((-seki(CH)*x1//y1)%mod)


### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
mod=10**9+7
ans=1

if K%2==1 and A[-1]<0:
    for i in range(K):
        ans=ans*A[N-(i+1)]%mod
    print(ans)
    exit()

l=0
r=N-1
if K%2==1:
    ans=ans*A[r]
    r-=1

for _ in range(K//2):
    ml=A[l]*A[l+1]
    mr=A[r]*A[r-1]
    if ml>mr:
        ans=ans*ml%mod
        l+=2
    else:
        ans=ans*mr%mod
        r-=2

print(ans)
# -*- coding: utf-8 -*-
 
 
def main(n):
    lst = []
    lst.append(1)
    lst.append(1)
    for i in range(2, n + 1):
        lst[i] = lst[i - 1] + lst[i - 2]
    return lst[n]
 

if __name__ == '__main__': 
    n = int(input())
    print(main(n))

### FIXED CODE ###

# -*- coding: utf-8 -*-


def main(n):
    lst = [1, 1]
    for i in range(2, n + 1):
        lst.append(lst[i - 1] + lst[i - 2])
    return lst[n]


if __name__ == '__main__':
    n = int(input())
    print(main(n))
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [0]*(n)
c = [0]*(m)
bb=0
c[0]=1
for i in range(0,n) :
    bb = ( bb+a[i] ) % m
    c[bb] += 1
    
    
answer = 0
print(c)
for i in range(0,m):
    if c[i] > 1:
        answer +=  (c[i] * (c[i]-1) // 2 )

print(answer)



### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [0]*(n)
c ={0:1}
bb=0
for i in range(0,n) :
    bb = ( bb+a[i] ) % m
    c[bb] = c.get(bb,0) + 1
    
    
answer = 0
#print(c)

for i,j in c.items():
    if j > 1:
        answer +=  (j * (j-1) // 2 )

print(answer)
import bisect
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
A.sort()
B.sort()
if len(set(A)) != N or len(set(B)) != M:
    print(0)
    quit()
ans = 1
mod = 10 ** 9 + 7
for i in reversed(range(1, N * M + 1)):
    ai = bisect.bisect_left(A, i)
    bi = bisect.bisect_left(B, i)
    a_flag = A[ai] == i
    b_flag = B[bi] == i
    if a_flag and b_flag:
        pass
    elif a_flag:
        cand = M - bi
        ans = (ans * cand) % mod
    elif b_flag:
        cand = N - ai
        ans = (ans * cand) % mod
    else:
        cand = (N - ai) * (M - bi) - (N * M - i)
        if cand <= 0:
            print(0)
            quit()
        ans = (ans * cand) % mod
print(ans)


### FIXED CODE ###

import bisect
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
A.sort()
B.sort()
if len(set(A)) != N or len(set(B)) != M:
    print(0)
    quit()
if A[-1] != N * M or B[-1] != N * M:
    print(0)
    quit()
ans = 1
mod = 10 ** 9 + 7
for i in reversed(range(1, N * M + 1)):
    ai = bisect.bisect_left(A, i)
    bi = bisect.bisect_left(B, i)
    a_flag = A[ai] == i
    b_flag = B[bi] == i
    if a_flag and b_flag:
        pass
    elif a_flag:
        cand = M - bi
        ans = (ans * cand) % mod
    elif b_flag:
        cand = N - ai
        ans = (ans * cand) % mod
    else:
        cand = (N - ai) * (M - bi) - (N * M - i)
        if cand <= 0:
            print(0)
            quit()
        ans = (ans * cand) % mod
print(ans)
a,b,c=int(input().split())
print(a*b//2)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(a*b//2)
import math
from functools import reduce

n = int(input())
a = list(map(int, input().split()))

print(reduce(lambda x, y: math.gcd(x, y), a))



### FIXED CODE ###

import fractions
from functools import reduce

n = int(input())
a = list(map(int, input().split()))

#print(reduce((lambda x, y: math.gcd(x, y)), a))
print(reduce((lambda x, y: fractions.gcd(x, y)), a))
A, B, K = map(int,input().split())
  for _ in range(K):
    if A >= 1:
      A -= 1
    elif B >= 1:
      B -= 1
    else:
      break
print(A,B)

### FIXED CODE ###

S,T=input().split()
print(T+S)
import bisect


n, k = map(int, input().split())
xs = list(map(int, input().split()))
index = bisect.bisect_right(xs, -1)

a = xs[:index][::-1]
cost = 0
if xs[index] == 0:
    cost += 1
    b = xs[index + 1:]
else:
    b = xs[index:]

cost_a = [0]
cost_b = [0]
for c in a:
    cost_a.append(abs(c))
for c in b:
    cost_b.append(c)

ret = float('inf')
# if len(a) >= k - cost:
#     ret = min(ret, cost_a[k - cost])
# if len(b) >= k - cost:
#     ret = min(ret, cost_b[k - cost])

for i in range(len(cost_a)):
    if k - i < len(cost_b):
        ret = min(ret, 2 * cost_a[i] + cost_b[k - i])

for i in range(len(cost_b)):
    if k - i < len(cost_a):
        ret = min(ret, 2 * cost_b[i] + cost_a[k - i])
print(ret)


### FIXED CODE ###

import bisect


n, k = map(int, input().split())
xs = list(map(int, input().split()))
index = bisect.bisect_right(xs, -1)

a = xs[:index][::-1]
cost = 0
if index < len(xs) and xs[index] == 0:
    cost += 1
    b = xs[index + 1:]
else:
    b = xs[index:]

cost_a = [0]
cost_b = [0]
for c in a:
    cost_a.append(abs(c))
for c in b:
    cost_b.append(c)

ret = float('inf')
if len(a) >= k - cost:
    ret = min(ret, cost_a[k - cost])
if len(b) >= k - cost:
    ret = min(ret, cost_b[k - cost])

for i in range(len(cost_a)):
    if 0 <= k - i < len(cost_b):
        ret = min(ret, 2 * cost_a[i] + cost_b[k - i])

for i in range(len(cost_b)):
    if 0 <= k - i < len(cost_a):
        ret = min(ret, 2 * cost_b[i] + cost_a[k - i])
print(ret)
from math import log2, ceil
from bisect import bisect_left, bisect_right

N = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = [True for _ in range(N)]

ans = 0
for i in list(range(N))[::-1]:
    if not b[i]: continue
    t = a[i]
    flg = False
    for j in list(range(ceil(log2(t)), int(log2(t * 2)) + 1))[::-1]:
        pair = 2 ** j - t
        left = bisect_left(a, pair)
        right = bisect_right(a, pair)
        # print(t, pair, a, b, left, right)
        if left == right:
            if left < N and left != i:
                if a[left] == pair and b[left]:
                    b[left] = False
                    b[i] = False
                    ans += 1
                    flg = True
                    break
        else:
            k = right - 1
            k = min(right - 1, N - 1)
            while k >= max(0, left):
                if a[k] == pair and b[k] and k != i:
                    b[k] = False
                    b[i] = False
                    ans += 1
                    flg = True
                    break
                k -= 1
            if flg:
                break

print(ans)


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc029/submissions/3804087
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = Counter(a)

ans = 0
for t in a:
    s = (1 << t.bit_length()) - t
    if t == s:
        ans += b[t] // 2
        b[t] %= 2
    else:
        u = min(b[s], b[t])
        ans += u
        b[s] -= u
        b[t] -= u

print(ans)
from collections import defaultdict
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

    def connectedNum(self, x):
        return self.size[self.find(x)]


N, M = map(int, input().split())
Un = UnionFind(M)
D = defaultdict(lambda: [])
for i in range(N):
    _, *L = map(int, input().split())
    for l in L:
        D[l-1].append(i)
for i in range(M):
    if len(D[i]) > 1:
        t = D[i]
        for d in t[1:]:
            Un.union(t[0], d)
if Un.size[Un.find(0)] == N:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

    def connectedNum(self, x):
        return self.size[self.find(x)]


N, M = map(int, input().split())
Un = UnionFind(N)  # 会話できる人をつなげる
D = defaultdict(lambda: [])
for i in range(N):
    _, *L = map(lambda x: int(x)-1, input().split())
    for l in L:
        D[l].append(i)
for i in range(M):
    if len(D[i]) > 1:
        t = D[i]
        for d in t[1:]:
            Un.union(t[0], d)
if Un.size[Un.find(0)] == N:
    print("YES")
else:
    print("NO")