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:
n,m=map(int,input().split())
p=list(map(int,input().split()))
num=[[] for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    num[x-1].append(y)
    num[y-1].append(x)
seen=[False]*n
ans=[-1]*n
for i in range(n):
    if seen[i]==False:
        queue=[i]
        for j in range(n):
            if len(queue)==0:
                break
            num1=queue.pop()
            seen[num1]=True
            ans[num1]=i
            for k in range(len(num[num1])):
                num2=num[num1][k]-1
                if seen[num2]==False:
                    queue.append(num2)
ans2=0
for i in range(n):
    if ans[i]==ans[p[i]-1]:
        ans2+=1
print(ans2)

Submission status: Wrong Answer

Solution code:
class Unionfind():  # 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 all_group_members(self):  # グループごとの辞書
        members_dict = {}
        for i, x in enumerate(self.parents):
            if self.find(x) not in members_dict:
                members_dict[self.find(x)] = set()
            members_dict[self.find(x)].add(i)
        return members_dict


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

uf = Unionfind(n)
for x, y in xy:
    uf.union(x - 1, y - 1)

ans = 0
for lst in uf.all_group_members().values():
    ans += sum((p[num] - 1 in lst) for num in lst)
print(ans)

Submission status: Wrong Answer

Solution code:
class Unionfind():  # 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 members(self, x):  # グループの要素
        root = self.find(x)
        return set(i for i in range(self.N) if self.find(i) == root)

    def roots(self):  # 根のリスト
        return set(i for i, x in enumerate(self.parents) if x < 0)

    def all_group_members(self):  # グループごとの辞書
        return {r: self.members(r) for r in self.roots()}


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

uf = Unionfind(n)
for x, y in xy:
    uf.union(x - 1, y - 1)

ans = 0
for lst in uf.all_group_members().values():
    ans += 1
    #ans += sum((p[num] - 1 in lst) for num in lst)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]

class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())


uf=UnionFind(n*2)
# uf2=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    uf.union(P[a],P[b])
    uf.union(a+n,b+n)
    uf.union(a+n,P[a])
ans=0
# print(uf.state_grouping(), uf2.state_grouping())
for l in uf.state_grouping():
    # l=set(l)
    num={i for i in l if i<n}
    ind={i-n for i in l if i>=n}
    ans+=len(num & ind)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]

class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())


uf=UnionFind(n)
uf2=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    uf.union(P[a],P[b])
    uf2.union(a,b)
ans=0
for l,ind in zip(uf.state_grouping(), uf2.state_grouping()):
    ans+= len([i for i in l if i in ind])
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p = [100000 - int(x) for x in input().split()]

class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1] * n
 
    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
 
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u == v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u # size[u] <= size[v]
        self.size[v] += self.size[u]
        self._par[u] = v
 
    def is_connected(self, u, v):
        return self.root(u) == self.root(v)

uf = UnionFind(10 ** 6)
for i in range(n):
    uf.unite(i+1, p[i])
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x, y)

ans = 0
for i in range(1, n+1):
    if uf.is_connected(i, 100000-i):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m,=map(int,input().split())
