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. 



Sample input:
5 2
5 3 1 4 2
1 3
5 4


Sample output:
2

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
P=list(map(int,input().split()))
XY=[[-1] for i in range(N)]
for i in range(M):
  x,y=map(int,input().split())
  XY[x-1].append(y-1)
  XY[y-1].append(x-1)
def f(i,XY):
  Y=XY[i]
  if Y[0]==-1:
    Y.pop(0)
    _=set(Y)
    _.add(i)
    for y in Y:
      _=_|f(y,XY)
    return _
  else:
    return set()
X=[]
for i in range(N-1):
  a=f(i,XY)
  if a != set():
    X.append(a)
ans=0
for x in X:
  for xx in x:
    if P[xx]-1 in x:
      ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
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 i in range(n)]
  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)
  uf=UnionFind(n)
  for i in range(m):
    uf.union(p[xy[i][0]-1]-1,p[xy[i][1]-1]-1)
  ans=0
  for i in range(n):
    if uf.same(i,p[i]-1):
      ans+=1
  print(ans)
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
p = [i-1 for i in p]
rem = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    rem[x] = False
    rem[y] = False
count = 0
for i in range(N):
    if rem[i] and p[i] == i:
        count += 1
alr = rem.copy()
for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [*xy[i]]
        indlist = [i[0] for i in xy[i]]
        numlist = [i[1] for i in xy[i]]
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.append(num)
            indlist.append(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        for num in numlist:
            if num in indlist:
                count += 1
print(count)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
pa=list(range(n))
def find(u):
  if u!=pa[u]:pa[u]=find(pa[u])
  return pa[u]
for i in range(m):
  a,b=map(int,input().split())
  a=find(a-1)
  b=find(b-1)
  if a!=b:pa[a]=b
c=0
for i in range(n):
  if find(p[i])==find(i):c+=1
print(c)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import bisect
d1=defaultdict(list)
d2=defaultdict(list)
n,m=map(int,input().split())
l=list(map(int,input().split()))
la=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  la[a].append(b)
  la[b].append(a)
lb=[0 for i in range(n+1)]
def dfs(x,y):
  if lb[x]!=0:
    return
  else:
    lb[x]=y
    s=la[x]
    if s==[]:
      pass
    else:
      for i in s:
        dfs(i,y)
c=1
for i in range(1,n+1):
  dfs(i,c)
  c+=1
lc=set(lb)
for i in range(1,n+1):
  d1[lb[i]]+=[i]
  d2[lb[i]]+=[l[i-1]]
ans=0
for i in d1:
  d11=d1[i]
  d12=d2[i]
  for j in d12:
    index=bisect.bisect_right(d11,j)
    if d11[index-1]==j:
      ans+=1
print(ans)

Submission status: Runtime Error

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N, M = map(int,input().split())
P = list(map(int,input().split()))
uf = UnionFind(N)
for i in range(N):
    x, y = map(int,input().split())
    uf.union(x,y)
A = list(uf.all_group_members().values())
a = len(A)
B =[[] for i in range(a)]
import bisect
for i in range(a):
    S = A[i]
    for j in range(len(S)):
        insert_index = bisect.bisect_left(B[i],S[j])
        B[i].insert(insert_index,S[j])
    p = 0
    ans = 0
    for k in range(len(S)):
        if p == 0:
            x = B[i].pop
            p = 1
        if x == S[k]:
            p = 0
    ans += len(S) - len(B[i]) + p
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
n,m=map(int,input().split())
a=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  if a>b:a,b=b,a
  uf.merge(a-1,b-1)
print(sum(1 for i in range(n) if uf.parent[i]==uf.parent[a[i]-1]))

Submission status: Runtime Error

Solution code:
def makeTree(cur):
    if cur in G:
        for x in G[cur]:
            if hist[x]==0:
                T[x] = T[cur]
                hist[x] = 1
                makeTree(x)
N,M = map(int,input().split())
P = list(map(int,input().split()))
P.insert(0,0)
G = {}
for _ in range(M):
    x,y = map(int,input().split())
    if x not in G:
        G[x] = []
    G[x].append(y)
    if y not in G:
        G[y] = []
    G[y].append(x)
T = {}
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if hist[i]==0:
        T[i]=i
        makeTree(i)
C = {c:[] for c in T.values()}
for x in T:
    C[T[x]].append(x)
cnt = 0
for c in C:
    B = [P[i] for i in C[c]]
    cnt += len(set(B) & set(C[c]))
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

n,m = map(int,input().split())
P = list(map(int,input().split()))
R = [list(map(int,input().split())) for i in range(m)]
U = [-1]*n
def root(x):
    if x == U[x-1]:
        return x
    elif U[x-1] == -1:
        return x
    return root(U[x-1])
for r in R:
    if U[r[0]-1]==-1:
        if U[r[1]-1]==-1:
            U[r[0]-1] = r[0]
            U[r[1]-1] = r[0]
        else:
            U[r[0]-1] = U[r[1]-1]
    else:
        if U[r[1]-1]==-1:
            U[r[1]-1] = U[r[0]-1]
        else:
            U[root(r[1])-1] = U[r[0]-1]
count = 0
for i in range(n):
    if root(P[i]) == root(i+1) and U[i] != -1:
        count += 1
    elif U[i] == -1 and P[i]-1 == i:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
P = list(map(int,input().split()))
R = [list(map(int,input().split())) for i in range(m)]
U = [-1]*n
def root(x):
    if x == U[x-1]:
        return x
    if U[x-1] == -1:
        return x
    return root(U[x-1])
for r in R:
    if U[r[0]-1]==-1:
        if U[r[1]-1]==-1:
            U[r[0]-1] = r[0]
            U[r[1]-1] = r[0]
        else:
            U[r[0]-1] = U[r[1]-1]
    else:
        if U[r[1]-1]==-1:
            U[r[1]-1] = U[r[0]-1]
        else:
            U[root(r[1])-1] = U[r[0]-1]
count = 0
for i in range(n):
    if root(P[i]) == root(i+1) and U[i] != -1:
        count += 1
    elif U[i] == -1 and P[i]-1 == i:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
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.par = [i for i in range(n)]

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

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
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.par = [i for i in range(n)]

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

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

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

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

print(ans)

Submission status: Runtime Error

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

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not x==y: # 根が同じでない場合のみ併合する
            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 same_check(self, x, y):
        return self.find(x) == self.find(y) 

def main():
    import sys
    input = sys.stdin.readline
    N,M = map(int,input().split())
    P = list(map(int,input().split()))
    XY = [list(map(int,input().split())) for i in range(M)]
    A = UnionFind(M)
    
    for i in range(M):
        x,y = XY[i]
        A.union(x,y)
        
    ans = 0
    for i in range(M):
        j = i+1
        p = P[i]
        if A.same_check(j,p):
            ans += 1
    print(ans)
    
    
    
main()

Submission status: Runtime Error

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,q=map(int,input().split())
t=UnionFind(n)
for _ in range(q):
  p,a,b=map(int,input().split())
  if p==0:
    t.Unite(a,b)
  elif p==1:
    if t.isSameGroup(a,b):
      print('Yes')
    else:
      print('No')


n,m=map(int,input().split())
arr=list(map(int,input().split()))
t=UnionFind(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  t.Unite(a,b)
ans=0
for i in range(n):
  if arr[i]==(i+1):
    ans+=1
  else:
    if t.isSameGroup((i+1),arr[i]):
      ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split())

#a = [0] * (H*W+1)
a = {}

for i in range(H):
    A = list(map(int, input().split()))
    for j, _ in enumerate(A):
        a[_] = (i+1, j+1)

#table = [0] * (H*W+1)
table = {i:0 for i in range(H*W+1)}

for i in range(D+1, H*W):
    x, y = a[i]
    x_, y_ = a[i-D]
    table[i] = table[i-D] + abs(x - x_) + abs(y - y_)

for i in range(int(input())):
    L, R = map(int, input().split())
    print(table[R] - table[L])

Submission status: Runtime Error

Solution code:
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.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)

