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 uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))
 
    def find(self, x):
        if x == self.par[x]:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
 
    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]


n, m = map(int, input().split())
p = [ int(x) for x in input().split() ]

uf = uf_tree(n+5)

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

ans = 0

for item_id, item in enumerate(p):
    if uf.same(item, item_id+1):
        ans += 1

print(ans)

Solution (Python):
class uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))
 
    def find(self, x):
        if x == self.par[x]:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
 
    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]


n, m = map(int, input().split())
p = [ int(x) for x in input().split() ]


uf = uf_tree(n+5)

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

ans = 0

for item_id, item in enumerate(p):
    if item == item_id + 1:
        ans += 1
    elif uf.same(item, item_id+1):
        ans += 1

print(ans)

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

par = [0]
rank = [0]
def init(n):
    for i in range(n):
        par.append(i+1)
        rank.append(0)

def find(x):
    if par[x]==x:
        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
    elif rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

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

init(n)
for i in range(m):
    unite(x[i][0],x[i][1])

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

Solution (Python):
n,m = map(int,input().split())
p = list(map(int,input().split()))
p = list(enumerate(p,start=1))

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 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_check(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(n)
for m in range(m):
    x,y = map(int,input().split())
    uf.union(x,y)

ans = 0
for now,value in p:
    if uf.same_check(now,value):
        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)
    self.size = [1] * (n+1)
    
  def union(self, a, b):
    para = self.find(a)
    parb = self.find(b)
    if self.rank[para] > self.rank[parb]:
      self.par[para] = parb
    else:
      self.par[parb] = para
      if self.rank[para] == self.rank[parb]:
        self.rank[para] += 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 is_same(self, a, b):
    return self.find(a) == self.find(b)

n, m = [int(item) for item in input().split()]
p = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(m)]
UF = UnionFind(n)

for x, y in xy:
  UF.union(x,y)
  
ans = 0
for i,item in enumerate(p):
  if UF.is_same(item, i+1):
    ans += 1
    
print(ans)

Solution (Python):
import sys
 
n, m = [int(i) for i in input().split(" ")]
p = [0] + [int(i) for i in input().split(" ")]
par = [i for i in range(0, n + 1)]
id_set = [[] for i in range(0, n + 1)]
p_set = [[] for i in range(0, n + 1)]

sys.setrecursionlimit(10**6)
 
def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

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

for i in range(0, m):
    x, y = [int(i) for i in input().split(" ")]
    unite(x, y)

for i in range(1, n + 1):
    r = root(i)
    id_set[r].append(i)
    p_set[r].append(p[i])
    
s = 0
for i in range(1, n + 1):
    if i == root(i):
        id_i = sorted(id_set[i])
        p_i = sorted(p_set[i])
        k = 0
        for j in range(0, len(id_i)):
            while k < len(p_i) and p_i[k] < id_i[j]:
                k += 1
            if k >= len(p_i):
                break
            if p_i[k] == id_i[j]:
                s += 1

print(s)

Solution (Python):
n, m = map(int, input().split())
lst = list(map(int, input().split()))
pair_lst = [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 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)
for pair in pair_lst:
    uf.union(pair[0], pair[1])
    
count = 0
for i in lst:
    if uf.same_check(i, lst[i-1]):
        count += 1
print(count)

Solution (Python):
class Union_Find:
    def __init__(self, N):
        self.N = N
        self.par = [i for i in range(N)]
        self.height = [0 for i in range(N)]
        self.size = [1 for i in range(N)]
    def Find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.Find(self.par[x])
        return self.par[x]
    def Size(self, x):
        return self.size[self.Find(x)]
    def Union(self, x, y):
        x, y = self.Find(x), self.Find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 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()))
uf = Union_Find(N + 1)
for _ in range(M):
    x, y = map(int, input().split())
    uf.Union(x, y)
ans = 0
for i in range(N):
    if uf.Same(p[i], i + 1):
        ans += 1
