Problem:
 Score : 400 points    Problem Statement We have a permutation of the integers from 1 through N , p_1 , p_2 , .., p_N .
We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1) , (x_2,y_2) , .., (x_M,y_M) .
AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i ( 1  ≤  i  ≤  N ) such that p_i = i is maximized:   Choose j such that 1  ≤  j  ≤  M , and swap p_{x_j} and p_{y_j} .   Find the maximum possible number of i such that p_i = i after operations.      Constraints  2  ≤  N  ≤  10^5  1  ≤  M  ≤  10^5  p is a permutation of integers from 1 through N .  1  ≤  x_j,y_j  ≤  N  x_j  ≠  y_j  If i  ≠  j , \{x_i,y_i\}  ≠  \{x_j,y_j\} .  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  p_1  p_2  ..  p_N  x_1  y_1  x_2  y_2  :  x_M  y_M       Output Print the maximum possible number of i such that p_i = i after operations.        Sample Input 1 5 2
5 3 1 4 2
1 3
5 4      Sample Output 1 2  If we perform the operation by choosing j=1 , p becomes 1 3 5 4 2 , which is optimal, so the answer is 2 .       Sample Input 2 3 2
3 2 1
1 2
2 3      Sample Output 2 3  If we perform the operation by, for example, choosing j=1 , j=2 , j=1 in this order, p becomes 1 2 3 , which is obviously optimal.
Note that we may choose the same j any number of times.       Sample Input 3 10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9      Sample Output 3 8       Sample Input 4 5 1
1 2 3 4 5
1 5      Sample Output 4 5  We do not have to perform the operation.

Solution (Python):
class UnionFind():
  def __init__(self,size):
    self.table=[-1for _ in range(size)]
  def root(self,x):
    while self.table[x]>=0:
      x=self.table[x]
    return x
  def unite(self,x,y):
    s1=self.root(x)
    s2=self.root(y)
    if s1!=s2:
      if self.table[s1]!=self.table[s2]:
        if self.table[s1]<self.table[s2]:
          self.table[s2]=s1
        else:
          self.table[s1]=s2
      else:
        self.table[s1]-=1
        self.table[s2]=s1
    return
  def same(self,x,y):
    return self.root(x)==self.root(y)
I=lambda:list(map(int,input().split()))
n,m=I()
p=I()
u=UnionFind(n)
for _ in range(m):
  a,b=I()
  u.unite(a-1,b-1)
print(sum(u.same(i,j-1)for i,j in zip(range(n),p)))

Solution (Python):
class UnionFind():
  def __init__(self,size):
    self.table=[-1for _ in range(size)]
  def root(self,x):
    while self.table[x]>=0:
      x=self.table[x]
    return x
  def unite(self,x,y):
    s1=self.root(x)
    s2=self.root(y)
    if s1!=s2:
      if self.table[s1]!=self.table[s2]:
        if self.table[s1]<self.table[s2]:
          self.table[s2]=s1
        else:
          self.table[s1]=s2
      else:
        self.table[s1]-=1
        self.table[s2]=s1
    return
  def same(self,x,y):
    return self.root(x)==self.root(y)
I=lambda:list(map(int,input().split()))
n,m=I()
p=I()
u=UnionFind(n)
for _ in range(m):
  a,b=I()
  u.unite(a-1,b-1)
print(sum(u.same(i,j-1)for i,j in zip(range(n),p)))

Solution (Python):
N, M = map( int, input().split())
P = list( map( int, input().split()))
par = [ i for i in range(N)]
 
def find(x):
    p = par[x]
    if p == x:
        return x
    a = find(p)
    par[x] = a
    return a
 
for i in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    bx, by = find(x), find(y)
    par[y] = bx
    par[by] = bx
 
ans = 0
for i in range(N):
    if find(i) == find(P[i]-1):
        ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
p=[0]+list(map(int,input().split()))
from collections import defaultdict
d=defaultdict(list)
f=defaultdict(int)

for _ in range(M):
    x,y=map(int,input().split())
    d[x].append(y)
    d[y].append(x)
ans=0
for i in range(1,N+1):
    if f[i]==0:
        ind={i}
        val={p[i]}
        que=d[i]
        while len(que)>0:
            tmp=[]
            for q in que:
                if f[q]==0:
                    f[q]=1
                    ind.add(q)
                    val.add(p[q])
                    tmp+=d[q]
            que=tmp
        ans+=len(ind&val)
print(ans)