u = UnionFind(n)
for i in range(m):
    x = xy[i][0]
    y = xy[i][1]
    u.union(x, y)

idxs = []
for i in range(1, n+1):
    idxs.append(u.find(i))

idx_dict = dict()
keys = []
for i in range(n):
    if idxs[i] not in keys:
        idx_dict[idxs[i]] = [i]
        keys.append(idx[i])
    else:
        idx_dict[idxs[i]].append(i)

counter = 0
for k in keys:
    l = idx_dict[k]
    template = []
    for i in range(len(l)):
        template.append(p[l[i]] - 1)

    counter += len(set(l) & set(template))

print(counter)

Submission status: Runtime Error

Solution code:
line = input().split(" ")
n, m = int(line[0]), int(line[1])

line = input().split(" ")
operations = []
for i in range(m):
	test = input().split(" ")
	operations.append((int(test[0]),int(test[1])))

correct = []
line2 = []
for i in range(len(line)):
	line2.append(int(line[i]))
	correct.append(i+1)

count = 0
for l,c in zip(line2, correct):
	if l == c:
		count += 1

if count == n:
	print(count)
else:
	while j < m:
		for i in range(len(operations)):
			if line2[operations[i][0]-1] == operations[i][1] or line2[operations[i][1]-1] == operations[i][0]:
				temp = line2[operations[i][0]-1] 
				line2[operations[i][0]-1] = line2[operations[i][1]-1]
				line2[operations[i][1]-1] = temp
		m += 1

