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

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.par=[i for i in range(n)]
    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:
            self.par[x]=y

n, m=map(int, input().split())
p=[int(s)-1 for s in input().split()]
pair=[[int(s)-1 for s in input().split()] for _ in range(m)]

uf=UnionFind(n)
for pi in pair:
    uf.unite(pi[0],pi[1])

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

Solution (Python):
n, m = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(n+1)]
rank = [0]*(n+1)
ans = 0

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

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

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

for i in range(n):
  ans += (find(p[i]) == find(i+1))

print(ans)

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

union = {node:node for node in range(n)}
depth = {node:0 for node in range(n)}

def root(node):
    if union[node] == node:
        return union[node]
    union[node] = root(union[node])
    return union[node]

for x, y in xys:
    a, b = sorted((root(x), root(y)), key=lambda z:depth[z])
    union[a] = b
    depth[b] = max(depth[b], depth[a]+1)

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

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

union = {node:(node, 0) for node in range(n)}

def root(node):
    if union[node][0] == node:
        return union[node]
    union[node] = root(union[node][0])
    return union[node]

def unite(*roots):
    r1, r2 = sorted(roots, key=lambda x:x[1])
    rank = max(r1[1]+1, r2[1])
    r = (r2[0], rank)
    union[r1[0]] = union[r2[0]] = r

for x, y in xys:
    unite(root(x), root(y))

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

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

union = {node:node for node in range(n)}

def root(node):
    if union[node] == node:
        return node
    union[node] = root(union[node])
    return union[node]

for x, y in xys:
    union[root(x)] = root(y)

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

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

nodes = range(n)
union = {node:node for node in nodes}

def root(node):
    if union[node] == node:
        return node
    union[node] = root(union[node])
    return union[node]

for x, y in xys:
    rx = root(x)
    ry = root(y)
    union[rx] = ry

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

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

nodes = range(n)
union = {node:node for node in nodes}

def root(node):
    if union[node] == node:
        return node
    union[node] = root(union[node])
    return union[node]

for x, y in xys:
    rx = root(x)
    ry = root(y)
    union[rx] = ry

groups = {node:{node} for node, rootn in union.items() if node==rootn} 
for node in nodes:
    if node in groups:
        continue
    group = groups[root(node)]
    group.add(node)
    groups[node] = group

print(sum(p in groups[i] for i, p in enumerate(ps)))

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

nodes = range(n)
union = {node:node for node in nodes}

def root(node, previouss=None):
    if not previouss:
        previouss = []

    if union[node] == node:
        for previous in previouss:
            union[previous] = node
        return node
    else:
        previouss.append(node)
        return root(union[node], previouss)

for x, y in xys:
    rx = root(x)
    ry = root(y)
    union[rx] = ry

groups = {node:{node} for node, rootn in union.items() if node==rootn} 
for node in nodes:
    if node in groups:
        continue
    group = groups[root(node)]
    group.add(node)
    groups[node] = group

print(sum(p in groups[i] for i, p in enumerate(ps)))

