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):
N, M = map(int,input().split())
p = list(map(int,input().split()))

def find(x, U):
  if x == U[x]:
    return x
  else:
    k = find(U[x], U)
    U[x] = k
    return k

U = [i for i in range(N)]
for _ in range(M):
  x, y = map(int,input().split())
  x -= 1
  y -= 1
  a = find(p[x]-1, U)
  b = find(p[y]-1, U)
  U[a] = b
  
for i in range(N):
  find(i, U)

ans = 0
for i in range(N):
  if U[i] == U[p[i]-1]:
    ans += 1
   
print(ans)

Solution (Python):
n, m = map(int, input().split())
p = [int(x) - 1 for x in input().split()]

class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1] * n
 
    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
 
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u == v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u 
        self.size[v] += self.size[u]
        self._par[u] = v
 
    def is_connected(self, u, v):
        return self.root(u) == self.root(v)

uf = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x-1, y-1)

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

print(ans)

Solution (Python):

import sys


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uf = UnionFind(N)
    for xx, yy in zip(x, y):
        uf.union(xx-1, yy-1)
    ans = 0
    for members in uf.all_group_members().values():
        s = {p[m]-1 for m in members}
        ans += sum(m in s for m in members)
    return ans


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        res = {}
        for i in range(self.n):
            r = self.find(i)
            if r not in res:
                res[r] = []
            res[r].append(i)
        return res
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    p = [int(next(tokens)) for _ in range(N)]  
    x = [int()] * (M)  
    y = [int()] * (M)  
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(solve(N, M, p, x, y))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
import sys
readline = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M = map(int, readline().rstrip().split())
    P = list(map(int, readline().rstrip().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, readline().rstrip().split())
        uf.union(x-1, y-1)
    
    res = 0
    for i, p in enumerate(P):
        if uf.same(p - 1, i):
            res += 1
    
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = [int(i) for i in input().split()]
uf = UnionFind(n)

p = [int(i) for i in input().split()]
for i in range(m):
    x, y = [int(j) for j in input().split()]
    uf.union(x-1, y-1)

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

print(count)

Solution (Python):


import math



from collections import deque
from collections import Counter




class UnionFind(): 
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,x):
        if self.par[x] <0: 
            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.par[x]>self.par[y]: 
            x,y=y,x
        self.par[x]+=self.par[y] 
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] 
    
    def same(self,x,y): 
        return self.find(x)==self.find(y)

    def member(self,x): 
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root ]
    
    def roots(self): 
        return [i for i , x in enumerate(self.par) if x<0]
    
    def group_count(self): 
        return len(self.roots())

    def all_member(self): 
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

n,m=map(int,input().split())
p=list(map(int,input().split()))
tree=UnionFind(n)
for i in range(m):
  x,y=map(int,input().split())
  tree.union(x-1,y-1)
ans=0
for i in range(n):
  if tree.same(p[i]-1,i):
    ans+=1
print(ans)

Solution (Python):
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

    
N,M = map(int,input().split())
P = list(map(int,input().split()))
uf = UnionFind(N)
for i in range(M):
    x,y = map(int,input().split())
    x-=1;y-=1
    uf.union(x,y)
ans = 0
for i in range(N):
    now = P[i]-1
    loc = i
    if uf.is_same(now,loc):
        ans += 1
print(ans)

Solution (Python):
import sys
from collections import defaultdict, deque
import math


from bisect import bisect_left, bisect_right





input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

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)

    def update(self):
        for i in range(len(self.par)):
            self.par[i] = self.find(i)

def solve():
    n,m = getList()
    nums = getList()
    uf = UnionFind(n)
    for i in range(m):
        x, y = getList()
        uf.union(x, y)
    uf.update()
    st1 = [[] for i in range(n + 1)]
    st2 = [[] for i in range(n + 1)]
    for i in range(n):
        st1[uf.par[i+1]].append(i+1)
        st2[uf.par[i+1]].append(nums[i])

    ans = 0
    for s1, s2 in zip(st1, st2):
        ans += len(list(set(s1) & set(s2)))



    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    
    solve()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=UnionFind(n+1)
for i in range(m):
  x,y=map(int,input().split())
  uf.union(p[x-1],p[y-1])
ans=0
for i in range(1,n+1):
  if uf.same(i,p[i-1]):
    ans+=1
print(ans)

Solution (Python):



class UnionFind():
    
    
    
    def __init__(self, n):
        self.n = n
        
        
        
        self.root = [-1]*(n+1)
        
        
        self.rnk = [0]*(n+1)

    
    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return
        
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        
        
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    

N,M=map(int,input().split())
p=list(map(int,input().split()))
x=[0]*M
y=[0]*M
UN=UnionFind(N)
for i in range(M):
    x[i],y[i]= map(int,input().split())
    UN.Unite(x[i],y[i])
    
cnt=0
for i in range(N):
    
    if UN.isSameGroup(i+1,p[i]):
        
        cnt +=1
print(cnt)