Solution (Python):
def root(nodes, x):
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = root(nodes, nodes[x])
        return nodes[x]

def unite(nodes, x, y):
    root_x, root_y = root(nodes, x), root(nodes, y)
    if root_x != root_y:
        large_root = min(root_x,root_y)
        small_root = max(root_x,root_y)
        nodes[large_root] += nodes[small_root]
        nodes[small_root] = large_root 

N, M = map(int, input().split())
p = [int(e)-1 for e in input().split()]

nodes = [-1]*N
info = [[int(e)-1 for e in input().split()] for i in range(M)]
for x, y in info:
    unite(nodes, x, y)

group = [[] for i in range(N)]
for i in range(N):
    group[root(nodes,i)].append(i)

def deplications(list1,list2):
    before = len(list1) + len(list2)
    list3 = list(set(list1 + list2))
    after = len(list3)
    return before - after

def make_list(list1):
    list2 = [p[e] for e in list1]
    return list2

ans = 0
for pair in group:
    if pair == []:
        continue
    ans += deplications(pair,make_list(pair))

print(ans)

Solution (Python):

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

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

    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
    def same_check(self,x,y):
        return self.find(x)==self.find(y)

uf=UnionFind(n)
ans=0
for i,j in edges:
    uf.union(i,j)
for i in range(n):
    if uf.same_check(i+1,P[i]):
        ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(N+1)]
rank = [0] * (N+1)
def find(x):
    if par[x] == x:
        return x
    else:
        
        par[x] = find(par[x])
        return par[x]

def same_checker(x, y):
    return find(x) == find(y)

def union(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

for i in range(M):
    x, y = map(int, input().split())
    union(x, y)
S = {}
for i in range(N):
    S[p[i]] = par[i+1]
ans = 0
for i in range(N):
    if same_checker(S[p[i]], S[i+1]):
        ans += 1

print(ans)

Solution (Python):

N,M = map(int, input().split())
p = list(map(int, input().split()))
swappair= [list(map(int, input().split())) for _ in range(M)]

union_list = [-1 for _ in range(N+1)]

def find(a): 
    while not union_list[a] == -1:
        a = union_list[a]
    return a

def merge(a,b): 
    ia = find(a)
    ib = find(b)
    if ia == ib:
        return 
        
    if ia < ib:
        union_list[ib] = ia
    elif ia > ib:
        union_list[ia] = ib
    


def is_same_grp(a,b):
    ia = find(a)
    ib = find(b)
    return ia == ib

for i in range(M):
    merge(*swappair[i])

ans = 0
for i in range(1,N+1):
    ans += int( is_same_grp(i, p[i-1]))

print(ans)

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
P = list(map(int, input().split()))
E = defaultdict(list)

for _ in range(M):
    x, y = map(int, input().split())
    E[x].append(y)
    E[y].append(x)

visited = [False] * (N+1)
connected = []
for i in range(1, N+1):
    if visited[i]:
        continue
    visited[i] = True
    temp = [i]
    stack = [v for v in E[i]]
    while stack:
        v = stack.pop()
        if visited[v]:
            continue
        visited[v] = True
        temp.append(v)
        stack += E[v]
    connected.append(temp)

ans = 0
for cn in connected:
    ans += len(set(cn) & set([P[i-1] for i in cn]))
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n+1)]
        self.rank=[0]*(n+1)

    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
    def same_check(self,x,y):
        return self.find(x)==self.find(y)

n,m=map(int,input().split())
P=list(map(int,input().split()))
UF=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    UF.union(x,y)
count=0
for i in range(n):
    if UF.same_check(i+1,P[i]):
        count+=1
print(count)

Solution (Python):
from collections import defaultdict
class UnionFind():
    def __init__(self, n):
        self.parent = [-1]*n
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def union(self, x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return False
        
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
        return True
    def lists(self):
        d = defaultdict(list)
        for i in range(len(self.parent)):
            parent = self.root(i)
            d[parent].append(i)
        return d

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))
    UF = UnionFind(n)
    for i in range(m):
        x, y = list(map(int, input().split()))
        UF.union(x-1, y-1)
    ans = 0
    for indices in UF.lists().values():
        indices_set = set(indices)
        p_set = set(ps[i]-1  for i in indices)
        ans += len(p_set & indices_set)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
mapp = [[] for _ in range(n + 1)]
for xy in xys:
    mapp[xy[0]].append(xy[1])
    mapp[xy[1]].append(xy[0])

