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:
def main():
    import sys
    sys.setrecursionlimit(1000000000)
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    g = [-1 for _ in range(n)]

    def s(x):
        if g[x] < 0:
            return x
        else:
            return s(g[x])

    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        a, b = s(i), s(j)
        if a > b:
            a, b = b, a

        g[a] -= 1
        g[b] = a

    t = [None] * n
    for i in range(n):
        t[i] = s(i)

    ans = 0
    for i in range(n):
        a = p[i] - 1
        b = t[a]
        c = t[i]
        if b == c:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000000000)
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    g = [-1 for _ in range(n)]

    def s(x):
        if g[x] < 0:
            return x
        else:
            return s(g[x])

    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        a, b = s(i), s(j)
        if a > b:
            a, b = b, a

        g[a] -= 1
        g[b] = a

    t = [None] * n
    for i in range(n):
        t[i] = s(i)

    ans = 0
    for i in range(n):
        a = p[i] - 1
        b = t[a]
        c = t[i]
        if b == c:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000000000000000000000000)
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    g = [-1 for _ in range(n)]

    def s(x):
        if g[x] < 0:
            return x
        else:
            return s(g[x])

    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        a, b = s(i), s(j)
        if a > b:
            a, b = b, a

        g[a] -= 1
        g[b] = a

    t = [None] * n
    for i in range(n):
        t[i] = s(i)

    ans = 0
    for i in range(n):
        a = p[i] - 1
        b = t[a]
        c = t[i]
        if b == c:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    g = [-1 for _ in range(n)]

    def s(x):
        if g[x] < 0:
            return x
        else:
            return s(g[x])

    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        a, b = s(i), s(j)
        if a > b:
            a, b = b, a

        g[a] -= 1
        g[b] = a

    t = [None] * n
    for i in range(n):
        t[i] = s(i)

    ans = 0
    for i in range(n):
        a = p[i] - 1
        b = t[a]
        c = t[i]
        if b == c:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10000000)
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    g = [-1 for _ in range(n)]

    def s(x):
        if g[x] < 0:
            return x
        else:
            return s(g[x])

    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        a, b = s(i), s(j)
        if a > b:
            a, b = b, a
            i, j = j, i

        g[a] -= 1
        g[b] = a

    t = []
    for i in range(n):
        c = s(i)
        t.append(c)

    ans = 0
    for i in range(n):
        a = p[i] - 1
        b = t[a]
        c = t[i]
        if b == c:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(100000)
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    g = [-1 for _ in range(n)]

    def s(x):
        if g[x] < 0:
            return x
        else:
            return s(g[x])

    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        a, b = s(i), s(j)
        if a > b:
            a, b = b, a
            i, j = j, i

        g[a] -= 1
        g[b] = a

    t = []
    for i in range(n):
        c = s(i)
        t.append(c)

    ans = 0
    for i in range(n):
        a = p[i] - 1
        b = t[a]
        c = t[i]
        if b == c:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    g = [-1 for _ in range(n)]

    def s(x):
        if g[x] < 0:
            return x
        else:
            return s(g[x])

    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        a, b = s(i), s(j)
        if a > b:
            a, b = b, a
            i, j = j, i

        g[a] -= 1
        g[b] = a

    t = []
    for i in range(n):
        c = s(i)
        t.append(c)

    ans = 0
    for i in range(n):
        a = p[i] - 1
        b = t[a]
        c = t[i]
        if b == c:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind():
  from collections import defaultdict
  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):
    ret = defaultdict(list)
    for i in range(self.n):
      ret[self.find(i)].append(i)
    return ret

  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 = 0

for L in D.values():
  check = set(L)
  for i in L:
    if P[i]-1 in check:
      ans += 1 

print(ans)

Submission status: Runtime Error

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

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

ans=0
groups = uf.all_group_members().values()

for c in groups:
    ans+= len( set(c) & set(p[i] for i in c ) ) 
print(ans)

Submission status: Runtime Error

Solution code:
n,m,p=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])==i:
    ans+=1
print(ans)

Submission status: Runtime Error

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]=par[ry]
 
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)

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.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)

unionfind = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    unionfind.union(x, y)
ans = 0
for i in range(N):
    if i + 1 != p[i]:
        if unionfind.same(p[i], i + 1):
            ans += 1
    else:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc097/tasks/arc097_b
