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: Time Limit Exceeded

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 i in range(N):
    if i in uf.members( p[i] - 1 ):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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 i in range(N):
    if i in uf.members( p[i] - 1 ):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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():
    tmp = set()
    for y in x:
        tmp.add(p[y]-1)
    for y in x:
        if y in tmp:
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

    for y in x:
        tmp.append(p[y]-1)
    for y in x:
        if y in tmp:
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

    # 要素xの根の値を取得
    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())


def resolve():
    N, M = list(map(int, input().split()))
    P = list(map(int, input().split()))
    XY = [list(map(int, input().split())) for _ in range(M)]
    uf = UnionFind(N)
    for xy in XY:
        uf.union(xy[0]-1, xy[1]-1)
    group_members = list(map(set, uf.all_group_members().values()))
    #print(group_members)
    cnt = 0
    for v in group_members:
        
        for i in v:
            if P[i]-1 in v:
                cnt += 1
    print(cnt)
    
    
if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

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

    # 要素xの根の値を取得
    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())


def resolve():
    N, M = list(map(int, input().split()))
    P = list(map(int, input().split()))
    XY = [list(map(int, input().split())) for _ in range(M)]
    uf = UnionFind(N)
    for xy in XY:
        uf.union(xy[0]-1, xy[1]-1)
    group_members = list(map(set, uf.all_group_members().values()))
    #print(group_members)
    cnt = 0
    for v in group_members:
        for i in v:
            if P[i]-1 in v:
                cnt += 1
    print(cnt)
    
    
if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

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

    # 要素xの根の値を取得
    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())


def resolve():
    N, M = list(map(int, input().split()))
    P = list(map(int, input().split()))
    XY = [list(map(int, input().split())) for _ in range(M)]
    uf = UnionFind(N)
    for xy in XY:
        uf.union(xy[0]-1, xy[1]-1)
    group_members = list(map(set, uf.all_group_members().values()))
    #print(group_members)
    cnt = 0
    for v in group_members:
        pvalues = set()
        for i in v:
            pvalues.add(P[i]-1)
        cnt += len(pvalues & v)
    print(cnt)
    
    
if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

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

    # 要素xの根の値を取得
    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())


def resolve():
    N, M = list(map(int, input().split()))
    P = list(map(int, input().split()))
    XY = [list(map(int, input().split())) for _ in range(M)]
    uf = UnionFind(N)
    for xy in XY:
        uf.union(xy[0]-1, xy[1]-1)
    group_members = uf.all_group_members()
    #print(group_members)
    cnt = 0
    for v in group_members.values():
        pvalues = [P[i]-1 for i in v]
        cnt += len(set(pvalues) & set(v))
    print(cnt)
    
    
if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
class DisjointSet:
    def __init__(self,size):
        self.rank=[0]*size
        self.p=[0]*size
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self,i):
        self.p[i]=i
        self.rank[i]=0
    
    def same(self,x,y):
        return self.findSet(x) == self.findSet(y)
    
    def unite(self, x,y):
        self.link(self.findSet(x), self.findSet(y))
    
    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y]+=1
     
    def findSet(self, x):
        if(x!=self.p[x]):
            self.p[x]=self.findSet(self.p[x])
        return self.p[x]

    def print(self):
        print(self.p)
        
def readinput():
    n,m=list(map(int,input().split()))
    p=list(map(int,input().split()))
    p.insert(0,0)
    pairs=[]
    for _ in range(m):
        pair=list(map(int,input().split()))
        pairs.append(pair)
    return n,m,p,pairs

def main(n,m,p,pairs):
    uft=DisjointSet(n+1)
    for x,y in pairs:
        if uft.same(x, y):
            pass
        else:
            uft.unite(x, y)

    #uft.print()

    #print(p)
    count=0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i==p[j]:
                #print(i,j)
                break
        if uft.same(i,j):
            #p[i],p[j] = p[j], p[i]
            count+=1
    
    return count

if __name__=='__main__':
    n,m,p,pairs=readinput()
    ans=main(n,m,p,pairs)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self._n = n
        self._table = [-1]*n
        self._rank = [0]*n

    def _root(self, x):
        stack = []
        while self._table[x] >= 0:
            stack.append(x)
            x = self._table[x]
        for y in stack:
            self._table[y] = x
        return x
    
    def unite(self, x, y):
        x, y = self._root(x), self._root(y)
        if x == y:
            return
        elif self._rank[x] > self._rank[y]:
            self._table[x] += self._table[y]
            self._table[y] = x
        else:
            self._table[y] += self._table[x]
            self._table[x] = y
            if self._rank[x] == self._rank[y]:
                self._rank[y] += 1
    
    def find(self, x, y):
        return self._root(x) == self._root(y)

    def count(self, x):
        return -self._table[self._root(x)]
    
    def __str__(self):
        return str(list(self))
    def __repr__(self):           
        return repr(list(self))
    def __iter__(self):
        return (self._root(i) for i in range(n))
    def __list__(self):
        return list(iter(self))