Solution (Python):
import sys


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


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


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

    
    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 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[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

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

    
    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    
    def get_n_groups(self):
        return len(self.get_parent_list())

    
    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    
    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    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.unite(x - 1, y - 1)

    cnt = 0
    for i in range(N):
        a = P[i] - 1
        if UF.check(i, a):
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

(n, m), p, *q = [list(map(int, o.split())) for o in open(0)]
UF = UnionFind(-~n)
for a, b in q:UF.union(a, b)
print(sum(UF.same(p[i], -~i) for i in range(n)))

Solution (Python):
n,m=map(int,input().split())
p=list(map(int,input().split()))
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(n,1)

for i in range(m):
    uf.unite(*map(int,input().split()))
print(len(tuple(1 for i in range(n) if uf.same(i+1,p[i]))))

Solution (Python):
from collections import deque
n,m = map(int,input().split())
p = list(map(int,input().split()))
route = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
visit = [False for i in range(n+1)]
atumari = []
for i in range(1,n+1):
    if visit[i]:
        continue
    visit[i] = True
    kar = set([i])
    d = deque()
    d.append(i)
    while d:
        now = d.popleft()
        for j in route[now]:
            if not visit[j]:
                visit[j] = True
                kar.add(j)
                d.append(j)
    atumari.append(kar)
ans = 0
for i in range(len(atumari)):
    for j in atumari[i]:
        if p[j-1] in atumari[i]:
            ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True

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

    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    pdic = {e :0 for e in range(n)}
    for i, pe in enumerate(p):
        pdic[pe] = i

    par = [-1] * n
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x-1, y-1)

    r = 0
    for i1 in range(n):
        r += same(i1, pdic[i1+1])
    print(r)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
  x,y=map(int,input().split())
  uf.union(x-1,y-1)
yes=[0]*n
for i in range(n):
  if uf.same(p[i]-1,i):
    yes[p[i]-1]=1
print(sum(yes))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


n, m = map(int, input().split())
p = list(map(int, input().split()))


uf = UnionFind(n)
union = uf.union
find = uf.find


for _ in range(m):
    x, y = map(int, input().split())
    union(x - 1, y - 1)

ans = 0
for i, x in enumerate(p):
    if find(i) == find(x - 1):
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
N,M=map(int,input().split())
P=list(map(int,input().split()))
G=[[] for _ in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    G[x].append(y)
    G[y].append(x)

chk=[0 for _ in range(N)]

for i in range(N):
    if P[i]==(i+1):
        chk[i]=1

def uni(v,G,cnt,C):
    C[v]=cnt
    for tmp in G[v]:
        if C[tmp]!=0:
            continue
        uni(tmp,G,cnt,C)

C=[0 for _ in range(N)]
cnt=1
ans=0
for i in range(N):
    if C[i]!=0:
        continue
    uni(i,G,cnt,C)
    cnt+=1

for i in range(N):
    p=P[i]
    if chk[p-1]:
        ans+=1
        continue
    else:
        num=i
        val=p
        if C[i]==C[p-1]:
            ans+=1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        
        
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
 
 
if __name__ == '__main__':
    n,m=map(int,input().split())
    p=list(map(int,input().split()))
    g=UnionFind(n+1)
    for i in range(m):
        x,y=map(int,input().split())
        g.union(x,y)
    cnt=0
    l=[]*n
    for i,j in enumerate(p):
        if g.table[j]==-1:
            if i+1==j:
                cnt+=1
        else:
            if g.find(i+1,j):
                cnt+=1
    print(cnt)

Solution (Python):
inf = 10**18
mod = 10**9+7

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int, input().split())
p = list(map(int, input().split()))
uf = UnionFind(n)
for i in range(m):
    x,y = map(int, input().split())
    uf.union(x-1, y-1)
ans=0
for i,num in enumerate(p):
    if uf.same(i,num-1):
        ans+=1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
p = list(map(int, input().split()))
union_find = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)
res = 0
groups = {}
for i in range(n):
    x = union_find.find(i)
    if x not in groups:
        groups[x] = []
    groups[x].append(i)

for k, v in groups.items():
    idx_set = set(v)
    ps_set = set([p[i]-1 for i in v])
    res += len(idx_set-ps_set)
print(n-res)

Solution (Python):
from collections import deque
n,m,=map(int,input().split())
p=list(map(int,input().split()))
way=[[] for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    way[x].append(y)
    way[y].append(x)
ans=0
top=[False]*n
for i in range(n):
    l=deque([i])
    s=set([])
    t=set([])
    while l:
        now=l.popleft()
        for to in way[now]:
            if top[to]:
                continue
            else:
                top[to]=True
                l.append(to)
                s.add(to)
                t.add(p[to]-1)
    ans+=len(s&t)
cnt=0
for i in range(n):
    if top[i]:
        continue
    else:
        if i+1==p[i]:
            cnt+=1
print(ans+cnt)

Solution (Python):



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


def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]



par = [-1] * n

for _ in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1 , bi - 1
    unite(ai, bi)




count = 0
for i in range(n):
    if same(i, P[i]):
        count += 1

print(count)

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


u = UnionFind(n)
for x, y in xy:
    u.union(x-1, y-1)

cnt = 0
for i, v in enumerate(p):
    if u.same(v-1, i):
        cnt += 1

print(cnt)