# 15:36-15:48 give up => hint
# 15:53-16:16

import sys

sys.setrecursionlimit(10000)


def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    p = [num-1 for num in p]
    x, y = [None] * M, [None] * M
    for i in range(M):
        x[i], y[i] = map(int, input().split())
        x[i] -= 1  # 0-index
        y[i] -= 1  # 0-index

    edges = {node: [] for node in range(N)}
    for xi, yi in zip(x, y):
        edges[xi].append(yi)
        edges[yi].append(xi)

    def rec(parent_node):
        children = edges[parent_node]
        for child in children:
            if check_node[child] is not None:
                continue

            indexes.append(child)
            numbers.append(p[child])
            check_node[child] = 1

            rec(child)

    ans = 0
    check_node = [None] * N
    for start in range(N):
        if check_node[start] is not None:
            continue

        # joint = [start]
        check_node[start] = 1
        indexes = [start]
        numbers = [p[start]]
        rec(start)

        ans += len(set(indexes) & set(numbers))

    return ans


print(main())

Submission status: Runtime Error

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc097/tasks/arc097_b
# 15:36-15:48 give up => hint
# 15:53-16:16


def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    p = [num-1 for num in p]
    x, y = [None] * M, [None] * M
    for i in range(M):
        x[i], y[i] = map(int, input().split())
        x[i] -= 1  # 0-index
        y[i] -= 1  # 0-index

    edges = {node: [] for node in range(N)}
    for xi, yi in zip(x, y):
        edges[xi].append(yi)
        edges[yi].append(xi)

    def rec(parent_node):
        children = edges[parent_node]
        for child in children:
            if check_node[child] is not None:
                continue

            indexes.append(child)
            numbers.append(p[child])
            check_node[child] = 1

            rec(child)

    ans = 0
    check_node = [None] * N
    for start in range(N):
        if check_node[start] is not None:
            continue

        # joint = [start]
        check_node[start] = 1
        indexes = [start]
        numbers = [p[start]]
        rec(start)

        ans += len(set(indexes) & set(numbers))

    return ans


print(main())

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

      
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 range(xy):
  Union.union(x-1,y-1)
a = Union.all_group_members()
ans = 0
for i in a.values():
  x = set()
  for j in i:
    x.add(key[j])
  y = set(i)
  ans += len(x & y)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

class UnionFind:
    def __init__(self,size):
        self.size = size
        self.parents = [i for i in range(size)]
        self.ranks = [0 for i in range(size)]

    def ancestor(self,i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.ancestor(self.parents[i])
            return self.parents[i]

    def union(self,i,j):
        ip = self.ancestor(i)
        jp = self.ancestor(j)
        if ip == jp:
            return False
        else:
            if self.ranks[ip] > self.ranks[jp]:
                self.parents[jp] = ip
            else:
                self.parents[ip] = jp
                if self.ranks[ip] == self.ranks[jp]:
                    self.ranks[ip]+=1

    def same(self,i,j):
        return self.ancestor(i) == self.ancestor(j)

    def __str__(self):
        parentDict = {}
        for i in range(self.size):
            a = self.ancestor(i)
            if a not in parentDict:
                parentDict[a] = [i]
            else:
                parentDict[a].append(i)
        result = f"===UnionFind description===\nSize:{self.size}\nGroupCount:{len(parentDict)}\n\nGroups:\n"
        for k in parentDict.keys():
            elements = ""
            for elem in parentDict[k]:
                elements+= f" {elem},"
            result += f"Group-{k}(Count:{len(parentDict[k])}):[{elements}]\n"
        return result





def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    U = UnionFind(N)
    for i in range(M):
        U.union(x[i]-1,y[i]-1)
    sum = 0
    for i in range(N):
        if p[i] == i+1 or U.same(p[i]-1,i):
            sum+=1
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, p, x, y)

if __name__ == '__main__':
    main()

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.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)

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

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

ans = 0

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

Submission status: Runtime Error

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):
        if root(i) == root(p[i]):
        cnt += 1
    print(cnt)

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

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

