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

import sys
import bisect


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    b = list(map(int, readline().split()))
    dp = [0] * 31
    for i in range(28, -1, -1):
        mdr = pow(2, i + 1)
        mdl = pow(2, i)
        for j in range(n-1, -1, -1):
            b[j] %= mdr
            a[j] %= mdr
        a.sort(reverse=True)
        b.sort()
        p_mdr_av = 0
        p_mdl_av = 0
        p_mdr = 0
        p_mdl_mdr_av = 0
        for av in a:
            if mdl - av >= 0:
                p_mdr_av = bisect.bisect_left(b, mdr - av, p_mdr_av)
                p_mdl_av = bisect.bisect_left(b, mdl - av, p_mdl_av)
                dp[i] += p_mdr_av - p_mdl_av
            else:
                p_mdr_av = bisect.bisect_left(b, mdr - av, p_mdr_av)
                dp[i] += p_mdr_av
                p_mdr = bisect.bisect_left(b, mdr, p_mdr)
                p_mdl_mdr_av = bisect.bisect_left(b, mdl + mdr - av, p_mdl_mdr_av)
                dp[i] += p_mdr - p_mdl_mdr_av
    t = 0
    for i in range(31):
        t += pow(2, i) * (dp[i] % 2)
    print(t)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import bisect

readline = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
n = int(readline())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))


def f(md):
    pos = n - 1
    res = 0
    for av in a:
        while True:
            if pos != -1 and av + b[pos] >= md:
                pos -= 1
            else:
                res += pos + 1
                break
    return res


def solve():
    dp = [0] * 31
    for i in range(28, -1, -1):
        md = pow(2, i + 1)
        for j in range(n-1, -1, -1):
            b[j] %= md
            a[j] %= md
        a.sort()
        b.sort()
        res1, res2, res3 = f(md // 2), f(md // 2 * 2), f(md // 2 * 3)
        dp[i] += (n - (res1 + res3 - res2)) % 2
    t = 0
    for i in range(31):
        t += pow(2, i) * (dp[i] % 2)
    print(t)


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

n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
    sp[ry]=sp[rx]|sp[ry]
    sp[rx]={}
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(x)]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if root(i)==root(p[i]-1) or i+1==p[i]:
    ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


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


for i in range(M):
    B,C = map(int,input().split())
    
    A.extend([C]*B)
