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

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

two_pow = [1 << i for i in range(n + 1)]
is_possible = True
for i in range(n):
    if a[i] > two_pow[i] - 1:
        is_possible = False
        break
if a[n] > two_pow[n]:
    is_possible = False

s = 0
for i in range(n + 1):
    s += a[i] * two_pow[n - i]
if s > two_pow[n]:
    is_possible = False

b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = (a[i] + b[i]) * 2

c = [0] * (n + 1)
c[n] = a[n]
ans = a[n]
for i in reversed(range(n)):
    if (c[i + 1] + 1) // 2 + a[i] + b[i] > two_pow[i]:
        is_possible = False
        break
    c[i] = min(c[i + 1], two_pow[i] - a[i] - b[i]) + a[i]
    ans += c[i]

# print(a)
# print(b)
# print(c)

if is_possible:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

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

is_possible = True
for i in range(n):
    if a[i] > 2**i - 1:
        is_possible = False
        break
if a[n] > 2**n:
    is_possible = False

s = 0
for i in range(n + 1):
    s += a[i] * (2**(n - i))
if s > 2**n:
    is_possible = False

b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = (a[i] + b[i]) * 2

c = [0] * (n + 1)
c[n] = a[n]
ans = a[n]
for i in reversed(range(n)):
    if (c[i + 1] + 1) // 2 + a[i] + b[i] > 2**i:
        is_possible = False
        break
    c[i] = min(c[i + 1], 2**i - a[i] - b[i]) + a[i]
    ans += c[i]

# print(a)
# print(b)
# print(c)

if is_possible:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import collections
s = input()
p = []
for i in range(len(s)):
    p.append(int(s[i:])%2019)

c = collections.Counter(p)
ans = 0
for x , y in c.items():
    ans += y*(y-1)//2
    if x == 0:
        ans += y
print(ans)

### FIXED CODE ###

s = list(input())
p = [0 for i in range(2019)]
n = len(s)
ans = 0
kar = 0
dig = 1
for i in range(n):
    kar = (kar + int(s[n-1-i])*dig)%2019
    dig = (dig*10)%2019
    p[kar] += 1

for i in range(2019):
    ans += p[i]*(p[i]-1)//2
    if i == 0:
        ans += p[i]
print(ans)
### BUGGY CODE ###

X,Y,Z,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()
li=[]
inf = 10**11
for i in range(X):
    for j in range(Y):
        if((i+1)*(j+1)>K): break
        for k in range(Z):
            if((i+1)*(j+1)*(k+1)<=K):
                li.append(A[i]+B[j]+C[k])
li.sort()
li.reverse()
for i in li[:K]:
    print(i)

### FIXED CODE ###

X,Y,Z,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()
li=[]
for i in range(X):
    for j in range(Y):
        if((i+1)*(j+1)>K): break
        for k in range(Z):
            if((i+1)*(j+1)*(k+1)<=K):
                li.append(A[i]+B[j]+C[k])
li.sort()
li.reverse()
for i in li[:K]:
    print(i)
### BUGGY CODE ###

n = int(input())

for i in range(1,int(n**(1/2))+1):
    if n%i!=0:
        continue
    x,y = i,n//i
    a=0
    b=-x
    while 1:
        tmp = a**5-b**5
        if tmp>n:
            if b<0:
                a+=1
                b+=1
                continue
            break
        if tmp==n:
            print(a,b)
            exit()
        a+=1
        b+=1
    a=0
    b=-y
    while 1:
        tmp = a**5-b**5
        if tmp>n:
            if b<0:
                a+=1
                b+=1
                continue
            break
        if tmp==n:
            print(a,b)
            exit()
        a+=1
        b+=1


### FIXED CODE ###

n = int(input())

for a in range(500):
    for b in range(-500,500):
        if a**5-b**5==n:
            print(a,b)
            exit()
### BUGGY CODE ###

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

for i in range(61):
    tmp_1 = 0
    tmp_0 = 0
    for k in range(N):
        if (A[k] >> i) & 1:
            tmp_1 += 1
        else:
            tmp_0 += 1
    ##print(i, tmp_1, tmp_0)
    ans += (tmp_1 * tmp_0) * (2 ** i)