p=list(map(int,input().split()))
way=[[] for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    way[x].append(y)
    way[y].append(x)
ans=0
top=[False]*n
for i in range(n):
    l=deque([i])
    s=set([])
    t=set([])
    while l:
        now=l.popleft()
        for to in way[now]:
            if top[to]:
                continue
            else:
                top[to]=True
                l.append(to)
                s.add(to)
                t.add(p[to]-1)
    ans+=len(s&t)
print(ans)

Submission status: Wrong Answer

Solution code:
# 16:09 - 16:36
N,M = map(int,input().split())
P = [0]+list(map(int,input().split()))
T = [[] for i in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    T[x].append(y)
    T[y].append(x)

X = [True]*(N+1)
X[0] = False
ans = 0
for i in range(N+1):
    if X[i]:
        Y,Z = [],[]
        Q = [i]
        while Q:
            v = Q.pop()
            X[v] = False
            Y.append(v)
            Z.append(P[v])
            for c in T[v]:
                if X[c]:
                    Q.append(c)
        Y.sort()
        Z.sort()
        n = len(Y)
        k = 0
        for j in range(n):
            while True:
                if k==n:break
                if Y[j]<=Z[k]:
                    if Y[j]==Z[k]:
                        ans+=1
                    break
                else:
                    k+=1
            if k==n:break
print(ans)

Submission status: Wrong Answer

Solution code:
# 16:09 - 16:30
N,M = map(int,input().split())
P = [0]+list(map(int,input().split()))
T = [[] for i in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    T[x].append(y)
    T[y].append(x)

X = [True]*(N+1)
X[0] = False
ans = 0
for i in range(N+1):
    if X[i]:
        Y,Z = [],[]
        Q = [i]
        while Q:
            v = Q.pop()
            X[v] = False
            Y.append(v)
            Z.append(P[v])
            for c in T[v]:
                if X[c]:
                    Q.append(c)
        Y.sort()
        Z.sort()
        n = len(Y)
        k = 0
        for j in range(n):
            while True:
                if k==n:break
                if Y[j]==Z[k]:
                    ans+=1
                    k+=1
                    break
                elif Y[j]<Z[k]:
                    break
                k+=1
            if k==n:break
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
rank=[0 for i in range(n)]
r=[i for i in range(n)]
si=[{i} for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    si[rx]=si[ry]|si[rx]
    sp[rx]=sp[rx]|sp[ry]
  else:
    r[ry]=rx
    si[rx]=si[rx]|si[ry]
    sp[rx]=sp[rx]|sp[ry]
    if r[rx]==r[ry]:
      rank[rx]+=1
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(x)]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if (i in get(i)) or i==p[i]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
p = [0] + LI()

g = [i for i in range(N+1)]
g_num = [1 for _ in range(N+1)]

def find(x):
    if g[x] == x : return x
    g[x] = find(g[x])
    return g[x]

def union(x,y):
    if find(g[x]) == find(g[y]): return
    if g_num[g[x]] < g_num[g[y]]: x,y = y,x
    g_num[g[x]] += g_num[g[y]]
    g[g[y]] = g[x]

for _ in range(M):
    x,y = LI()
    union(x,y)

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

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

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

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

    if x == y:
      return

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

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

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

n,m=nii()
p=list(nii())

uf=UnionFind(n+1)

for i in range(m):
  x,y=nii()
  uf.union(x,y)

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

print(n-cnt)

Submission status: Wrong Answer

Solution code:
# Union Find
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True

# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


n, m = map(int,input().split())
p = list(map(int,input().split()))
par = [-1] * n
ans = 0
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    unite(x,y)


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

Submission status: Wrong Answer

Solution code:
# Union Find
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True

# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)




n, m = map(int,input().split())
p = list(map(int,input().split()))
par = [-1] * n
ans = 0
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    unite(x,y)
for i in range(n):
    if same(p.index(i+1),0) or p[i] == i:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
import heapq
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(list)
        for i in range(self.n):
            d[self.find(i)] += [i]
        t = list(d.keys())
        for i in t:
            heapq.heapify(d[i])
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        p[i] -= 1
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if uf.same(r,i):
            pre = int(p[i])
            new = heapq.heappop(d[r])
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    for i in range(N):
        tmp = p[i]-1
        if uf.same(uf.find(tmp),i):
            p[i] = i
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
maxn = 100000

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

par = [0] * (n+1)
rank = [0] * (n+1)

#初期化
for i in range(n+1):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
#結合
def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1

for _ in range(q):
    a,b = map(int, input().split())
    unite(a,b)

ans = 0
for i in range(1,n+1):
    if par[p.index(i)+1] == find(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 = map(int,input().split())
p = list(map(lambda x : int(x)-1,input().split()))
count = 0
uf = UnionFind(N)
for _ in range(M):
    i,j = map(lambda x : int(x)-1,input().split())
    uf.union(i,j)
dic = uf.all_group_members()
print(dic)
for i in range(N):
    if uf.same(p[i],i):
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def find(x): # 木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def unite(x,y): # xとyの属する集合を併合
    x=find(x)
    y=find(y)
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

def same(x,y): # xとyが同じ集合に属するか判定
    return find(x)==find(y)

def main():
    n,m=inpm()
    global par,rank
    par=[i for i in range(n)]  # 親
    rank=[0 for _ in range(n)] # 木の深さ
    p=inpl()
    xy=[]
    for _ in range(m):
        x,y = inpm()
        if x>y:
            x,y=y,x
        xy.append([x,y])
    xy.sort()
    for i in range(m):
        x,y=xy[i]
        unite(x-1,y-1)
    groop=[[] for _ in range(n)]
    for i in range(n):
        groop[par[i]].append(i)
    ans=0
    for i in range(n):
        ps=[]
        for j in range(len(groop[i])):
            ps.append(p[groop[i][j]]-1)
        if ps==[]:
            continue
        else:
            ans+=len(set(ps)&set(groop[i]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def find(x): # 木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def unite(x,y): # xとyの属する集合を併合
    x=find(x)
    y=find(y)
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

def same(x,y): # xとyが同じ集合に属するか判定
    return find(x)==find(y)

def main():
    n,m=inpm()
    global par,rank
    par=[i for i in range(n)]  # 親
    rank=[0 for _ in range(n)] # 木の深さ
    p=inpl()
    xy=[]
    for _ in range(m):
        x,y = inpm()
        if x>y:
            x,y=y,x
        xy.append([x,y])
    xy.sort()
    for i in range(m):
        x,y=xy[i]
        unite(x-1,y-1)
    groop=[[] for _ in range(n)]
    for i in range(n):
        groop[par[i]].append(i)
    ans=0
    for i in range(n):
        ps=[]
        for j in range(len(groop[i])):
            ps.append(p[groop[i][j]]-1)
        if ps==[]:
            continue
        else:
            l=len(ps)
            ps.sort()
            x=0
            y=0
            while x<l and y<l:
                if ps[x]==groop[i][y]:
                    ans+=1
                    x+=1
                    y+=1
                elif ps[x]>groop[i][y]:
                    y+=1
                elif ps[x]<groop[i][y]:
                    x+=1
    print(ans)


if __name__ == "__main__":
    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:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)
        self.root = [-1]*(n+1)
        self.cnt = 0

    # 検索
    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 groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[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 count(self, x):
        return -self.root[self.find(x)]
#
#graph = [[] for _ in range(N)]
#
#for x,y in xy:
#    graph[x-1].append(y-1)
#    graph[y-1].append(x-1)
        
    
uf = UnionFind(N)
for x,y in xy:
    uf.union(x-1,y-1)
    
idxlist = [[] for _ in range(N)]

for i,t in enumerate(uf.par):
    idxlist[t].append(i)
    
import bisect
ans = 0
for idxs in idxlist:
    for idx in idxs:
        tmpidx = bisect.bisect_left(idxs,P[idx]-1)
        if tmpidx >= len(idxs):continue
        if idxs[tmpidx] == P[idx]-1:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
class uf():
    def __init__(self,n):
        self.root = [-1] * (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):
        rootx = self.findroot(x)
        rooty = self.findroot(y)
        if rootx == rooty:
            return
        else:
            self.root[rootx] += self.root[rooty]
            self.root[rooty] = rootx
            return

    def is_same_group(self,x,y):
        return self.findroot(x) == self.findroot(y)

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

uf = uf(N)

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

count = 0
for n in range(N):
    if uf.is_same_group(P[n-1],n+1):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            x = self.parent[x] = self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

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

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

print(ans)
#print([uf.root(i) for i in range(n)])
#print([uf.parent[i] for i in range(n)])
#print([uf.size(i) for i in range(n)])

Submission status: Wrong Answer

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

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

graph = [0] * (n + 1)
for i in range(n):
    graph[i] = i

#木の根を求める
def root(x):
    if graph[x] == x:
        return x
    else:
        graph[x] = root(graph[x])
        return graph[x]

def isSame(x, y):
    if root(x) == root(y):
        print("Yes")
    else:
        print("No")

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

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

#print(graph)

tmp = [[] for _ in range(n+1)]
tmp_ = [[] for _ in range(n+1)]
for i in range(n):
    tmp[graph[i]].append(i+1)
    tmp_[graph[i]].append(i+1)

tmp_2 = [[] for _ in range(n+1)]
index = 0
for s in tmp_:
    while len(s) != 0:
        tmp_2[index].append(p[s.pop()-1])
    index += 1

#print(tmp)
#print(tmp_2)
ans = set()
for i in range(n):
    ans = ans | (set(tmp[i]) & set(tmp_2[i]))

print(len(ans))

Submission status: Wrong Answer

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

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

for _ in range(M):
	x,y=map(int, input().split())
	for p in list(path[x]):
		path[p] |= path[y]
	for p in list(path[y]):
		path[p] |= path[x]

Submission status: Wrong Answer

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

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

for _ in range(M):
	x,y=map(int, input().split())
	for p in list(path[x]):
		path[p] |= path[y]
	for p in list(path[y]):
		path[p] |= path[x]

Submission status: Wrong Answer

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

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

for _ in range(M):
	x,y=map(int, input().split())
	for p in path[x]:
		path[p].add(y)
	for p in path[y]:
		path[p].add(x)