b=sorted(A)
print(sum(b[-N:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    A= list(map(int,input().split()))
    A = sorted(A)

    BC=[list(map(int,input().split())) for i in range(M)]
    BC = sorted(BC, key=lambda x: x[1],reverse=True)
    index=0
    max_index=len(A)
    
    for B,C in BC:
        temp = [C]*B
        for t in temp:
            if max_index>index and  t>A[index]:
                A[index] = t
            else:
                return A
            index+=1
    return A
    
if __name__ == '__main__':
    A=main()
    print(sum(A))
### BUGGY CODE ###

import sys 

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


if N == 1:
    print(A[0])
    sys.exit()

mae = []
usiro = []

#0の時に前 1の時に後ろ
Flag = 0

for i in reversed(range(0,N,1)):
    
    if Flag == 0: # 前の時
        mae.append(str(A[i]))
        mae.append(" ")
        Flag = 1
    else:
        usiro.insert(0,str(A[i]))
        usiro.insert(0,str(" "))
        Flag = 0

moziretu = (mae + usiro)
del moziretu[((len(moziretu))//2)]
moziretu = ''.join(moziretu)
print(moziretu)
  
  




### FIXED CODE ###

import sys 
from collections import deque
N = int(input())
A = list(map(int, input().split()))


if N == 1:
    print(A[0])
    sys.exit()

mae = deque()
usiro = deque()

#0の時に前 1の時に後ろ
Flag = 0

for i in reversed(range(0,N,1)):
    
    if Flag == 0: # 前の時
        mae.append(str(A[i]))
        mae.append(" ")
        Flag = 1
    else:
        usiro.insert(0,str(A[i]))
        usiro.appendleft(" ")
        Flag = 0

moziretu = (mae + usiro)
del moziretu[((len(moziretu))//2)]
moziretu = ''.join(moziretu)
print(moziretu)
### BUGGY CODE ###

N,K=map(int,input().split())
while True:
    if N%K==0:
        print(0)
        break
    elif N<K:
        if N<K/2:
            print(N)
            break
        else:
            print(K-N)
            break
    else:
        N=abs(N-K)

### FIXED CODE ###

N,K=map(int,input().split())
while True:
    if N%K==0:
        print(0)
        break
    elif N<K:
        if N<K/2:
            print(N)
            break
        else:
            print(K-N)
            break
    else:
        N=N%K
### BUGGY CODE ###

def search(x,r):
  low = 0
  high = len(r)-1
  mid = (low+high)//2
  while low<=high:
    rr = r[mid]-x
    ll = r[mid+1]-x
    if rr*ll<=0:
      return(abs(rr),abs(ll))
    elif r[mid]-x > 0:
      high = mid
      mid = (low+high)//2
    else:
      low = mid
      mid = (low+high)//2
      

a, b, q = [int(i) for i in input().split()]
s = []
for i in range(a):
	s.append(int(input()))
t = []
for i in range(b):
	t.append(int(input()))
x = []
for i in range(q):
	x.append(int(input()))

for xx in x:

  s_l = float('inf')
  s_r = float('inf')
  if s[-1] - xx <= 0:
    s_l = abs(s[-1] - xx)
  elif s[0] - xx >= 0:
    s_r = abs(s[0] - xx)
  else:
  	s_l,s_r=search(xx,s)
  
  t_l = float('inf')
  t_r = float('inf')
  if t[-1] - xx <= 0:
    t_l = abs(t[-1] - xx)
  elif t[0] - xx >= 0:
    t_r = abs(t[0] - xx)
  else:
  	t_l,t_r=search(xx,t)
  
  #print(s_l,s_r,t_l,t_r)
  
  #l = max(s_l,t_l)
  #r = max(s_r,t_r)
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    l = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
  

### FIXED CODE ###

from bisect import bisect

a, b, q = [int(i) for i in input().split()]
s = []
for i in range(a):
	s.append(int(input()))
s = [-float('inf')] + s + [float('inf')]
t = []
for i in range(b):
	t.append(int(input()))
t = [-float('inf')] + t + [float('inf')]
x = []
for i in range(q):
	x.append(int(input()))

for xx in x:
  
  s_i = bisect(s,xx)
  s_r = abs(xx - s[s_i])
  s_l = abs(xx - s[s_i-1])
  t_i = bisect(t,xx)
  t_r = abs(xx - t[t_i])
  t_l = abs(xx - t[t_i-1])

  
  #print(s_l,s_r,t_l,t_r)
  
  #l = max(s_l,t_l)
  #r = max(s_r,t_r)
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    l = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
key=[]
for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      s=S[i]+S[j]+S[k]
      if s in key:continue
      else:key.append(s)
print(len(key))

### FIXED CODE ###

N=int(input())
S=input()
i_lis=[]
key=0
for i in range(N-2):
  if S[i] in i_lis:continue
  else:i_lis.append(S[i])
  j_lis=[]
  for j in range(i+1,N-1):
    if S[j] in j_lis:continue
    else:j_lis.append(S[j])
    k_lis=[]
    for k in range(j+1,N):
      if S[k] in k_lis:continue
      else:k_lis.append(S[k]);key+=1
print(key)
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
hlist = np.array(list(map(int, input().split()))).astype(np.int64)
ab = [list(map(int, input().split())) for _ in range(m)]
ab = np.array(ab)
ba = ab[:, ::-1]

ans = 0
for i in range(1, n+1):
  t = np.zeros(n)
  t[ab[ab[:,0] == i, 1] - 1] = 1
  t[ab[ba[:,0] == i, 0] - 1] = 1
  if (t*hlist >= hlist[i-1]).sum() == 0:
    ans += 1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
hlist = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

maxh = [0]*n
for a, b in ab:
  maxh[a-1] = max(maxh[a-1], hlist[b-1])
  maxh[b-1] = max(maxh[b-1], hlist[a-1])
ans = 0
for i in range(n):
  if maxh[i] < hlist[i]:
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())
v = []
d = []
c = []

query = [list(map(int, input().split())) for _ in range(q)]
query = query[::-1]

color = [0] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

for v, d, c in query:
    v -= 1
    dfs(v, 0, d, c, -1)

for co in color:
    print(co)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())

query = [list(map(int, input().split())) for _ in range(q)]

color = [0] * n
depth = [-1] * n

def dfs(node, dist, col, pre_node):
    if dist <= depth[node]:
        return
    depth[node] = dist
    if color[node] == 0:
        color[node] = col
    if dist == 0:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist-1, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, d, c, -1)

for co in color:
    print(co)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
e = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    e[v].append((u,(a,b)))
    e[u].append((v,(a,b)))


def dijkstra(s,cu):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud[cu]:
                d[u] = c + ud[cu]
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
m = 10**15
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    m = min(m,r)

    res[i] = m

x = 10**15
for i in range(n):
    print(x - res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
ans = 0

for i in range(a,b+1):
    if i%c != 0 and i%d != 0:
        ans += 1

print(ans)

### FIXED CODE ###

def gcd(x,y):
    if y==0:
        return x
    else:
        return(gcd(y,x%y))
    
a,b,c,d = map(int,input().split())
g = gcd(c,d)
l = c*d//g

ans =(b-a+1)-( (b//c-(a-1)//c) + (b//d-(a-1)//d) - (b//l-(a-1)//l)  )
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())

flag = True
lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)

### FIXED CODE ###

S = input()
Q = int(input())

lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)
### BUGGY CODE ###

import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
def p2(x): return pow(2,x,mod)
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = map(list,list(zip(*xy)))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  ans += ((p2(lu)-1)*(p2(rd)-1)*(p2(ld+ru))+(p2(ld)-1)*(p2(ru)-1)*(p2(lu+rd))+
  p2(n-1)-(p2(lu)-1)*(p2(rd)-1)*(p2(ld)-1)*(p2(ru)-1))
  ans %= mod
  bit.add(y+1,1)
print(ans)

### FIXED CODE ###

import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
from collections import defaultdict
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
dcy = defaultdict(int)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yls = list(yls)
for i in range(n):
  dcy[yls[i]] = i
yls.sort()
yind = [0 for i in range(n)]
for i in range(n):
  ind = dcy[yls[i]]
  yind[ind] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

A_length = len(A)

a = [A.pop(0)]
print(max(A))

for i in range(A_length-2):
    temp = A.pop(i)
    print(max(max(a), max(A)))
    a.append(temp)

print(max(a))


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

A_max = max(A)
A_second = A_max

if A.count(A_max) == 1:
  AA = []
  for a in A:
    if a != A_max:
      AA.append(a)
  A_second = max(AA)

for i in range(len(A)):
  if A[i] == A_max:
    print(A_second)
  else:
    print(A_max)
### BUGGY CODE ###

n, k = list(map(int, input().split(' ')))
s = list(map(int, list(input())))
pres = []
i = 0
while i < n:
    ka = 0
    while s[i] == s[i+ka]:
        ka += 1
        if ka+i >= n:
            break
    pres.append([s[i],ka])
    i += ka
ia = 0
result = []
while ia < len(pres):
    h = 0
    if pres[ia][0] == 0:
        if ia + 2*k <= len(pres):
            for p in range(2*k):
                h += pres[p+ia][1]
            result.append(h)
        else:
            for p in range(len(pres)-ia):
                h += pres[p+ia][1]
            result.append(h)
            break
    else:
        if ia + 2*k+1 <= len(pres):
            for p in range(2*k+1):
                h += pres[ia+p][1]
            result.append(h)
        else:
            for p in range(len(pres)-ia):
                h += pres[ia+p][1]
            result.append(h)
            break
    ia += 1
print(max(result))

### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(int, list(str(input()))))
c = 0
ran = [0,0]
for i in range(n):
    if s[c] == s[i]:
        ran[-1] += 1
    else:
        ran.append(i+1)
        c = i
result = []
for i in range(1, len(ran)):
    if s[ran[i-1]] == 1:
        result.append(ran[min(i+2*k,len(ran)-1)]-ran[i-1])
    else:
        result.append(ran[min(i+2*k-1, len(ran)-1)]-ran[i-1])
print(max(result))
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
a.append(a[n-1]+1)
l=[0]
for i in range(n):
    if a[i]>=a[i+1]:
        l.sort()
        if l[0]<a[i]:
            l[0]=a[i]
        else:
            l.append(a[i])
    else:
        continue
if l[0]==0:
    print(len(l))
else:
    print(len(l)+1)

### FIXED CODE ###


from collections import deque

n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
l=deque([a[0]])
for i in range(1,n):
    if l[0]>=a[i]:
        l.appendleft(a[i])
    elif l[-1]<a[i]:
        l[-1]=a[i]
    else:
        p=0
        q=len(l)-1
        while q-p!=1:
            if l[(p+q)//2]>=a[i]:
                q=(p+q)//2
            else:
                p=(p+q)//2
        l[p]=a[i]
print(len(l))
### BUGGY CODE ###

from collections import deque


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[INF] * W for _ in range(H)]
# pathD = [[INF] * W for _ in range(H)]
path[x1][y1] = 0
# pathD[x1][y1] = 0

q = deque()
q.append((x1, y1, 0, 0, 0))
D = ((0, 1), (1, 0), (0, -1), (-1, 0))
q_append = q.append
q_appendleft = q.appendleft
while q:
    x, y, d, k, s = q.popleft()
    if k == 0:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] >= s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, nd, K - 1, s + 1))
    else:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] >= ns:
                path[nx][ny] = ns
                nk = k - 1 if d == nd else K - 1
                appendQ = q_appendleft if d == nd else q_append
                appendQ((nx, ny, nd, nk, ns))