bfs = [0] * (n + 1)
count = 0
for i in range(1, n + 1):
    nexts = mapp[i]
    if not(bfs[i]):
        bfs[i] = i
    for j in nexts:
        if bfs[j]:
            continue
        bfs[j] = i
        nexts += mapp[j]
    if bfs[i] == bfs[p[i - 1]]:
        count += 1
print(count)

Solution (Python):
n, m=map(int, input().split())
p=[0]+list(map(int, input().split()))

par=[i for i in range(n+1)]
cnt=0
def root(i):
    if par[i]==i:
        return i
    else:
        par[i]=root(par[i])
        return par[i]


for i in range(m):
    x, y=map(int, input().split())
    if root(x)==root(y):
        0
        
    else:
        par[root(y)]=root(x)
        

ans=0
for i in range(n):
    n=1+i
    if root(n)==root(p[n]):
        ans=ans+1
print(ans)
'''
print(par[1:])

root_ls=[0]+[root(i+1) for i in range(n)]
print(par[1:])
print(root_ls[1:])
'''

Solution (Python):
class UnionFind:

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

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

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        self.par[rx] = ry

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

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

tree = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    tree.union(x, y)

cnt = 0
for i, p in enumerate(P, 1):
    if tree.same(i, p):
        cnt += 1
print(cnt)

Solution (Python):
def Root(x, cnt):
  cnt += 1
  if L[x] == x:
    return x, cnt
  else:
    return Root(L[x], cnt)

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

Data = []
for i in range(M):
  Data.append(list(map(int, input().split())))

L = [i for i in range(N + 1)]
for i in Data:
  a = Root(i[0], 0)
  b = Root(i[1], 0)
  if a[1] > b[1]:
    L[b[0]] = L[a[0]]
  else:
    L[a[0]] = L[b[0]]
    
Ans = 0
for i in range(N):
  if Root(i + 1, 0)[0] == Root(p[i], 0)[0]:
    Ans += 1