print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]
        
    def same(self, x, y):
        return self.root(x)==self.root(y)
 
    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        x = self.root(x)
        y = self.root(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
        
uf = UnionFind(N)

for i in range(M):
    x, y = map(int, input().split())
    uf.unite(x - 1, y - 1)
    
cnt = 0
for i in range(N):
    if uf.same(i, P[i] - 1):
        cnt += 1
        
        
print(cnt)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def A():
    return


def B():
    return


def C():
    s = stdin.readline().rstrip()
    K = II() - 1
    ans = []
    for i in range(len(s)):
        for k in range(K+1):
            b = s[i:i + k + 1]
            ans.append(b)
    ans = list(set(ans))
    ans.sort()
    print(ans[K])
    return


def D():
    n, m = LI()
    p = LI_()
    xy = LIR_(m)
    size = [1 for _ in range(n)]
    height = [1 for _ in range(n)]
    par = [i for i in range(n)]
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def union(x, y):
        s1 = find(x)
        s2 = find(y)
        if s1 != s2:
            if height[s1] < height[s2]:
                par[s1] = s2
                size[s2] += size[s1]
                size[s1] = 0
            else:
                par[s2] = s1
                size[s1] += size[s2]
                size[s2] = 0
                if height[s1] == height[s2]:
                    height[s1] += 1

    for x,y in xy:
        union(x, y)
    ans = 0
    for i in range(n):
        if find(p[i]) == find(i):
            ans += 1
    
    print(ans)
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    s = input()
    k = I()
    l = []
    n = len(s)
    alp = list("abcdefghijklmnopqrstuvwxyz")
    for i in alp:
        for j in range(n):
            if s[j] == i:
                l.append(s[j])
                for m in range(j+1,min(j+k,n)):
                    l.append(s[j:m+1])
        l = sorted(list(set(l)))
        if len(l) >= k:break
    print(l[k-1])

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

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

    def unite(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

    n,m = LI()
    p = LI()
    for i in range(n):
        p[i] -= 1
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    for i in range(m):
        x,y = LI()
        if not same(x-1,y-1):
            unite(x-1,y-1)
    for i in range(n):
        root(i)
    g = [[] for i in range(max(par)+1)]
    for i in range(n):
        g[par[i]].append(i)
        g[par[i]].append(p[i])
    ans = 0
    for i in g:
        i.sort()
        d = defaultdict(int)
        for j in i:
            d[j] += 1
            if d[j] == 2:
                ans += 1
    print(ans)

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

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

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

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

def union(x,y):
    if size[x]>size[y]:
        size[x]+=size[y]
        par[y]=find(x)
    elif size[y]>size[x]:
        size[y]+=size[x]
        par[x]=find(y)
    elif size[x]==size[y]:
        size[x]+=size[y]
        par[y]=find(x)
        
for i in range(M):
    a,b=map(int,input().split())
    if find(a)==find(b):
        pass
    else:
        union(find(a),find(b))

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

Solution (Python):
n,m = map(int,input().split())

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

p = [0]+p
pairs = []

for i in range(m):
    pairs.append(tuple(map(int,input().split())))


U = [0]*(n+1)
for i in range(n+1):
    U[i] = i
def find(x):
    global U
    k = x
    while U[k]!=k:
        k = U[k]
    U[x] = k
    return k

def union(x,y):
    global U
    a = find(x)
    b = find(y)
    if a != b:
        U[b] = a
for x,y in pairs:
    union(x,y)
res = 0
for i in range(1,n+1):
    if find(p[i]) == find(i):
        res += 1

print(res)

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

for i in range(N):
    Pi[i] = Pi[i] - 1

T = [i for i in range(N)]

def parent(n):
    if T[n] == n:
        return n
    r = parent(T[n])
    T[n] = r
    return r

for _ in range(M):
    p1, p2 = map(int, input().split())
    p1 -= 1
    p2 -= 1
    pr1 = parent(p1)
    pr2 = parent(p2)
    if pr1 == pr2:
        continue
    T[pr2] = pr1

count = 0
for i in range(N):
    p1 = parent(Pi[i])
    p2 = parent(i)
    if p1 == p2:
        count += 1
print(count)

Solution (Python):
import collections
import itertools
import operator


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


a,b =  map(int, input().split())
l = list(map(int, input().split()))
uf = UnionFind(a)
for i in range(b):
    x,y =map(int, input().split())
    x-=1
    y-=1
    uf.union(x, y)  
ans=0
for i,t in enumerate(l):
    if uf.same(t-1,i):ans+=1

print(ans)

Solution (Python):
class UnionFind:
    """1-index"""

    def __init__(self, n):
        self.parent = [-1] * (n + 1)  

    
    def root(self, A):
        if self.parent[A] < 0:
            return A
        else:
            return self.root(self.parent[A])

    
    def size(self, A):
        return - self.parent[self.root(A)]

    
    def unite(self, A, B):
        A = self.root(A)
        B = self.root(B)

        if A == B:  
            return False

        if self.size(A) < self.size(B):
            A, B = B, A

        self.parent[A] += self.parent[B]  
        self.parent[B] = A

        return True

    
    def same_check(self, A, B):
        return self.root(A) == self.root(B)


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, y)

ans = 0
for i, v in enumerate(p):
    if uf.same_check(i + 1, v):
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, 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)
UF.all_find()


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

