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:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]

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

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

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

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

tree = UnionFind(n)
for x, y in xy:
    tree.Unite(x, y)

root = [[] for _ in range(n+1)]
for i in range(n):
    root[tree.Find_Root(p[i])].append(i+1)
out_put = 0
for i in range(n):
    if p[i] in root[tree.Find_Root(p[i])]:
        out_put += 1

print(out_put)

Submission status: Time Limit Exceeded

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

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

for v in range(len(P)):
    if seen[v]:
        continue
    check=[]
    tmp_seen=[False for _ in range(N)]
    dfs(v)
    for p in check:
        if tmp_seen[p]:
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
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: Time Limit Exceeded

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

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: 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())
p=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)

ans=0
for List in list(uf.all_group_members().values()):
    tree=set()
    for i in range(len(List)):
        tree.add(p[List[i]])
    for g in range(len(List)):
        if List[g]+1 in tree:
            tree.remove(List[g]+1)
            ans+=1
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())
p=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)

for List in list(uf.all_group_members().values()):
    tree=set()
    for i in range(len(List)):
        tree.add(p[List[i]])
    for g in range(len(List)):
        if List[g]+1 in tree:
            p[List[g]]=List[g]+1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]

from collections import deque

def bfs(u):
    d = [-1] * n
    queue = deque([u])
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] < 0:
                d[i] = d[v] + 1
                queue.append(i)
    return d

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

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

ans = 0

for i, j in enumerate(p):
    # print(i, j)
    d = bfs(i)
    # print(d)
    if d[j - 1] >= 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
p=list(map(int,input().split()))
E=[[] for _ in range(N)]
unseen=[]
for i in range(M):
  x,y=map(int,input().split())
  x-=1
  y-=1
  if p[x]==x+1 and p[y]==y+1:
    pass
  else:
    if x not in unseen:
      unseen.append(x)
    if y not in unseen:
      unseen.append(y)
    E[x].append(y)
    E[y].append(x)
  
cnt=0
done=[]
for i in range(N):
  if p[i]==i+1:
    cnt+=1
    done.append(i+1)
while unseen:
  u=unseen.pop()
  tmp=[u]
  seen=[u+1]
  list_num=[p[u]]
  while tmp:
    u=tmp.pop()
    for v in E[u]:
      if v+1 not in seen:
        seen.append(v+1)
        tmp.append(v)
        list_num.append(p[v])
        if v in unseen:
          unseen.remove(v)
  tmp_set=set(list_num)&set(seen)
  cnt+=len(tmp_set)
  cnt-=len(tmp_set&set(done))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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


ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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


ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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


ans = 0
visited = [0]*n
for i in range(len(p)):
    if visited[p[i]-1] == 1:
        continue

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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


ans = 0
visited = [0]*n
for i in range(len(p)):
    if visited[p[i]-1] == 1:
        continue

    if uf.size(p[i]-1) == 1:
        if p[i]-1 == i: ans += 1
        visited[i]==1
    else:
        loop = uf.members(p[i]-1)
        visited[i]=1
        for l in loop:
            if p[l]-1 in loop:ans += 1
            visited[l] = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
q = deque([])

def get_root(i):
    while True:
        if parent[i] == -1:
            return i
        i = parent[i]

def bfs(i):
    global l
    c = 0
    q.append(i)
    while True:
        if len(q) == 0:
            break
        p = q.popleft()
        l.append(p)
        c += 1
        if not children[p] == -1:
            for j in children[p]:
                q.append(j)
    return c

n, m = map(int, input().split())
p = list(map(int, input().split()))
parent = [-1] * n
children = [-1] * n
d = [0] * n
root = []
rank = []
num = ["a"] * n
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if num[x] == "a":
        num[x] = [y]
    else:
        num[x].append(y)
    if num[y] == "a":
        num[y] = [x]
    else:
        num[y].append(x)
    if d[x] == d[y] == 0:
        root.append(x)
        rank.append(1)
        children[x] = [y]
        parent[y] = x
        d[x] = 1
        d[y] = 1
    elif d[x] == 1 and d[y] == 0:
        r = get_root(x)
        children[r].append(y)
        parent[y] = r
        d[y] = 1
    elif d[x] == 0 and d[y] == 1:
        r = get_root(y)
        children[r].append(x)
        parent[x] = r
        d[x] = 1
    else:
        s = get_root(x)
        t = get_root(y)
        if not s == t:
            i = rank[root.index(s)]
            j = rank[root.index(t)]
            if i >= j:
                parent[t] = s
                children[s].append(t)
                if i == j:
                    rank[root.index(s)] += 1
            else:
                parent[s] = t
                children[t].append(s)