count = 0
for l,c in zip(line2, correct):
	if l == c:
		count += 1

print(count)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def get_p(ind):
    global parent
    while parent[ind] != ind:
        ind = parent[ind]
    return ind

def get_p2(ind):
    global parent
    if parent[ind] == -1:
        return ind
    else:
        parent[ind] = get_p2(parent[ind])
        return parent[ind]

parent = []

def main():
    global parent

    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [-1 for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        if parent[a] == -1 and parent[b] == -1:
            parent[max(a, b)] = min(a, b)
        elif parent[a] != -1 and parent[b] != -1:
            a_parent = get_p2(a)
            b_parent = get_p2(b)
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)
        elif parent[a] == -1:
            parent[a] = get_p2(b)
        else:
            parent[b] = get_p2(a)

    ans = 0

    for i in range(num + 1):
        if parent[i] == -1:
            parent[i] = i


    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int) == get_p(ind):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def get_p(ind, parent):
    while parent[ind] != ind:
        ind = parent[ind]
    return ind

def get_p2(ind, parent):
    if parent[ind] == -1:
        return ind, parent
    else:
        parent[ind], parent = get_p2(parent[ind], parent)
        return parent[ind], parent

def main():
    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [-1 for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        if parent[a] == -1 and parent[b] == -1:
            parent[max(a, b)] = min(a, b)
        elif parent[a] != -1 and parent[b] != -1:
            a_parent, parent = get_p2(a, parent)
            b_parent, parent = get_p2(b, parent)
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)
        elif parent[a] == -1:
            parent[a], parent = get_p2(b, parent)
        else:
            parent[b], parent = get_p2(a, parent)





    ans = 0

    for i in range(num + 1):
        if parent[i] == -1:
            parent[i] = i


    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int, parent) == get_p(ind, parent):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from typing import Union, List
import sys
from copy import copy

sys.setrecursionlimit(10**5)

# 木の根を返す
def find(x: int, S: List[int]) -> int:
    if S[x] == x:
        return x
    else:
        S[x] = find(S[x], S)
        return S[x]

# xとyが同じ集合に属すかの判定
def same(x: int, y: int, S: List[int]) -> bool:
    return find(x, S) == find(y, S)

# xとyの属する集合を結合
def unite(x: int, y: int, S: List[int]) -> None:
    rx = find(x, S)
    ry = find(y, S)
    if rx == ry:
        return None
    else:
        S[rx] = ry

if __name__ == '__main__':
    [N, M] = [int(i) for i in input().split()]

    S = [int(i) for i in range(N+1)]
    p = [0] + [int(num) for num in input().split()]

    for i in range(M):
        [x, y] = [int(i) for i in input().split()]
        unite(x, y, S)

    score = 0
    for i in range(1, N+1):
        if same(i, p[i], S):
            score += 1
    print(score)

Submission status: Runtime Error

Solution code:
N,M = [int(s) for s in input().split()]
p = [int(s) for s in input().split()]
par = []
counter = 0

for i in range(N):
    par.append(i+1)
    
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

for i in range(M):
    x,y = [int(s) for s in input().split()]
    union(x,y)
    