print(ans)

Solution (Python):
class UnionFindTree:
    def __init__(self, size: int):
        self.__size = size
        self.__data = [-1] * (size + 1)

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

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

    def find(self, u: int) -> int:
        if self.__data[u] < 0:
            return u
        self.__data[u] = self.find(self.__data[u])
        return self.__data[u]

    def same(self, u: int, v: int) -> bool:
        return self.find(u) == self.find(v)


def equals(N: int, M: int, P: list, XY: list) -> int:
    """例えば xi <-> xj かつ xj <-> xk の場合、xi、xj、xk は
    どの二つも交換可能である。したがって、交換可能なインデックス
    の集合をつくり、そのインデックスの集合とインデックスに対応し
    た P の部分集合との一致する部分が正しい位置における数値群と
    なる。
    """
    uft = UnionFindTree(N)
    for x, y in XY:
        uft.unite(x, y)

    return sum(1 for i, p in enumerate(P) if uft.same(i+1, p))


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    P = [int(s) for s in input().split()]
    XY = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = equals(N, M, P, XY)
    print(ans)

Solution (Python):
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    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 not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

a,b = map(int,input().split())
su = 0
c = list(map(int,input().split()))
uf = UnionFind(a)
for i in range(b):
    n,m = map(int,input().split())
    uf.unite(n,m)

aaa = list(uf.grouper())

for i in range(len(aaa)):
    for j in range(len(aaa[i])):
        if uf.are_same(c[aaa[i][j]-1],aaa[i][j]):
            su += 1

print(su)

Solution (Python):
N,M=map(int,input().split())
P=list(map(int,input().split()))
par=[i for i in range(N)]
ans=0

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

def connect(x,y):
    if root(x)!=root(y):
        par[root(y)]=root(x)

for i in range(M):
    x,y=map(int,input().split())
    connect(x-1,y-1)

for i in range(N):
    if root(i)==root(P[i]-1):
        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)]
rank=[1]*N

ans=0

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

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

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

for i in range(M):
    x,y=map(int,input().split())
    connect(x-1,y-1)

for i in range(N):
    if same(i,P[i]-1):
        ans+=1

print(ans)

Solution (Python):


import sys
 

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

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

  def issame(self, x, y):
    if self.root(x) == self.root(y):
      return True
    else:
      return False
  
  def merge(self, x, y):
    x, y = [self.root(x), self.root(y)]
    if x == y:
      return False
    if self.par[x] > self.par[y]:
      x, y = y, x
    self.par[x] += self.par[y]
    self.par[y] = x
    return True

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

  def out(self):
    return self.par

if __name__ == "__main__":
  n,m = map(int, sys.stdin.readline().rstrip().split())
  p = list(map(int, sys.stdin.readline().rstrip().split()))

  uf = UnionFind(n)
  for i in range(m):
    x,y = list(map(int, sys.stdin.readline().rstrip().split()))
    x, y = x-1, y-1
    if not uf.issame(x,y):
      uf.merge(x,y)

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

