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: Wrong Answer

Solution code:
def root(i):
  if par[i] == i:
    return i
  par[i] = root(par[i])
  return par[i]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[ry] = rx

def same(x, y):
  return par[x] == par[y]

n,m = map(int, input().split(" "))
p = [0] + list(map(int, input().split(" ")))
a = [(list(map(int, input().split(" ")))) for i in range(m)]
par = list(range(n + 1))
count = 0
for i, j in a:
  union(i, j)
  #print(par)
#print(p)
for i in range(1, n + 1):
  if same(root(p[par[i]]), root(par[i])):
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
def root(i):
  #print(i)
  if par[i] == i:
    return i
  par[i] = root(par[i])
  return par[i]

def union(x, y, n):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    #print(x, y, rx, ry, par)
    par[ry] = rx
    for i in range(n):
      if par[i] == ry:
        par[i] = rx

def same(x, y):
  return par[x] == par[y]

n,m = map(int, input().split(" "))
p = [0] + list(map(int, input().split(" ")))
a = [(list(map(int, input().split(" ")))) for i in range(m)]
par = list(range(n + 1))
count = 0
for i, j in a:
  union(i, j, n)
  #print(par)
#print(p)
for i in range(1, n + 1):
  if same(p[par[i]], par[i]):
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    P = []
    for p in mi():
        P.append(p-1)

    X = [[] for _ in range(N)]
    for i in range(M):
        x,y = mi()
        X[x-1].append(y-1)
        X[y-1].append(x-1)
    
    def search(x,y): # x → y が存在するか探す
        stack = deque([(x,[x],set([x]))])
        while stack:
            current, history, seen = stack.popleft()
            if current == y: break

            for next in X[current]:
                if next in seen: continue
                stack.append((next,history+[next], seen|set([next])))
        
        if current == y: return history
        else: return []
            

    def swap(i,j):
        p = P[i]
        P[i] = P[j]
        P[j] = p
        

    ans = 0
    for i in range(N):
        while P[i] != i:
            path = search(i,P[i])
            if len(path) <= 1: break 
            for j in range(len(path)-1):
                swap(path[j], path[j+1])

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

    print(ans)

        



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

D = uf.all_group_members()

ans = []

for L in D.values():
  temp = set()
  for i in L:
    temp.add(p[i]-1)

Submission status: Wrong Answer

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 _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
par=[i for i in range(n)]
 
def find(x):
  if par[x]==x:
    return par[x]
  else:
    par[x]=find(par[x])
    return par[x]
 
def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy
 
f=lambda x:int(x)-1
for mm in range(m):
  x,y=map(f,input().split())
  union(x,y)
 
ans=0
for i in range(n):
  if find(p[i]-1)==i:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
f=lambda x:int(x)-1
p=list(map(f,input().split()))
par=[j for j in range(n)]
def find(x):
  if x==par[x]:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def union(a,b):
  ra=find(a)
  rb=find(b)
  if ra!=rb:
    par[ra]=rb

for i in range(m):
  v,w=map(f,input().split())
  union(v,w)

ans=0
for j in range(n):
  if find(j)==find(p[j]):
    ans+=1
print(ans)
print(par)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
f=lambda x:int(x)-1
p=list(map(f,input().split()))
par=[j for j in range(n)]
def find(x):
  if x==par[x]:
    return x
  else:
    par[x]=find([par[x]])
    return par[x]

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

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

ans=0
for j in range(n):
  if par[j]==par[p[j]]:
    ans+=1
print(ans)

Submission status: Wrong Answer

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())
A=UnionFind(n)
P=list(map(int,input().split()))
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  A.union(a,b)
V=[0]*n
ans=0
for i in range(n):
  if V[i]==0:
    V[i]=0
    B=[]
    C=[]
    for j in range(len(A.members(i))):
      V[j]=1
      B.append(P[j]-1)
      C.append(j)
    ans=ans+len(C)+len(B)-len(set(C)|set(B))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
p=list(map(int,input().split()))
fromto=[]
tree=[[] for _ in range(N)]
for i in range(N):
    fromto.append([i,p[i]-1])
cnt=0
for i in range(M):
    x,y=map(int,input().split())
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
col=[-1]*N
for i in range(N):
    if col[i]==-1:
        d = deque()
        d.append(i)
        while len(d)>0:
            v=d.popleft()
            col[v]=i
            for j in tree[v]:
                if col[j]==-1:
                    d.append(j)
            #print(col,d)
            #input()
#print(col,fromto)
for i in range(N):
    x=fromto[i][0]
    y=fromto[i][1]
    if col[x-1]==col[y-1]:
        cnt=cnt+1
print(cnt)

Submission status: Wrong Answer

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()}

      
n,m = map(int, input().split())
p = [x-1 for x in list(map(int, input().split()))]
key = dict()
for k,v in enumerate(p):
  key[v] = k