print(ans%mod)

### FIXED CODE ###

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

for i in range(61):
    tmp_1 = 0
    tmp_0 = 0
    for k in range(N):
        if (A[k] >> i) & 1:
            tmp_1 += 1
        else:
            tmp_0 += 1
    ##print(i, tmp_1, tmp_0)
    ans += (tmp_1 * tmp_0) * (2 ** i)
print(ans%mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
assert len(A) == N
total = 0
for i,ai in enumerate(A):
  total += ai * sum(A[i+1:])
print(total % (10 ** 9 + 7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
assert len(A) == N
total = 0
sum_A = sum(A)
for i,ai in enumerate(A):
  sum_A -= ai
  total += ai * sum_A
print(total % (10 ** 9 + 7))
### BUGGY CODE ###

N = int(input())
a = sorted(list(map(int, input().split())))

X = 1
c = 1

for i in range(N - 1):
    a_0 = a[i]
    a_1 = a[i] - 1
    a_2 = a[i] + 1
    j = i
    while True:
        if j == N - 1:
            X = max(X, c)
            c = 1
            break
        b_0 = a[j + 1]
        b_1 = a[j + 1] - 1
        b_2 = a[j + 1] + 1
        b = [b_0, b_1, b_2]
        if a_0 in b or a_1 in b or a_2 in b:
            c += 1
            j += 1
        else:
            X = max(X, c)
            c = 1
            break
print(X)

### FIXED CODE ###

import collections
N = int(input())
a = (list(map(int, input().split())))
for i in range(N):
    a.append(a[i] - 1)
    a.append(a[i] + 1)
c = collections.Counter(a)
print(c.most_common()[0][1])
### BUGGY CODE ###

s, t = input(), input()
for i in range(len(s)):
  if s[i] != t[i]:
    a = s[i]
    b = t[i]
    s = s.translate(str.maketrans({a: b, b: a}))
if s == t:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

s, t = input(), input()
ls, lt = [ [s[0], {0}] ], [ [t[0], {0}] ]

for i in range(len(s)-1):
  if s[i] != s[i+1]:
    b = True
    for j in range(len(ls)):
      if s[i+1] in ls[j][0]:
        ls[j][1].add(i+1)
        b = False
    if b:
      ls.append( [s[i+1], {i+1}] )
      
for i in range(len(t)-1):
  if t[i] != t[i+1]:
    b = True
    for j in range(len(lt)):
      if t[i+1] in lt[j][0]:
        lt[j][1].add(i+1)
        b = False
    if b:
      lt.append( [t[i+1], {i+1}] )

if len(ls) != len(lt):
  print("No")
else:
  for i in range(len(ls)):
    if ls[i][1] != lt[i][1]:
      print("No")
      exit()
  print("Yes")
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]
from bisect import bisect_left
# def 二分探索(リスト, 要素)
def index(lst, e):
    # Step 1. bisect_left して
    i = bisect_left(lst, e)
    
    # Step 2. 変な値を ValueError で弾いて
    if i == len(lst):
        return -1
    if lst[i] != e:
        return -1
    # Step 3. 値を返す。
    return i

A=sorted(A)

for i in B:
    j=1
    while j!=-1:
        j=index(A,i[0])
        if not j==-1:
            A[j]=i[1]
        A=sorted(A)
    print(sum(A))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]

dp=[0 for i in range(1,10**6)]
for i in A:
    dp[i]+=1
S=sum(A)
for i in B:
    S+=(i[1]-i[0])*dp[i[0]]
    print(S)
    dp[i[1]]+=dp[i[0]]
    dp[i[0]]=0
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

cum = [0]
for i in range(1, n+1):
    cum.append(cum[i-1] + (p[i-1]+1)/2)

max = sum(p[:k])
idx = 0
for i in range(1, n-k+1):
    if max < sum(p[i:i+k]):
        max = sum(p[i:i+k])
        idx = i

print(cum[idx+k]-cum[idx])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

cum = [0]
for i in range(1, n+1):
    cum.append(cum[i-1] + (p[i-1]+1)/2)

res = 0
for i in range(0, n-k+1):
    val = cum[i+k] - cum[i]
    if res < val:
        res = val

print(res)
### BUGGY CODE ###

K,S = map(int,input().split())
ans = 0
for i in range(K+1) :
    for j in range(K+1) :
        for k in range(K+1) :
            if (i+j+k) == S :
                ans += 1
print(ans)


### FIXED CODE ###

K,S = map(int,input().split())
answer = 0
for i in range(K+1) :
    for j in range(K+1) :
        if (i+j) >= (S-K) and (i+j) <= S :
            answer += 1
print(answer)
### BUGGY CODE ###

P = 10 ** 9 + 7
N = 10 ** 9  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]