ans = 0
for i in range(n):
    if parent[i] == -1 and children[i] != -1:
        l = []
        bfs(i)
        p0 = list(l)
        for j in l:
            pp = p[j] - 1
            p0.append(pp)
        k = len(p0)
        ans += k - len(set(p0))
    elif parent[i] == -1:
        if p[i] - 1 == i:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
q = deque([])

def get_root(i):
    while True:
        if parent[i] == -1:
            return i
        i = parent[i]

def bfs(i):
    global l
    c = 0
    q.append(i)
    while True:
        if len(q) == 0:
            break
        p = q.popleft()
        l.append(p)
        c += 1
        if not children[p] == -1:
            for j in children[p]:
                q.append(j)
    return c

n, m = map(int, input().split())
p = list(map(int, input().split()))
parent = [-1] * n
children = [-1] * n
d = [0] * n
root = []
rank = []
num = ["a"] * n
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if num[x] == "a":
        num[x] = [y]
    else:
        num[x].append(y)
    if num[y] == "a":
        num[y] = [x]
    else:
        num[y].append(x)
    if d[x] == d[y] == 0:
        root.append(x)
        rank.append(1)
        children[x] = [y]
        parent[y] = x
        d[x] = 1
        d[y] = 1
    elif d[x] == 1 and d[y] == 0:
        r = get_root(x)
        children[r].append(y)
        parent[y] = r
        d[y] = 1
    elif d[x] == 0 and d[y] == 1:
        r = get_root(y)
        children[r].append(x)
        parent[x] = r
        d[x] = 1
    else:
        s = get_root(x)
        t = get_root(y)
        if not s == t:
            i = rank[root.index(s)]
            j = rank[root.index(t)]
            if i >= j:
                parent[t] = s
                children[s].append(t)
                if i == j:
                    rank[root.index(s)] += 1
            else:
                parent[s] = t
                children[t].append(s)

ans = 0
for i in range(n):
    if parent[i] == -1 and children[i] != -1:
        l, p0 = [], []
        bfs(i)
        for j in l:
            pp = p[j] - 1
            p0.append(pp)
        l = l + p0
        k = len(l)
        ans += k - len(set(l))
    elif parent[i] == -1:
        if p[i] - 1 == i:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
q = deque([])

def get_root(i):
    while True:
        if parent[i] == -1:
            return i
        i = parent[i]

def bfs(i):
    global l
    c = 0
    q.append(i)
    while True:
        if len(q) == 0:
            break
        p = q.popleft()
        l.append(p)
        c += 1
        if not children[p] == -1:
            for j in children[p]:
                q.append(j)
    return c

n, m = map(int, input().split())
p = list(map(int, input().split()))
parent = [-1] * n
children = [-1] * n
d = [0] * n
root = []
rank = []
num = ["a"] * n
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if num[x] == "a":
        num[x] = [y]
    else:
        num[x].append(y)
    if num[y] == "a":
        num[y] = [x]
    else:
        num[y].append(x)
    if d[x] == d[y] == 0:
        root.append(x)
        rank.append(1)
        children[x] = [y]
        parent[y] = x
        d[x] = 1
        d[y] = 1
    elif d[x] == 1 and d[y] == 0:
        r = get_root(x)
        children[r].append(y)
        parent[y] = r
        d[y] = 1
    elif d[x] == 0 and d[y] == 1:
        r = get_root(y)
        children[r].append(x)
        parent[x] = r
        d[x] = 1
    else:
        s = get_root(x)
        t = get_root(y)
        if not s == t:
            i = rank[root.index(s)]
            j = rank[root.index(t)]
            if i >= j:
                parent[t] = s
                children[s].append(t)
                if i == j:
                    rank[root.index(s)] += 1
            else:
                parent[s] = t
                children[t].append(s)

ans = 0
for i in range(n):
    if parent[i] == -1 and children[i] != -1:
        l = []
        bfs(i)
        for j in l:
            if p[j] - 1 in l:
                ans += 1
    elif parent[i] == -1:
        if p[i] - 1 == i:
            ans += 1
print(ans)