print(Ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
n,m = list(map(int,input().split()))
p = list(map(int,input().split()))
uft = UnionFind(n)

for _ in range(m):
    x,y = map(int, input().split())
    uft.unite(x,y)
count = 0
for i in range(n):
    if uft.same(i+1,p[i]): count += 1
 
print(count)

Solution (Python):

def root(nodes,x):
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = root(nodes,nodes[x])
        return nodes[x]

def unite(nodes,x,y):
    root_x, root_y = root(nodes,x) , root(nodes,y)
    if root_x != root_y:
        nodes[root_x] = root_y

def is_same(nodes,x,y):
    return root(nodes,x) == root(nodes,y)



N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
x_y = [list(map(int,input().split())) for i in range(M)]
nodes = [-1]*(N+1)
cnt = 0

for x,y in x_y:
    unite(nodes,x,y)


for i in range(N):
    if is_same(nodes,i+1,p[i]):cnt += 1

print(cnt)

Solution (Python):
N,M = map(int,input().split())
P = list(map(int,input().split()))
XY = [tuple(map(int,input().split())) for _ in range(M)]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def check(self, x, y):
        return self.find(x) == self.find(y)


A = UnionFind(N)
for (x,y) in XY:
    A.unite(x,y)


ans = 0
for i in range(N):
    if A.check(i+1,P[i]):
        ans += 1

print(ans)

Solution (Python):
n,m = map(int,input().split())
p = list(map(int,input().split()))
info = [list(map(int,input().split())) for _ in range(m)]

par =[i for i in range(n+1)] 
rank=[0]*(n+1)


def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
  

def find(x, y):
  return root(x) == root(y)


def union(x, y):
  x = root(x)
  y = root(y)
  if rank[x] < rank[y]:
    par[x] = y
  else:
    par[y] = x
    if rank[x] == rank[y]:
      rank[x] += 1

for i in range(m):
  union(info[i][0],info[i][1])

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

ans = 0 
for i in range(1,n+1):
  if find(i,a[i]):
    ans += 1
    
print(ans)

Solution (Python):
n, m = map(int, input().split())
p = list(map(lambda x: x-1, map(int, input().split())))

follow = [i for i in range(n)]
num = [1]*n
def root_index_of(x):
    r = x
    while follow[r] != r:
        r = follow[r]
    return r

def connected(x, y):
    return root_index_of(x) == root_index_of(y)

def connect(x, y):
    rx = root_index_of(x)
    ry = root_index_of(y)

    if rx == ry:
        return

    if num[rx] < num[ry]:
        follow[rx] = ry
        follow[x] = ry
        num[ry] += num[rx]
    else:
        follow[ry] = rx
        follow[y] = rx
        num[rx] += num[ry]

for i in range(m):
    x, y = map(lambda x: x-1, map(int, input().split()))
    connect(p[x], p[y])

ans = 0
for i in range(n):
    if connected(i, p[i]):
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
    
    
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    
    def find(self, x):
        while self.table[x] >= 0:
            
            x = self.table[x]
        return x

    
    def union(self, x, y):
        s1 = self.find(x)  
        s2 = self.find(y)
        if s1 != s2:  
            if self.table[s1] != self.table[s2]:  
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                
                
                self.table[s1] += -1
                self.table[s2] = s1
        return


def func(n, m, p, x):
    union = UnionFind(n + 1)
    for _x in x:
        union.union(p[_x[0]], p[_x[1]])
    count = 0
    for i in range(n):
        if union.find(i + 1) == union.find(p[i]):
            count += 1
            
            
    
    return str(count)


n, m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
x = [[0, 0] for _ in range(m)]
for i in range(m):
    x[i] = [int(i) - 1 for i in input().split()]
print(func(n, m, p, x))
"""
print(str(2) + " vs " + func(5, 2, [5, 3, 1, 4, 2], [[0, 2], [4, 3]]))
print(str(3) + " vs " + func(3, 2, [3, 2, 1], [[0, 1], [1, 2]]))
print(str(8) + " vs " + func(10, 8, [5, 3, 6, 8, 7, 10, 9, 1, 2, 4],
                             [[2, 0], [3, 0], [4, 8], [1, 4], [5, 4], [2, 4], [7, 8], [6, 8]]))
print(str(5) + " vs " + func(5, 1, [1, 2, 3, 4, 5], [[0, 4]]))

"""

Solution (Python):


def main():
    na = list(map(int, input().split()))
    N, M = na[0], na[1]
    p = list(map(int, input().split()))
    x_list = [None] * (N + 1)
    y_list = [None] * (N + 1)
    for i in range(M):
        na = list(map(int, input().split()))
        x, y = na[0], na[1]
        if x_list[x] is None:
            x_list[x] = [y]
        else:
            x_list[x].append(y)
        if y_list[y] is None:
            y_list[y] = [x]
        else:
            y_list[y].append(x)

    visited = [False] * (N + 1)
    connections = [None] * (N + 1)
    for i in range(1, N + 1):
        if not visited[i]:
            q = []
            c = set()
            visited[i] = True
            q.append(i)
            while 0 < len(q):
                j = q.pop(0)
                c.add(j)
                if not x_list[j] is None:
                    for k in x_list[j]:
                        if not visited[k]:
                            visited[k] = True
                            q.append(k)
                if not y_list[j] is None:
                    for k in y_list[j]:
                        if not visited[k]:
                            visited[k] = True
                            q.append(k)
            if 1 < len(c):
                connections[i] = c

    cn = 0
    counted = [False] * (N + 1)
    for i in range(1, N + 1):
        if not connections[i] is None:
            c = connections[i]
            for j in c:
                if p[j - 1] in c:
                    cn += 1
                counted[j] = True
    for i in range(1, N + 1):
        if not counted[i]:
            if p[i - 1] == i:
                cn += 1

    print(cn)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N+1)]
        self.rank=[0 for _ in range(N+1)]
    
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    
    def same_check(self,x,y):
        return self.find(x)==self.find(y)
    
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

n,m=map(int,input().split())
s=list(map(int,input().split()))
l=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    l.union(x,y)
cnt=0
for i in range(n):
    if l.same_check(s[i],i+1):
        cnt+=1
print(cnt)

Solution (Python):
N, M = map(int, input().split())
P = list(map(int, input().split()))


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

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

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    UF.union(x, y)

ans = 0
for i, p in enumerate(P):
    ans += UF.same(i, p - 1)

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, M = map(int, input().split())
p_list = list(map(int, input().split()))
union_find = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    union_find.union(x, y)

result = 0
for i in range(N):
    if union_find.check_same(p_list[i], i + 1):
        result += 1
print(result)

Solution (Python):


"""
参考：http://at274.hatenablog.com/entry/2018/02/02/173000
・Union-Find木
"""

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

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

    
    def union(self, x, y):
        
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, M = map(int, input().split())
pN = list(map(int, input().split()))
uf = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    uf.union(x, y)