Solution (Python):
n, m = map(int, input().split())
p = list(map(int, input().split()))
graph = [[] for i in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
group = [0] * (n + 1)
ans = 0

for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if not group[point]:
            group[point] = i
            space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    for i in range(N):
        p[i] -= 1
    x = [0 for _ in range(M)]
    y = [0 for _ in range(M)]
    for i in range(M):
        x[i], y[i] = map(int, input().split())
        x[i] -= 1
        y[i] -= 1

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

    def unite(x,y):
        x = root(x)
        y = root(y)
        if x!=y:
            Parent[x] = y

    Parent = [i for i in range(N)]
    for i in range(M):
        unite(x[i], y[i])

    count = 0
    for i in range(N):
        if root(i)==root(p[i]):
            count += 1

    return count

if __name__ == '__main__':
    print(main())

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

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

    def same_check(self, x, y):

        return self.find(x) == self.find(y)


N, M = map(int, input().split())
*p, = map(int, input().split())
xy = [map(int,input().split()) for _ in range(M)]
result = 0

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

for i in p:
    if union.same_check(p[i-1]-1,i-1):
        result += 1

print(result)

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


n, m = map(int, input().split())
uft = UnionFind(n)
p = list(map(int, input().split()))
rev = {x: i for i, x in enumerate(p)}

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

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

print(ans)

Solution (Python):
class DisjointSet:
    def __init__(self, no):
        self.parent = None
        self.rank = 0
        self.size = 1
        self.no = no

    def getRoot(self):
        if self.parent is None:
            return self
        else:
            self.parent = self.parent.getRoot()
            return self.parent

    def getSize(self):
        return self.getRoot().size

    def union(self, x):
        r = self.getRoot()
        xr = x.getRoot()
        if xr.rank > r.rank:
            r.parent = xr
            xr.size += r.size
        elif xr.rank < r.rank:
            xr.parent = r
            r.size += xr.size
        elif xr != r:
            xr.parent = r
            r.rank += 1
            r.size += xr.size

N, M = map(int, input().split())
V = list(map(int, input().split()))
s = []
for i in range(N):
    s.append(DisjointSet(i+1))

for i in range(M):
    u, v = map(int, input().split())
    s[u-1].union(s[v-1])

dic = {}
for i in range(N):
    gid = s[i].getRoot().no
    if gid not in dic:
        A = set()
        B = set()
        dic[gid] = (A, B)
    else:
        A, B = dic[gid]
    A.add(i+1)
    B.add(V[i])
    

ans = 0
for key in dic.keys():
    aa = len(dic[key][0] & dic[key][1])
    
    ans += aa

print(ans)

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

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

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

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

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

uni =  UnionFind(n+1)
for i in range(m):
    x, y = map(int, input().split())
    uni.union(x, y)

cnt = 0

for i in range(n):
    if uni.same_check(p[i], i + 1):
        cnt += 1
print(cnt)

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

par = [i for i in range(n)]

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

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

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

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n+1)]
group = [0]*(n+1)
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += group[num] == group[i]
print(ans)

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

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


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

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


print(count)

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

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


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

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


print(count)

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

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

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

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

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)

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

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

def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		return
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += rank[x]
		else:
			par[x] = y
			rank[x] += rank[y]
		return

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

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)

Solution (Python):


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

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

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

            return True
        return False


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

s = UnionFind(N)

for i in range(M):
    a, b = map(int, input().split())
    s.union(a-1, b-1)

