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()))
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())
uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.union(x-1,y-1)
ans = 0
for i in range(n):
    if uf.find(i) == uf.find(p[i]-1):
        ans += 1
print(ans)

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):
def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_check(root,x,y):
    if find_root(root,x) == find_root(root,y):
        return True
    else:
        return False
    
def UF_make(graph,n):  
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):  
        Root[i] = find_root(Root,i)
    Root.pop(0)  
    return Root

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

UF=UF_make(XY,N)


groups=[[] for i in range(N+1)]
for i in range(N):
    groups[UF[i]].append(P[i])

for i in range(N+1):
    groups[i].sort()

import bisect
ans=0
for i in range(N):
    num=bisect.bisect_left(groups[UF[i]],i+1)
    if num!=len(groups[UF[i]]) and groups[UF[i]][num]==i+1:
        ans+=1

print(ans)

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix, csgraph
N, M = map(int, input().split())
P = tuple(map(lambda n: int(n) - 1, input().split()))
row, column = zip(*tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(M)))
matrix = csr_matrix((np.ones((M,), dtype=np.int8), (row, column)), dtype=np.int8, shape=(N, N))
connection = csgraph.connected_components(matrix)[1]
print(sum(len(set(connection[list(pair)])) == 1 for pair in enumerate(P)))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 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()))
U=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    U.union(x-1,y-1)
ans=0
for i in range(n):
    if U.same(P[i]-1,i):
        ans+=1
print(ans)

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

def unite(x,y):
  x,y=find(x),find(y)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y] 
    par[y]=x 

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

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

def main():
  global N 
  N, M = map(int, input().split())
  global par 
  par = [-1] * N
  p = list(map(int, input().split()))
  for i in range(M):
    x, y = map(int, input().split())
    unite(x-1, y-1)
  ans = 0
  for i in range(N):
    if same(i, p[i]-1):
      ans += 1
  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
p = LI()
xy = []
for i in range(M):
    x, y = LI()
    x -= 1
    y -= 1
    xy.append((x, y))

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)]

uf = UnionFind(N)
p_dic = {}
for i in range(N):
    p_dic[p[i]] = i


for i in range(M):
    x, y = xy[i]
    uf.Unite(x, y)

ans = 0
for i in range(1, N + 1):
    if uf.isSameGroup(p_dic[i], i - 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 same(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+1)
graph = [[] for _ in range(N)]
can = [[] for _ in range(N)]
xy = list()
for i in range(M):
  x, y = map(int, input().split())
  uf.union(x, y)
ans = 0
for i in range(1, N+1):
  if uf.same(i, P[i-1]):
    ans += 1
print(ans)

Solution (Python):
from sys import setrecursionlimit

class UnionFind:
    def __init__(self, n):
        
        
        self.par = [i for i in range(n + 1)]
        
        self.rank = [0] * (n + 1)
        self.size = [1] * (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 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 x == y:return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self):
        return len({self.find(x) for x in range(1, n + 1)})

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(p[x - 1], p[y - 1])

cnt = 0
for i in range(n):
    check = uf.check(p[i], i + 1)
    if check:cnt += 1
print(cnt)

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=[int(i)-1 for i in input().split()]
tree=UnionFind(n)
for _ 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],i):
        ans+=1
print(ans)

Solution (Python):
import collections

N,M = map(int,(input().split()))
p = list(map(int,(input().split())))
line = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,(input().split()))
    line[a-1].append(b-1)

class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

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

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

Tree = UnionFind(N)
for i in range(N):
    for node in line[i]:
        Tree.union(i,node)

d = [[] for _ in range(N)]
e = [[] for _ in range(N)]
for i in range(N):
    d[Tree.root(i)].append(i)
    d[Tree.root(i)].append(p[i]-1)

ans = 0
for i in range(N):
    ans += len(d[i]) - len(set(d[i]))

print(ans)

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

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

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

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

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

    def is_root(self, x):
        return self.parent[x] < 0

n, m = map(int, input().split())
p = list(map(int, input().split()))
count = 0
pair_list = []
for i in range(m):
    array = list(map(int,input().split()))
    array[0] -=1 ; array[1] -= 1
    pair_list.append(array)

uf = UnionFind(len(p))


for i in range(m):
    uf.unite(pair_list[i][0], pair_list[i][1])


for i in range(n):
    uf.find(i)



for i in range(n):
    if p[i] == i+1:
        count += 1
    else:
        if uf.same(p[i]-1, p[p[i]-1]-1) is True:
            count += 1
        else:
            continue
print(count)

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 same(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+1)
for i in range(M):
    x,y = map(int,input().split())
    uf.union(x,y)
cnt = 0
for i in range(1,N+1):
    if uf.same(i,p[i-1]):
        cnt += 1
print(cnt)

Solution (Python):
from sys import setrecursionlimit

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

    def count_group(self):
        return len({self.find(x) for x in range(n)})

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)


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

Solution (Python):
n,m = map(int,input().split())
p_list = list(map(int,input().split()))
x_y_list = []
for i in range(m):
  x_y_list.append(list(map(int,input().split())))
  
class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            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

        self.parents[y] = x
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
U = UnionFindPathCompression(n)

for x_y in x_y_list:
  x = x_y[0] -1
  y = x_y[1] - 1
  U.union(x,y)
  