Solution (Python):
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*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]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
input=open(0).readline
n,m=map(int,input().split())
*p,=map(int,input().split())
u=UnionFind(n+1)
for _ in range(m):
    u.unite(*map(int,input().split()))
print(sum(u.same(p[i],i+1)for i in range(n)))

Solution (Python):


class UnionFind:
    def __init__(self, n):
        self.nodes = list(range(n))
 
    def root(self, x):
        if (self.nodes[x] == x):
            return x
        self.nodes[x] = self.root(self.nodes[x])
        return self.nodes[x]
    
    def unite(self, x, y):
        if (self.root(x) == self.root(y)):
            return
        self.nodes[self.root(x)] = self.root(self.nodes[y])
        return
    
    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.unite(x-1, y-1)

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

Solution (Python):
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, size):
        self.par = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.sizes = [1 for _ in range(size)]
    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 same(self, x, y):
        return self.root(x) == self.root(y)
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.par[y] = x
            self.sizes[x] += self.sizes[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def size(self, x):
        return self.sizes[self.root(x)]

uf = UnionFind(n)
for x, y in xy:
    uf.unite(x-1, y-1)
mask = [0] * n
for i in range(n):
    mask[i] = uf.root(i)
res = 0
for i in range(n):
    if mask[i] == uf.par[p[i]-1]:
        res += 1
print(res)

Solution (Python):
class UnionFindTree():
    def __init__(self, values=[]):
        self.parent_of = {}
        self.rank_of = {}
        for value in values:
            if value in self.parent_of:
                raise RuntimeError("Dupulicated Value Added")
            self.parent_of[value] = None
            self.rank_of[value] = 0

    def __root(self, value):
        if self.parent_of[value] is None:
            return value
        else:
            self.parent_of[value] = self.__root(self.parent_of[value])
            return self.parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.rank_of[r1] < self.rank_of[r2]:
                self.parent_of[r1] = r2
            else:
                self.parent_of[r2] = r1
                if self.rank_of[r1] == self.rank_of[r2]:
                    self.rank_of[r1] += 1

    def is_same(self, a, b):
        return self.__root(a) == self.__root(b)

    def groups(self):
        groups = {}
        for k in self.parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    P = [x-1 for x in map(int, input().split())]
    uft = UnionFindTree(P)
    for _ in range(M):
        p, q = [x-1 for x in map(int, input().split())]
        uft.unite(P[p], P[q])
    ans = 0
    for i in range(N):
        if uft.is_same(i, P[i]):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)

N, M = map(int, input().split())
p = [0] + list(map(int, input().split()))
x, y = zip(*(map(int, input().split()) for _ in range(M)))
E = [[] for _ in range(N + 1)]
for a, b in zip(x, y):
    E[a].append(b)
    E[b].append(a)
v = [True for _ in range(N + 1)]


def f(i, P, Q):
    v[i] = False
    P.add(i)
    Q.add(p[i])
    for a in E[i]:
        if v[a]:
            f(a, P, Q)


ans = 0
for i in range(1, N + 1):
    if v[i]:
        P = set()
        Q = set()
        f(i, P, Q)
        ans += len(P & Q)
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):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
n, m = map(int, input().split())
p = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(m)]
place = Unionfind(n)
d = {}
for x, y in edges:
    place.union(x-1, y-1)
loot = [0] * n
for i in range(n):
    loot[i] = place.find(i)
    if loot[i] not in d:
        d[loot[i]] = {p[i]-1}
    else:
        d[loot[i]].add(p[i]-1)
counter = 0
for i in range(n):
    if i in d[loot[i]]:
        counter += 1
print(counter)

Solution (Python):
I=lambda:list(map(int,input().split()));n,m=I();p=I();l=[i for i in range(n+1)]
def u(x):
 if l[x]!=x:l[x]=u(l[x])
 return l[x]
for _ in[0]*m:x,y=I();l[u(x)]=u(y)
print(sum(u(i)==u(j)for i,j in enumerate(p,1)))