Union = UnionFind(n)
xy = [list(map(int, input().split())) for i in range(m)]
for x,y in xy:
  Union.union(x-1,y-1)
a = Union.all_group_members()
ans = 0

Submission status: Wrong Answer

Solution code:
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def LIR_(n): return [LI_() for i in range(n)]
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)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p = tuple(p)
uni = set()
num = set()
chk = [int(i)+1 for i in range(n)]
chk = set(chk)
for i in range(m):
  x,y = [int(i) for i in input().split()]
  uni.add(p[x-1])
  uni.add(p[y-1])
  num.add(x)
  num.add(y)
  
ans = len(uni & num)
diff = chk-num
diff = list(diff)
for i in diff:
  if i == p[i-1]:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    p = [0] + list(map(int, input().split()))
    cnt = 0
    global parent
    parent = list(range(n+1))
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        cnt += (root(i) == root(p[i]))
    print(cnt)
    
def root(x):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x])
    return parent[x]

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    ps = dict(sorted({i:pi for i, pi in enumerate(p)}.items()))
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for k, v in ps.items():
        if same(v, int(k)):
            cnt += 1
    print(cnt)
        
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 x != y:
        par[x] = y

if __name__ == "__main__":
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    par = [0] + [i for i in range(1, n+1)]
    main()

Submission status: Wrong Answer

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():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

tree = UnionFind(n)

for x, y in xy:
    tree.Unite(x, y)
root = [tree.Find_Root(i) for i in range(n)]
result = [[] for _ in range(max(root))]
for i in range(n):
    result[root[i]-1].append(i+1)
out_put = 0
for i in range(n):
    out_put += (p[i] in result[root[i]-1])
print(out_put)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def dfs(v):
    seen[v]=1
    check.append(P[v]-1)
    for nv in Graph[v]:
        if seen[nv]:
            continue
        dfs(nv)

N,M=map(int,input().split())
P=list(map(int,input().split()))
Graph=[[] for _ in range(N)]
seen=[-1 for _ in range(N)]
cnt=0
for _ in range(M):
    x,y=map(int,input().split())
    Graph[x-1].append(y-1)
    Graph[y-1].append(x-1)

for v in range(len(P)):
    if seen[v]!=-1:
        continue
    check=[]
    dfs(v)
    for p in check:
        if seen[p]==1:
            cnt+=1
        seen[p]=0
print(cnt)

Submission status: Wrong Answer

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())
A=UnionFind(n)
B=UnionFind(n)
P=list(map(int,input().split()))
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  A.union(a,b)
  B.union(P[a]-1,P[b]-1)
AA=list(A.all_group_members().values())
BB=list(B.all_group_members().values())
ans=0
for i in range(len(AA)):
  ans=ans+len(AA[i])+len(BB[i])-len(set(AA[i])|set(BB[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

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

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

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

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

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

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

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

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

uf = UnionFind(n)
ab = [tuple(map(int,input().split())) for i in range(m)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    uf.union(a,b)


ans = 0
for r in uf.all_roots():

    if uf.size(r) == 1:
        if p[r] == r: ans += 1
    else:
        loop = uf.members(r)
        member = []
        for l in loop:
            member.append(p[l]-1)
        ans += len(set(loop) & set(member))

print(ans)

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
        #ノード数nの配列を作る
        #親の番号を格納する
        #-> 自分が根だった場合は、-(その集合のサイズ)とする
        #作るときはparentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent = [-1 for _ in range(n)]
        self.n = n
    def root(self, x):
        #要素xの根の番号を返す
        if self.parent[x] < 0:
            # 自分が根
            return x
        # 要素xの親を要素xの根に変えておく(付け替える)
        # 次の呼び出しが早くなる
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]
    def size(self, x):
        #要素xの所属するグループの頂点数を調べる
        #根のparentにサイズが格納されている
        return -self.parent[self.root(x)]
    def merge(self, x, y):
        #xとyを結合する
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        #大きい方(x)に小さい方(y)をくっつけたい
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
    def family(self,x): # xが属する連結集合を返す
        return [i for i in range(self.n) if self.issame(i,x)]
    def maximum(self): # 連結最大集合を返す
        return self.family(self.parent.index(min(self.parent)))

p = list(map(int,input().split()))
UF = UnionFind(N)
for i in range(M):
    x,y = map(int,input().split())
    UF.merge(x-1,y-1)

ans = 0
L = [i for i in range(N) if UF.root(i)==i]
for i in range(len(L)):
    if UF.size(L[i])==1:
        if L[i]==p[i]-1:
            ans +=1
    else:
        S = UF.family(L[i])
        T = [p[i]-1 for i in S]
        ans += len(set(S).intersection(set(T)))
print(ans)

Submission status: Wrong Answer

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

ll=[i for i in range(1,n+1)]

def root(a,l):
    while l[a-1]!=a:
        a=l[a-1]
    return a
print(ll)
for i in range(m):
    a=max(l[i][0],l[i][1])
    b=min(l[i][0],l[i][1])
    lll=[]
    while ll[a-1]!=a:
        a=ll[a-1]
        lll.append(a)
    for j in lll:
        ll[j-1]=a
    lll=[]
    while ll[b-1]!=b:
        b=ll[b-1]
        lll.append(b) #a,bの根を探索し、ついでに経路上のを根へつなぎなおす
    for j in lll:
        ll[j-1]=b
    if a!=b: #根が同じならそのまま
        ll[b-1]=a
k=0
for i in range(n):
    if root(p.index(i+1)+1,ll)==root(i+1,ll):
        k+=1

print(k)

Submission status: Wrong Answer

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


ll=[]
for i in range(m):
    a=0
    b=0
    for j in range(len(ll)):
        if l[i][0] in ll[j] or l[i][1] in ll[j]:
            a+=1
            b=j
    if a==1:
        ll[b]=ll[b].union(set(l[i]))

    else:
        ll.append(set(l[i]))
    print(a,b,ll)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
xy = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

par = [i for i in range(n)]
rank = [0 for _ in range(n)]


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


def is_same(x, y):
    return par[x] == par[y]


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


for x, y in xy:
    union(x, y)

count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i) else 0
print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
xy = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

par = [i for i in range(n)]
rank = [0 for _ in range(n)]


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


def is_same(x, y):
    return par[x] == par[y]


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


for x, y in xy:
    union(x, y)

count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i) else 0
print(count)

Submission status: Wrong Answer

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

par = [i for i in range(n)]
rank = [1 for _ in range(n)]


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


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


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


for x, y in xy:
    unite(x - 1, y - 1)


count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i - 1) else 0
print(count)