count = 0
for i in range(n):
  if U.same(i,p_list[i]-1) == True:
    count += 1
    
print(count)

Solution (Python):








def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    p = [num-1 for num in p]
    x, y = [None] * M, [None] * M
    for i in range(M):
        x[i], y[i] = map(int, input().split())
        x[i] -= 1  
        y[i] -= 1  

    edges = {node: [] for node in range(N)}
    for xi, yi in zip(x, y):
        edges[xi].append(yi)
        edges[yi].append(xi)

    ans = 0
    check_node = [None] * N
    for start in range(N):
        if check_node[start] is not None:
            continue

        indexes = []
        numbers = []
        queue = [start]
        queue_i = 0
        while queue_i < len(queue):
            node = queue[queue_i]
            if check_node[node] is not None:
                queue_i += 1
                continue

            check_node[node] = 1
            indexes.append(node)
            numbers.append(p[node])
            
            for edge in edges[node]:
                if check_node[edge] is None:
                    queue.append(edge)
            
            queue_i += 1

        ans += len(set(indexes) & set(numbers))

    return ans


print(main())

Solution (Python):
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
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 main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,M = LMIIS()
    tree = UnionFind(N)
    P = LMIIS()
    for i in range(M):
        x,y = LMIIS()
        tree.union(x-1,y-1)
    ans = 0
    for i in range(N):
        if i+1 == P[i] or tree.find(i) == tree.find(P[i]-1):
            ans += 1
    print(ans)



    

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 same(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 i in range(m):
  a,b = map(int,input().split())
  uf.union(a-1,b-1)

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

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]
    
    def find(self,x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.size(x) < self.size(y):
                x,y =y,x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
    def same(self,x,y):
        return self.find(x) == self.find(y)

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

    def is_roota(self,x):
        return self.parent[x] < 0

n,m =map(int, input().split())
p = list(map(int, input().split()))
count = 0
pair_list = []
for i in range(m):
    array = list(map(int,input().split()))
    array[0] -= 1
    array[1] -= 1  
    pair_list.append(array)

uf = UnionFind(len(p))  


for i in range(m):
    uf.unite(pair_list[i][0], pair_list[i][1])


for i in range(n):
    uf.find(i)





for i in range(n):
    if p[i] == i+1:
        count += 1
    else:
        if uf.same(p[i]-1, p[p[i]-1]-1) is True:
            count += 1
        else:
            continue
print(count)

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

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

    
    def check(self, x, y):
        return self.find(x) == self.find(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.unite(x - 1, y - 1)

ans = 0
for i in range(N):
    if tree.check(i, p[i] - 1):
        ans += 1

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    p=list(map(int1,input().split()))
    class UnionFind:
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    
    u=UnionFind(N)
    for _ in range(M):
        x,y=map(int1,input().split())
        u.unite(x,y)
    ans=0
    for i in range(N):
        if u.is_same(i,p[i]):
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

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

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

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

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

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

n,m = map(int,input().split())
l = list(map(int,input().split()))
u = Unionfind(n)
for i in range(m):
    x,y = map(int,input().split())
    u.union(x-1,y-1)

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

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

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

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

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

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

n,m = map(int,input().split())
l = list(map(int,input().split()))
u = Unionfind(n)
for i in range(m):
    x,y = map(int,input().split())
    u.union(x-1,y-1)

l1 = [[] for i in range(n)]
l2 = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    l1[x].append(i)
    l2[x].append(l[i]-1)
ans = 0
for i in range(n):
    a = set(l1[i])
    b = set(l2[i])
    ans += len(a&b)
print(ans)

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

def main():
    n,m = map(int,input().split())
    p = list(map(int,input().split()))
    xy = [list(map(int,input().split())) for _ 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_list = [list() for i in range(n)]
            for i in range(n):
              return_list[self.find(i)].append(i)
            return return_list

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

    uf = UnionFind(n)
    ans = 0
    for x,y in xy:
        uf.union(x-1,y-1)
    for v in uf.all_group_members():
        set1 = set()
        for i in v:
            set1.add(p[i]-1)
        ans += len(set(v)&set1)

    print(ans)

if __name__ == '__main__':
    main()

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

def main():
    n,m = map(int,input().split())
    p = list(map(int,input().split()))
    xy = [list(map(int,input().split())) for _ in range(m)]

    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):
            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:
                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 all_group_members(self):
            return_list = [list() for i in range(n)]
            for i in range(n):
              return_list[self.find(i)].append(i)
            return return_list

    uf = UnionFind(n)
    ans = 0
    for x,y in xy:
        uf.union(x-1,y-1)
    for v in uf.all_group_members():
        set1 = set()
        for i in v:
            set1.add(p[i]-1)
        ans += len(set(v)&set1)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
p=list(map(int,input().split()))
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
    
    def merge(self, a, b):
        if self.issame(a,b):
            return
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
        self.size[pb] += self.size[pa]
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
    
    def issame(self, x, y):
        return self.root(x) == self.root(y)
    
    def getsize(self, x):
        return self.size[self.root(x)]

uf=UnionFind(2*n)
for i in range(n):
    uf.merge(i,p[i]+n-1)
for i in range(m):
    x,y=map(int,input().split())
    x-=1;y-=1
    uf.merge(x,y)
ans=0
for i in range(n):
    ans+=int(uf.issame(i,i+n))
print(ans)