def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % P


# def combinations_count(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


if __name__ == '__main__':
    n, a, b = list(map(int, input().split(" ")))
    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)

    total = pow(2, n, P)
    # print(total)
    a_total = cmb(n, a)
    # print(a_total)
    b_total = cmb(n, b)
    print(total - a_total - b_total - 1)

### FIXED CODE ###

from math import factorial
N, A, B = map(int, input().split())
MOD = 10 ** 9 + 7

def calc(n):
    ret = 1
    for i in range(n):
        ret = ret * (N - i) % MOD
    return ret * pow(factorial(n), MOD - 2, MOD) % MOD

print(max(0, (pow(2, N, MOD) - ((calc(A) + calc(B)) % MOD) - 1) % MOD))
### BUGGY CODE ###

"""
解法１：
startとgoalの組み合わせの全探索で調べる。
マス目の数は最大で400なので、組み合わせの数は最大で約160000.
各組み合わせごとにBFSで最短経路を調べるので、400回ループが必要。
なので計算時間としてはO(H^3W^3)

解法２：
ワーシャルフロイドで各ノードから各ノードへの最短経路を求める。
計算量としては、O(H^3W^3となる)。

実装としては解法１のほうが楽そうなのでそちらを使う。
"""

from itertools import combinations
from copy import deepcopy
from collections import deque

H,W = map(int,input().split())
MAP = [list(input()) for _ in range(H)]

nodeList = []
for i in range(H):
    for j in range(W):
        if MAP[i][j] == ".":
            nodeList.append((i,j))

adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0
for start,goal in list(combinations(nodeList,2)):
    copyMAP = deepcopy(MAP)
    que = deque([[start,0]])
    while que:
        node,step = que.popleft()
        if node == goal:
            ans = max(ans,step)
            break
        else:
            i,j = node
            if copyMAP[i][j] == ".":
                copyMAP[i][j] == "#"
                for a,b in adjecents:
                    x = i+a
                    y = j+b
                    if 0<=x<H and 0<=y<W and copyMAP[x][y]==".":
                        que.append([(x,y),step+1])
print(ans)


### FIXED CODE ###

"""
解法１：
startとgoalの組み合わせの全探索で調べる。
マス目の数は最大で400なので、組み合わせの数は最大で約160000.
各組み合わせごとにBFSで最短経路を調べるので、400回ループが必要。
なので計算時間としてはO(H^3W^3)

解法２：
ワーシャルフロイドで各ノードから各ノードへの最短経路を求める。
計算量としては、O(H^3W^3となる)。

解法１だとなんかTLEするので、解法２で行く。
"""

H,W = map(int,input().split())
MAP = [list(input()) for _ in range(H)]
dp = [[float("INF")]*(H*W) for _ in range(H*W)]
adjecents = [(1,0),(-1,0),(0,1),(0,-1)]

for i in range(H):
    for j in range(W):
        if MAP[i][j] == ".":
            pointer = i*W + j
            dp[pointer][pointer] = 0
            for a,b in adjecents:
                x = i + a
                y = j + b
                if 0<=x<H and 0<=y<W and MAP[x][y] == ".":
                    pointer2 = x*W + y
                    dp[pointer][pointer2] = 1

for i in range(H*W):
    for j in range(H*W):
        for k in range(H*W):
            dp[j][k] = min(dp[j][k],dp[j][i]+dp[i][k])

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dp[i][j] != float("INF"):
            ans = max(ans,dp[i][j])
print(ans)
### 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)]