Submission status: Wrong Answer

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

par = [i for i in range(n)]
rank = [1 for _ in range(n)]


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


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


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


for x, y in xy:
    unite(x - 1, y - 1)


count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i - 1) else 0
print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline()[:-1]

N, M = map(int, input().split())
P = list(map(int, input().split()))
groups = []

for i in range(M):
    x, y = map(int, input().split())
    exist = -1
    process = False
    for j, group in enumerate(groups):
        if x in group or y in group:
            group.add(x)
            group.add(y)
            if exist == -1:
                exist = j
                process = True
            else:
                groups[exist] |= groups[j]
                groups.pop(j)
                break
    if not process:
        groups.append({x, y})

ans = 0
for group in groups:
    target = set()
    for m in group:
        target.add(P[m-1])
        target.add(P[m-1])
    ans += len(group & target)

others = set(P)
for group in groups:
    others -= group

target = set()
for m in others:
    target.add(P[m-1])
    target.add(P[m-1])
ans += len(others & target)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M=map(int,input().split())
P=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
G=np.array([-1]*N)
Gnum=0
for x,y in XY:
  _M=max(G[x-1],G[y-1])
  _m=min(G[x-1],G[y-1])
  if _M==-1 :
    G[x-1]=G[y-1]=Gnum
    Gnum+=1
  elif _m!=-1:
    G[x-1]=G[y-1]=_m
    Gnum-=1
    G[np.where(G>=_M)[0].tolist()]-=1
  else:
    G[x-1]=G[y-1]=_M
for i in range(N):
  if G[i]==-1:
    G[i]=Gnum
    Gnum+=1
Group=[]
for i in range(Gnum):
  Group.append(np.where(G==i)[0].tolist())
ans=0
for i in range(N):
  if i in Group[G[P[i]-1]]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M=map(int,input().split())
P=list(map(int,input().split()))
XY=[sorted(list(map(int,input().split()))) for i in range(M)]
G=np.array([-1]*N)
Gnum=0
for x,y in XY:
  _M=max(G[x-1],G[y-1])
  _m=min(G[x-1],G[y-1])
  if _M==-1 :
    G[x-1]=G[y-1]=Gnum
    Gnum+=1
  elif _m!=-1:
    G[x-1]=G[y-1]=_m
    Gnum-=1
    G[np.where(G>=_M)]-=1
  else:
    G[x-1]=G[y-1]=_M
for i in range(N):
  if G[i]==-1:
    G[i]=Gnum
    Gnum+=1
Group=[]
for i in range(Gnum):
  Group.append(np.where(G==i)[0].tolist())
ans=0
for i in range(N):
  if i in Group[G[P[i]-1]]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    alr[x] = False
    alr[y] = False
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.add(num)
            indlist.add(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        count += len(numlist & indlist)
    else:
        if p[i] == i:
            count += 1
print(count)