ans = 0
for i in range(N):
    
    if p[i] == i+1:
        ans += 1
    
    elif s.find(p[i]-1) == s.find(i):
        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.table = [-1 for _ in range(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 unite(self, x, y):
    s1, s2 = self.root(x), self.root(y)
    if s1 != s2:
      if self.table[s1] != self.table[s2]:
        if self.table[s1] < self.table[s2]:
          self.table[s2] = s1
        else:
          self.table[s1] = s2
      else:
        self.table[s1] += -1
        self.table[s2] = s1
    return
  
  def findSet(self, x, y):
    return self.root(x) == self.root(y)
uf = UnionFind(N)
for i in range(M):
  px, py = map(int, input().split())
  px -= 1
  py -= 1
  uf.unite(px, py)
ans = 0
for i, v in enumerate(p):
  if uf.findSet(i,v):
    ans += 1
print(ans)

Solution (Python):

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

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

    def same(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
        self.par[x] = y




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

uf = UnionFind(n);

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


count = 0
for index in range(n):
    start = index + 1
    to = p[index]
    if uf.same(start, to):
        count += 1
print(count)

Solution (Python):
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  rank = [0 for i in range(n)]
  
  def find(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = find(p)
    pare_inds[x] = a
    return a
  
  def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
      return
    if rank[x] < rank[y]:
      pare_inds[x] = y
    else:
      pare_inds[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1

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

  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    unite(x, y)
  
  ans = 0
  for i in range(n):
    if same(i, plst[i] - 1):
      ans += 1

  print(ans)
solve()

Solution (Python):
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  
  def find(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = find(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = find(x), find(y)
    pare_inds[y] = r_x
    pare_inds[r_y] = r_x
  
  ans = 0
  for i in range(n):
    if find(i) == find(plst[i] - 1):
      ans += 1

  print(ans)
solve()

Solution (Python):
N,M = list(map(int,input().strip().split(' ')))
P = list(map(int,input().strip().split(' ')))
X =[]
for i in range(M):
    X.append( list(map(int,input().strip().split(' '))))
    
    
par = [i for i in range(1,N+1)]

def GetRoot(a):
    ind = a-1
    if par[ind]==a:
        return a
    else:
        par[ind] = GetRoot(par[ind])
        return par[ind]

def unite(a,b):
    aRoot,bRoot = GetRoot(a),GetRoot(b)
    if aRoot >= bRoot:
        par[aRoot-1] = bRoot
    else:
        par[bRoot-1] = aRoot
        
for j in X:
    unite(j[0],j[1])

result = 0
for p in P:
    if GetRoot(p) == GetRoot(P[p-1]):
        result = result+1
print(result)

Solution (Python):

class UnionFindSet:
    def __init__(self):
        self.dic = dict()

    def find(self,x):
        
        if x not in self.dic:
            return x
        else:
            self.dic[x] = self.find(self.dic[x])
            return self.dic[x]

    def union(self,x,y):
        fx = self.find(x)
        fy = self.find(y)
        if fx != fy:
            self.dic[fx] = fy

n, m = map(int,input().split())
p = [None] + list(map(int,input().split()))
s = UnionFindSet()

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

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

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

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

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

    
    def subsetall(self):
        a = []
        for i in xrange(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

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

s = UnionFind(N)

for i in range(M):
  a, b = map(int, input().split())
  s.union(a-1,b-1)

ans = 0
for i in range(N):
  if p[i] == i+1: ans +=1
  elif s.find(p[i]-1) == s.find(i): ans+=1
print(ans)

Solution (Python):
def main():
    """
    2 <= N <= 10^5
    1 <= M <= 10^5
    p: 順列

    1 <= xi, yi <= N
    xi != yj
    if i != j then {xi, yi} != {xj, yj}
    """
    N, M = map(int, input().split())
    *p, = map(int, input().split())
    xy = [
        list(map(int, input().split()))
        for _ in range(M)
    ]

    editorial(N, M, p, xy)


class UnionFind:
    def __init__(self, par):
        self.par = par

    def root(self, x):
        if self.par[x] == x:
            return x
        
        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:
            self.par[y] = x


def editorial(N, M, p, xy):
    par = list(range(N+1))
    uf = UnionFind(par)
    for x, y in xy:
        uf.unite(x, y)

    _p = [0] + p
    ans = 0
    for i in range(1, N+1):
        if uf.root(i) == uf.root(_p[i]):
            ans += 1

    print(ans)


def f(N, M, p, xy):
    """
    (1, 2): 1,2を入れ替える
    (2, 3): 2,3を入れ替える
        default: 123
            1,2: 213
            2,3: 231
        defaultからの移動: (1,3), (1,2)
        (1,2),(2,3) -> (1,3),(1,2)
        入れ替えると2番目xが1番目xになる？

    入力例1より、j=1,2,1の順で入れ替え
        j1=(1,2),j2=(2,3) => (1,3)
    """
    d_xy = {x: y for x, y in xy}
    d_yx = {y: x for x, y in xy}
    extra = []
    for x, y in xy:
        if y in d_xy:
            extra.append((x, d_xy[y]))

    print(xy)
    print("---")
    print(extra)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFindSet:
    def __init__(self):
        self.dic = dict()

    def find(self, x):
        if x not in self.dic:
            return x
        else:
            self.dic[x] = self.find(self.dic[x])
            return self.dic[x]

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx != fy:
            self.dic[fx] = fy

n, m = map(int, input().split())
p = [None] + list(map(int, input().split()))
s = UnionFindSet()
for _ in range(m):
    x, y = map(int, input().split())
    s.union(p[x], p[y])
ans =0
for i in range(n, 0, -1):
    if s.find(i) == s.find(p[i]):
        ans += 1
print(ans)

Solution (Python):





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



def union(x, y):
    s1 = find(x)
    s2 = find(y)
    if s1 != s2:
        if link[s1] >= link[s2]:
            
            link[s2] += link[s1]
            link[s1] = s2
        else:
            link[s1] += link[s2]
            link[s2] = s1
        return True
    return False


N, M = map(int, input().split())
p = list(map(int, input().split()))
link = [-1 for _ in range(N + 1)]

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

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

Solution (Python):





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



def union(x, y):
    s1 = find(x)
    s2 = find(y)
    if s1 != s2:
        if link[s1] >= link[s2]:
            
            link[s1] += link[s2]
            link[s2] = s1
        else:
            link[s2] += link[s1]
            link[s1] = s2
        return True
    return False


N, M = map(int, input().split())
p = list(map(int, input().split()))
link = [-1 for _ in range(N + 1)]

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

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

Solution (Python):
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n+1)]
group = [0]*(n+1)
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += group[num] == group[i]
print(ans)

Solution (Python):
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n+1)]
group = [0]*(n+1)
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p,1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += group[num] == group[i]
print(ans)

Solution (Python):
N, M = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if not group[point]:
            group[point] = i
            space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Solution (Python):
N, M = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = (int(i) for i in input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

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

graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

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

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

graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

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

def root(val):
    if parent[val]==val:
        return val
    else:
        parent[val]=root(parent[val])
        return parent[val]

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

def unite(x,y):
    xr=root(x)
    yr=root(y)
    if xr==yr :return
    parent[xr]=yr
p=list(map(int, input().split()))
X=[]
Y=[]
for i in range(M):
    x,y=map(int, input().split())
    X.append(x)
    Y.append(y)
    unite(x-1,y-1)
ct=0
for i,pp in enumerate(p):
    ct+=same(i,pp-1)
print(ct)

Solution (Python):
n,m = (int(i) for i in input().split())
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
for i,j in x: unite(i,j)
ans = -1
for i,j in enumerate([0]+p):
	if root(i)==root(j): ans += 1
print(ans)

Solution (Python):
from collections import deque


n,m = map(int,input().split())
p = list(map(int,input().split()))
links = {}
checked = set()
for i in range(n):
    links[i] = set()
for i in range(m):
    x,y = map(int,input().split())
    v=x-1
    w=y-1
    links[v].add(w)
    links[w].add(v)
queue = deque()
ans = 0

for start in range(n):
    if start in checked:
        continue

    v = start
    queue.appendleft(v)
    checked.add(v)

    cluster = set()
    cluster.add(v)
    values = set()
    values.add(p[v]-1)

    while queue:
        v = queue.pop()
        neighbors = links[v]
        for w in neighbors:
            if w in checked:
                continue
            else:
                queue.appendleft(w)
                checked.add(w)
                cluster.add(w)
                values.add(p[w]-1)

    common = len (cluster & values)
    ans += common

print(ans)

Solution (Python):
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  belongs = [[] for i in range(n)]
  
  def get_root(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = get_root(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = get_root(x), get_root(y)
    if r_x < r_y:
      pare_inds[y] = r_x
      pare_inds[r_y] = r_x
    else:
      pare_inds[x] = r_y
      pare_inds[r_x] = r_y
  
  for i in range(n):
    belongs[get_root(i)].append(i)

  ans = 0

  for lst in belongs:
    lst2 = [plst[i] - 1 for i in lst]
    set1 = set(lst)
    set2 = set(lst2)
    ans += len(set1 & set2)














  
  print(ans)
solve()