n, m, *X = map(int, open(0).read().split())
P, XY = X[:n], X[n:]

uf = UnionFind(n)
for x, y in zip(XY[::2], XY[1::2]):
    uf.unite(x-1, y-1)
group = list(uf)
ans = 0
for i in set(group):
    L = {j for j, n in enumerate(group, 1) if n == i}
    R = {P[l-1] for l in L}
    ans += len(L & R)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
s = list(map(int, input().split()))
g = [[] for i in range(n)]

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

q = deque()
chk = [0] * n
res = []

for i in range(n):
    tmp = set()
    if not chk[i]:
        q.append(i)
        while q:
            v = q.pop()
            chk[v] = 1
            tmp.add(v)
            for u in g[v]:
                if chk[u] == 1:
                    continue
                q.append(u)
        res.append(tmp)

ans = 0
for re in res:
    tmp2 = set()
    for r in re:
        tmp2.add(s[r] - 1)
    ans += len(tmp2 & re)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
P = tuple(map(lambda x:int(x)-1, input().split()))
swaps = [set() for _ in range(n)]
for i in range(m):
    x, y = tuple(map(lambda x:int(x)-1, input().split()))
    swaps[x].add(y)
    swaps[y].add(x)

c = 0
from collections import deque
for idx in range(n):
    q = deque([idx])
    visited = {idx}
    while q:
        i = q.pop()
        if idx == P[i]:
            c += 1
            break
        for s in swaps[i]:
            if not s in visited:
                visited.add(s)
                q.append(s)
print(c)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
P = tuple(map(lambda x:int(x)-1, input().split()))
swaps = [set() for _ in range(n)]
for i in range(m):
    x, y = tuple(map(lambda x:int(x)-1, input().split()))
    swaps[x].add(y)
    swaps[y].add(x)

c = 0
from collections import deque
for idx in range(n):
    q = deque([idx])
    visited = {idx}
    while q:
        i = q.pop()
        if idx == P[i]:
            c += 1
            break
        for s in swaps[i]:
            if not s in visited:
                visited.add(s)
                q.append(s)
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

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

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

    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

    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.par) if i==x]

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

uni = UnionFind(N)
for xyi in xy:
    x, y = xyi
    x, y = x-1, y-1
    uni.union(x, y)
# print(uni.all_group_members())

res = 0
for gr in uni.all_group_members().values():
    if len(gr)==1:
        if gr[0]+1 == p[gr[0]]:
            res += 1
    else:
        s1 = set(itemgetter(*gr)(p))
        s2 = set([val+1 for val in gr])
        res += len(s1&s2)
print(res)

Submission status: Time Limit Exceeded

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

neighbors = {v: [] for v in range(n)}
for _ in range(m):
    x, y = map(int, input().split())
    neighbors[x - 1] += [y - 1]
    neighbors[y - 1] += [x - 1]


visited = [False] * n

def conn(i0):
    q = [i0]
    c = set([i0])
    while q:
        i = q.pop()
        visited[i] = True
        c.add(i)
        for n in neighbors[i]:
            if not visited[n]:
                q.append(n)
    return c


def nmatch(c):
    p = set([ps[i] for i in c])
    return len(p & c)


conns = []
for i in range(n):
    if not visited[i]:
        conns.append(conn(i))


answer = sum(nmatch(c) for c in conns)
print(answer)

Submission status: Time Limit Exceeded

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:
    B=[]
    C=[]
    AA=A.members(i)
    for j in range(len(AA)):
      V[AA[j]]=1
      B.append(P[AA[j]]-1)
      C.append(AA[j])
    ans=ans+len(C)+len(B)-len(set(C)|set(B))
print(ans)

Submission status: Time Limit Exceeded

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)
AA=list(A.all_group_members().values())
V=[0]*n
ans=0
for i in range(len(AA)):
  B=[P[AA[i][j]]-1 for j in range(len(AA[i]))]
  ans=ans+len(AA[i])+len(B)-len(set(AA[i])|set(B))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    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 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 all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
          
    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 cand in groups:
        ans+=len(set(cand) & set(p[i]-1 for i in cand) )
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n,m=map(int,input().split())
    p = [int(i)-1 for i in 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)
    
        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()}
    
          
    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 cand in groups:
        ans+=len(set(cand) & set(p[i] for i in cand) )
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m=map(int,input().split())
    p = [int(i)-1 for i in 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)
    
        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()}
    
          
    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 cand in groups:
        ans+=len(set(cand) & set(p[i] for i in cand) )
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
p = [int(i)-1 for i in 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)

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

      
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 cand in groups:
    ans+=len(set(cand) & set(p[i] for i in cand) )
print(ans)