if __name__ == "__main__":
    main()

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():
    # 作りたい要素数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-1, y-1)
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])
    if not(p[i] in result[root[i]-1]):
        print(i+1)
print(out_put)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10**8)
def dfs(v):
    seen[v]=True
    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)]
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)):
    p=P[v]-1
    seen=[False for _ in range(N)]
    dfs(v)
    if seen[p]:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = []
for _ in range(M):
    xy.append(tuple(map(int, input().split())))
#print(xy)


G = [[] for _ in range(N+1)]
for el in xy:
    x, y = el
    G[x].append(y)
    G[y].append(x)


seen=[False] * (N+1)
def dfs(n):
    seen[n]=True
    group[-1].append(n)
    for child in G[n]:
        if seen[child] == False:
            dfs(child)

group=[]
for i in range(1,N+1):
    if seen[i] == False:
        group.append([])
        dfs(i)
        #print(seen)
#print(seen)
#print(group)

cnt = 0
for el in group:
    temp = set(el) & set([p[i-1] for i in el])
    cnt += len(temp)
print(cnt)

Submission status: Runtime Error

Solution code:
# ABC097D - Equals (ARC097D)
"""
Union-Find: O(α(N))

Verified:
    https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A
    https://judge.yosupo.jp/problem/unionfind
"""


class UnionFind:
    __slots__ = ["_data_size", "_first_index", "_parents"]

    def __init__(self, data_size: int, is_zero_indexed: bool = True) -> None:
        self._data_size = data_size
        self._first_index = 0 if is_zero_indexed else 1
        self._parents = [-1] * (data_size + self._first_index)

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), 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 main():
    N, _, *PXY = open(0).read().split()
    P, XY = PXY[:N], PXY[N:]
    uf = UnionFind(N, is_zero_indexed=False)
    for x, y in zip(*[iter(XY)] * 2):
        uf.unite(x, y)
    ans = sum(uf.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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)))
    def all_family(self): # 根集合P, 子集合の集合C(C[i]にはP[i]を根とする子集合が入る)
        P = [i for i in range(self.n) if self.parent[i] < 0] # 根の集合
        p = len(P)
        C = [[] for _ in range(p)]
        for i in range(self.n):
            C[self.root(i)].append(i)
        return C




            

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
C = UF.all_family()
for i in range(len(C)):
    S = C[i]
    T = [p[i]-1 for i in S]
    ans += len(set(S).intersection(set(T)))

print(ans)

Submission status: Runtime Error

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

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

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

# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)

# xとyの属する集合を併合(ランク有)
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
            rank[y] += rank[x]
        else:
            par[y] = x
            rank[x] += rank[y]

for i in range(Q):
    p,a,b = map(int,input().split())
    if p == 0:
        unite(a,b)
    else:
        print('Yes' if bool_same(a,b) else 'No')

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open('0').read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
ans = sum(1 if u.same(p,i+1) else 0 for i,p in enumerate(p))
print(ans)

Submission status: Runtime Error

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

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

def uf_root(a):
  if par[a] == a: return a
  par[a] = uf_root( par[a] )
  return par[a]

def uf_same(a,b):
  if (uf_root(a) ==uf_root(b)): return True
  return false

def uf_union(a,b):
  if (uf_same(a,b)): return
  a = uf_root(a)
  b = uf_root(b)
  par[a] = b
  return

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

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

Submission status: Runtime Error

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(n)]

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 root(x) == root(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[x] == rank[y]:
            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: Runtime Error

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(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: Runtime Error

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(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: 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)]

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


def root(x):
    if x == par[x]:
        return x
    par[x] = root(par[x])  # 経路圧縮
    return par[x]


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


def unite(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[x] == rank[y]:
            rank[x] += 1
    par[x] = y


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: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
def dfs(loc,num):
    root[loc]=num
    for item in plan[loc]:
        if root[item]==-1:
            dfs(item,num)
    return 0

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

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

plan=[[]for i in range(N)]
root=[-1]*N

for _ in range(M):
    a,b=map(int,input().split())
    plan[a-1].append(b-1)
    plan[b-1].append(a-1)

for i in range(N):
    if root[i]==-1:
        dfs(i,i)

ans=0
for i in range(N):
    if root[i]==root[P[i]-1]:
        ans+=1
#print(root)
print(ans)