ans = -1 if path[x2][y2] == INF else path[x2][y2]
print(ans)


### FIXED CODE ###

from collections import deque


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]

q = deque()
for d in range(4):
    path[x1][y1][d] = (1, 0)
    q.append((x1, y1, d, 1, 0))

D = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while q:
    x, y, d, s, k = q.popleft()
    if k == K:
        for nd in range(4):
            if nd == d:
                dx, dy = D[nd]
                nk = 1
            else:
                dx, dy = 0, 0
                nk = 0
            nx = x + dx; ny = y + dy
            ns = s + 1
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
                path[nx][ny][nd] = (ns, nk)
                q.append((nx, ny, nd, ns, nk))
    else:
        for nd in range(4):
            if nd == d:
                dx, dy = D[nd]
                nk = k + 1
            else:
                dx, dy = 0, 0
                nk = 0
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
                path[nx][ny][nd] = (ns, nk)
                if ns == s:
                    q.appendleft((nx, ny, nd, ns, nk))
                else:
                    q.append((nx, ny, nd, ns, nk))

ans = INF
for d in range(4):
    ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans
print(ans)
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int,input().split())),reverse=True)
count = 0
while True:
    cnt = 0
    ccnt = 0
    done = 0
    for i in range(n):
        if a[i] % 2 == 0:
            if done == 0:
                a[i] = a[i] // 2
                cnt += 1
                done += 1
            else:
                a[i] = a[i] * 3
                ccnt += 1
        else:
            a[i] = a[i] * 3
            ccnt += 1
    if cnt  == 0:
        break
    else:
        count += 1