DP = [[set() for j in range(w+1)]for i in range(h+1)]
DP[0][0].add((0,0))
for i in range(h+1):
    for j in range(w+1):
        for s,t in DP[i][j]:
            if i < h and j<w:
                q = b[i][j]-a[i][j]
                DP[i+1][j].add((s+q,t))
                DP[i+1][j].add((s,t+q))
                DP[i][j+1].add((s+q,t))
                DP[i][j+1].add((s,t+q))
s = DP[h-1][w] | DP[h][w-1]
ans = float("inf")
for i,j in s:
    ans = min(ans, abs(i-j))

print(ans)

### 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 ###

import fractions
from functools import reduce
from copy import copy


def main():
    N = int(input())
    A = list(map(int, input().split()))
    gcds = []
    for i in range(N):
        if i == 0:
            gcds.append(gcd(*A[i+1:]))
        elif i == N-1:
            gcds.append(gcd(*A[:i]))
        else:
            gcds.append(gcd(gcd(*A[:i]), gcd(*A[i+1:])))
    print(max(gcds))


def gcd(*nums):
    return reduce(fractions.gcd, nums)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd


def main():
    N = int(input())
    A = list(map(int, input().split()))
    left = [0] * N
    right = [0] * N
    for i in range(1, N):
        left[i] = gcd(left[i-1], A[i-1])
        right[-1-i] = gcd(right[-i], A[-i])
    gcds = []
    for i in range(N):
        gcds.append(gcd(left[i], right[i]))
    print(max(gcds))


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

q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(lambda x:max(int(x),3),input().split())

n=max(r)+1
sievebd=n//2-1
sieve=[True]*sievebd
limit=(int((n-1)**.5)-1)//2
for i in range(limit):
    if sieve[i]:
        for j in range(2*i**2+6*i+3,sievebd,2*i+3):
            sieve[j]=False