cnt = 0
for i in range(N):
    if uf.same_check(pN[i], i+1):
        cnt += 1
print(cnt)

Solution (Python):
n, m = map(int, input().split())
a = input().split()
a = [int(m) for m in a]
s = []
for i in range(m):
    s.append([int(m) for m in input().split()])
s.sort(key=lambda x:(x[0], x[1]))
class UnionFind():
    
    
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    
    def find(self,x):
        while self.table[x] >= 0:
            
            x = self.table[x]
        return x

    
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                
                
                self.table[s1] += -1
                self.table[s2] = s1
        return

class UnionFind2(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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


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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


u = UnionFind(n)
for i in range(m):
    u.union(s[i][0] - 1, s[i][1] - 1)
    k = u.table
k = u.table



count = 0
for i in range(n):
    if u.find(i) == u.find(a[i] - 1):
        count += 1
print(count)

Solution (Python):

from collections import deque, defaultdict
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
visited = [False for _ in range(N)]

for x,y in xy:
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

def dfs(v):
    que = deque()
    vis_list = []
    visited[v] = True
    vis_list.append(v)
    que.append(v)
    while len(que) > 0:
        i = que.pop()   
        
        for n in list(graph[i]):
            if visited[n] == False:
                visited[n] = True
                vis_list.append(n)
                que.append(n)

    return vis_list

grps = []
for i in range(N):
    if visited[i] == False:
        grps.append(dfs(i))

ans = 0
for g_list in grps:
    if len(g_list) == 1:
        if g_list[0] == p[g_list[0]]-1:
            ans += 1
    else:
        tmp = set([])
        for i in g_list:
            tmp.add(p[i]-1)
        ans += len( set(g_list) & tmp)

print(ans)

Solution (Python):

from collections import deque, defaultdict
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
visited = [False for _ in range(N)]

for x,y in xy:
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

def dfs(v):
    que = deque()
    vis_list = []
    visited[v] = True
    vis_list.append(v)
    que.append(v)
    while len(que) > 0:
        i = que.pop()   
        
        for n in list(graph[i]):
            if visited[n] == False:
                visited[n] = True
                vis_list.append(n)
                que.append(n)

    return vis_list

grps = []
for i in range(N):
    if visited[i] == False:
        grps.append(dfs(i))

ans = 0
for g_list in grps:
    if len(g_list) == 1:
        if g_list[0] == p[g_list[0]]-1:
            ans += 1
    else:
        tmp = set([])
        for i in g_list:
            tmp.add(p[i]-1)
        ans += len( set(g_list) & tmp)

print(ans)

Solution (Python):
N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]

class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        
T=Unionfind(N)
for m in range(M):
  x,y=map(int,input().split())
  T.unite(x-1,y-1)
ans=0
for i in range(N):
  if T.find(P_list[i]-1)==T.find(i):
    ans+=1
print(ans)

Solution (Python):
N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]

class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
  
  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root
    
  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      self.Tree[s1]=s2
    
T=Unionfind(N)
for m in range(M):
  x,y=map(int,input().split())
  T.unite(x-1,y-1)
ans=0
for i in range(N):
  if T.find(P_list[i]-1)==T.find(i):
    ans+=1
print(ans)

Solution (Python):
N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]
Tree=[i for i in range(N)]
def find(x):
  if x==Tree[x]:
    return x
  else:
    root=find(Tree[x])
    Tree[x]=root
    return root
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1==s2:
    pass
  else:
    Tree[s1]=s2
for m in range(M):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(N):
  if find(P_list[i]-1)==find(i):
    ans+=1
print(ans)

Solution (Python):
def Union(x,y,par):
    x = Find(x,par)
    y = Find(y,par)
    if par[x] < par[y]:
        par[y] = par[x]
    else:
        par[x] = par[y]

def Find(x,par):
    return x if x==par[x] else Find(par[x],par)

n,m=map(int,input().split())
p =list(map(int,input().split()))
par=[i for i in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    Union(x,y,par)
ans = 0
for i in range(n):
    ans += 1 if Find(p[i]-1,par)==Find(i,par) else 0
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.rank = [0]*n
        self.parent = [i for i in range(n)]

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

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            self.rank[y] += 1

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


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

uf = UnionFind(n)

for x, y in info:
    uf.merge(p[x-1]-1, p[y-1]-1)

ans = 0
for i in range(n):
    if uf.same(i, p[i]-1):
        ans += 1

print(ans)