print(count)  

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
    while a[i] % 2==0:
        a[i] /= 2
        cnt += 1
print(cnt)
### BUGGY CODE ###


N, M = map(int, input().split())
P = [0] + list(map(int, input().split()))
XY = [list(map(int, input().split())) for i in range(M)]

G = [[] for i in range(1 + N)]

for xy in XY:
    G[xy[0]].append(xy[1])
    G[xy[1]].append(xy[0])

searched = []
B = []
F = [0] * (1 + N)
blocknum = -1
for i, g in enumerate(G):
    if i in searched:
        continue
    blocknum += 1  # 何番目のブロックか
    stack = [i]  # 未探索
    searched_small = [i]  # 探索済
    F[i] = blocknum
    while True:
        for j in G[stack.pop()]:
            if j not in searched_small:
                stack.append(j)
                searched_small.append(j)
            F[j] = blocknum

        if len(stack) == 0:
            B.append(searched_small)
            searched.extend(searched_small)
            break

ans = -1
#print(F)
#print(B)
for i, p in enumerate(P):
    if i in [P[b] for b in B[F[i]]]:
        ans += 1

print(ans)

### FIXED CODE ###

# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    uf = Uf(N+1)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.unite(x, y)
    ans = 0
    for i, p in enumerate(P, 1):
        if uf.same(i, p):
            ans += 1
    print(ans)

main()