for i in range(N):
    if same(i+1,p[i]):
        counter += 1

print(counter)

Submission status: Runtime Error

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

class UnionFind():
    def __init__(self, N):
        self.nodes = [i for i in range(N)]

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

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

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

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

ans = 0
for idx, p in enumerate(P):
    if tree.is_same(idx+1, p):
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

#print (N,M,pli,sli)
#print (ue)
#print (dw)
for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  if (1==1):
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    assert ue[_a]==-1
    assert ue[_b]==-1
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, elems):
        self.parent = dict()
        for e in elems:
            self.parent[e] = e

    def root(self, e):
        if self.parent[e] == e:
            return e

        return self.root(self.parent[e])

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

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

        self.parent[self.root(x)] = self.root(y)


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

uf = UnionFind(list(range(n)))

for _ in range(m):
    x, y = map(lambda z: int(z) - 1, input().split())
    uf.unite(p[x], p[y])

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

print(count)

Submission status: Runtime Error

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

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

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

    def unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if self.rank[ru] < self.rank[rv]:
            self.par[ru] = rv
        else:
            self.par[ry] = ru
            if self.rank[ru] == self.rank[rv]:
                self.rank[ru] += 1

    def same(self, u, v):
        return self.root(u) == self.root(v)

uni = Unionfind(N)
for i in range(M):
    x, y = map(int, input().split())
    uni.unite(x, y)

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

print(count)

Submission status: Runtime Error

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

class Unionfind:
    def __init__(self, num):
        self.num = num
        self.par = [int(i) for i in range(num+1)]

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

    def unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru != rv:
            self.par[ru] = rv

    def same(self, u, v):
        return self.root(u) == self.root(v)

uni = Unionfind(N)
for i in range(M):
    x, y = map(int, input().split())
    uni.unite(x, y)

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

print(count)

Submission status: Runtime Error

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

class Unionfind:
    def __init__(self, num):
        self.num = num
        self.par = [int(i) for i in range(num+1)]

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

    def unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru != rv:
            self.par[ru] = rv

    def same(self, u, v):
        return self.root(u) == self.root(v)

uni = Unionfind(N)
for i in range(M):
    x, y = map(int, input().split())
    uni.unite(x, y)

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

print(count)

Submission status: Runtime Error

Solution code:
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 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(i, P[i])
        
print(cnt)

Submission status: Runtime Error

Solution code:
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))
#print(par)
ans=0
for i in range(1,N+1):
    if find(i)==find(p.[i]):
        ans+=1
        #print(i,find(i))
print(ans)

Submission status: Runtime Error

Solution code:
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_check(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)  # (3)
ans=0
for i,t in enumerate(l):
    if uf.same(t-1,l[i]-1):ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

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

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
uf = [i for i in range(n + 1)]

def dfs(x):
    if uf[x] == x:
        return x
    return dfs(uf[x])

for _ in range(m):
    xy = list(map(int, input().split()))
    rx, ry = dfs(xy[0]), dfs(xy[1])
    if rx != ry:
        uf[rx] = ry
count = sum([1 for i in range(n) if p[i] == i + 1 or dfs(i + 1) == dfs(p[i])])
print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
uf = {}

def dfs(cld):
    if cld not in uf:
        return []
    elif uf[cld] < 0:
        return [cld]
    return dfs(uf[cld]) + [cld]

for xy in xys:
    xin = (xy[0] in uf)
    yin = (xy[1] in uf)
    xp = dfs(xy[0])
    yp = dfs(xy[1])
    if xin and yin:
        if uf[xp[0]] == uf[yp[0]]:
            uf[yp[0]] = xp[0]
            uf[xp[0]] -= 1
        elif uf[xp[0]] < uf[yp[0]]:
            uf[xy[1]] = xp[0]
        else:
            uf[xy[0]] = yp[0]
    elif xin:
        uf[xy[1]] = xp[0]
    elif yin:
        uf[xy[0]] = yp[0]
    else:
        uf[xy[0]] = -1
        uf[xy[1]] = xy[0]
count = 0
for i in range(n):
    num = i + 1
    pi = p[i]
    if num == pi or sum(set(dfs(num)) & set(dfs(pi))) > 0:
        count += 1
print(count)