for i in range((sievebd-1)//2):
    if not sieve[i]:sieve[2*i+1]=False
if len(sieve)>2:
    for i in range(2,sievebd,2):
        sieve[i]=False
for i in range(q):
    print(sum(sieve[(l[i]-3)//2:(r[i]-3)//2+1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n=10**5
sievebd=n//2
sieve=[True]*sievebd
limit=int(n**.5)//2
sieve[0]=0
for i in range(limit):
    if sieve[i]:
        for j in range(2*i*(i+1),sievebd,2*i+1):
            sieve[j]=False
for i in range((sievebd-1)//2,0,-1):
    if not sieve[i]:sieve[2*i]=False
for i in range(3,sievebd,2):sieve[i]=False
for i in range(1,sievebd):sieve[i]+=sieve[i-1]
q=int(input())
l=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    print(sieve[(l[i][1]-1)//2]-sieve[max(0,(l[i][0]-1)//2-1)])
### BUGGY CODE ###

import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=list(sys.stdin.readline().strip())
    S,T=len(s),len(t)
    dp=[['' 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]+s[i]
            if len(dp[i+1][j+1])<len(dp[i+1][j]):dp[i+1][j+1]=dp[i+1][j] 
            if len(dp[i+1][j+1])<len(dp[i][j+1]):dp[i+1][j+1]=dp[i][j+1] 
    print(dp[S][T])
if __name__=='__main__':main()

### FIXED CODE ###

import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=list(sys.stdin.readline().strip())
    S,T=len(s),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])
    res=''
    i,j=S,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:
            res=s[i-1]+res
            i,j=i-1,j-1
    print(res)
if __name__=='__main__':main()
### BUGGY CODE ###

import copy

h, w = list(map(int, input().split()))
black_list = []
for i in range(h):
  for j, val in enumerate(list(input())):
    if val == "#":
      black_list.append([i,j])
max_val = 0
for i in range(h):
  for j in range(w):
    min_val = h*w
    for point in black_list:
      diff = abs(i-point[0]) + abs(j-point[1])
      if diff < min_val:
        min_val = diff
    if max_val < min_val:
      max_val = min_val
print(max_val)

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy
 
def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

#153_E
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
dp = [10 ** 10 for _ in range(h+1)]
dp[0] = 0
for i in range(1, h+1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
print(dp[h])

### FIXED CODE ###

#153_E
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
dp = [10 ** 10 for _ in range(h+1)]
dp[0] = 0
for i in range(1, h+1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
print(dp[h])
### BUGGY CODE ###



class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.size = [1 for i in range(n + 1)]

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

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

    def unite(self, x, y):
        if self.same(x, y):
            return
        xr = self.find(x)
        yr = self.find(y)
        if self.size[xr] > self.size[yr]:
            xr, yr = yr, xr
        self.size[yr] = self.size[xr] + self.size[yr]
        self.par[xr] = yr


def submit():
    n, m = map(int, input().split())
    plist = list(map(int, input().split()))
    
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.unite(x, y)

    groups = {}
    for i in range(1, n + 1):
        r = uf.find(i)
        if r not in groups.keys():
            groups[r] = {i}
        else:
            groups[r].add(i)

    ans = 0
    for group in groups.values():
        for g in group:
            if plist[g - 1] in group:
                ans += 1
    print(ans)


submit()

### FIXED CODE ###



class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.size = [1 for i in range(n + 1)]

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

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

    def unite(self, x, y):
        if self.same(x, y):
            return
        xr = self.find(x)
        yr = self.find(y)
        if self.size[xr] > self.size[yr]:
            xr, yr = yr, xr
        self.size[yr] = self.size[xr] + self.size[yr]
        self.par[xr] = yr


def submit():
    n, m = map(int, input().split())
    plist = list(map(int, input().split()))
    
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.unite(x, y)

    groups = {}
    for i in range(1, n + 1):
        r = uf.find(i)
        if r not in groups.keys():
            groups[r] = {i}
        else:
            groups[r].add(i)

    ans = 0
    for group in groups.values():
        for g in group:
            if plist[g - 1] in group:
                ans += 1
    print(ans)


submit()
### BUGGY CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i, gs in enumerate(Gs):
        count = 0
        for j, s in enumerate(gs):
            if s == '#':
                count = 0
                Gc[i][j] = 0
            else:
                count += 1
                Gc[i][j] = count

    return Gc

Gs1 = np.asarray(S)
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs1, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)


### FIXED CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i in range(w):
        if i == 0:
            Gc[:, i] = Gs[:, i]
        else:
            Gc[:, i] = (Gc[:, i-1] + 1) * Gs[:, i]

    return Gc

Gs1 = np.asarray(S) == "."
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs1, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
data = list(stdin.readline().rstrip().split()[0])

count = 0

for i in range(n):
    s_1 = data[i]
    for j in range(i+1, n):
        if s_1 != data[j]:
            s_2 = data[j]
            for k in range(j+1, n):
                s_3 = data[k]
                if s_1 != s_3 and s_2 != s_3:
                    if (k - j) != (j - i):
                        count += 1

print(count)

### FIXED CODE ###

N = int(input())
S = input()

R_cnt, G_cnt, B_cnt = 0, 0, 0

for i in range(len(S)):
    if S[i] == "R":
        R_cnt += 1
    elif S[i] == "G":
        G_cnt += 1
    else:
        B_cnt += 1

All = R_cnt * G_cnt * B_cnt

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2 * j - i
        if k >= N:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            All -= 1

print(All)
### BUGGY CODE ###

from collections import Counter

n = int(input())
aa = tuple(reversed(sorted(map(int, input().split()))))
cnt = Counter(aa)

ans = 0
for i in range(n):
    if cnt[aa[i]] > 1:
        continue

    f = True
    for j in range(i + 1, n):
        if aa[i] % aa[j] == 0:
            f = False
            break
    if f:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
aa = tuple(sorted(map(int, input().split())))
cnt = Counter(aa)
amax = max(aa)
af = [False] * (amax + 1)

ans = 0
for i in range(n):
    x = aa[i]
    if af[x]:
        continue
    while x <= amax:
        af[x] = True
        x += aa[i]
    if cnt[aa[i]] == 1:
        ans += 1

print(ans)
### BUGGY CODE ###

import fractions
n=int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

count=0
for i in range(n):
  count+=(ans//a[i])
print(count%(10**9+7))
  


### FIXED CODE ###

import fractions
n=int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

count=0
for i in range(n):
  count+=(ans//a[i])
print(count%(10**9+7))