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:
from collections import defaultdict
n, m=map(int, input().split())
p=[int(s)-1 for s in input().split()]
pair=[[int(s)-1 for s in input().split()] for _ in range(m)]

avl=defaultdict(list)
for pi in pair:
    avl[pi[0]].append(pi[1])
    avl[pi[1]].append(pi[0])

def trv(src, dst, alr=[]):
    ans=False
    if src==dst or dst in avl[src]:
        return True
    for a in avl[src]:
        if a not in alr:
            alr.append(a)            
            ans|=trv(a, dst, alr)
    return ans

cnt=0
for i in range(n):
    if trv(p.index(i), i, []):
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ps = [int(p) for p in input().split()]
xys = [tuple(map(int, input().split())) for _ in range(m)]
 
union = {node:node for node in range(n)}
 
def root(node):
    if union[node] == node:
        return node
    union[node] = root(union[node])
    return union[node]
 
for x, y in xys:
    union[root(x)] = root(y)
 
print(sum(root(i+1) == root(p) for i, p in enumerate(ps)))

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
p_list = list(map(int, input().split()))
x_list = []
y_list = []


def get_reachable_nodes(current, _reachable_nodes, _edge_list):
    candidate_nodes = _edge_list[current]
    if all([j in _reachable_nodes for j in candidate_nodes]):
        return _reachable_nodes

    for j in candidate_nodes:
        if j not in _reachable_nodes:
            next_reachable_nodes = _reachable_nodes.copy()
            next_reachable_nodes.append(j)
            _reachable_nodes.extend(get_reachable_nodes(j, next_reachable_nodes, _edge_list))
    return list(set(_reachable_nodes))


for i in range(m):
    x, y = list(map(int, input().split()))
    x_list.append(x)
    y_list.append(y)

edge_list = [[] for i in range(n)]
for i in range(m):
    edge_list[x_list[i] - 1].append(y_list[i] - 1)
    edge_list[y_list[i] - 1].append(x_list[i] - 1)

reachable_nodes_list = [get_reachable_nodes(i, [], edge_list) for i in range(n)]
reachable_nodes_set = []
for reachable_nodes in reachable_nodes_list:
    if reachable_nodes not in reachable_nodes_set and len(reachable_nodes) > 0:
        reachable_nodes_set.append(reachable_nodes)
reachable_nodes_list = reachable_nodes_set
# print(reachable_nodes_list)

a = 0
for reachable_nodes in reachable_nodes_list:
    for node in reachable_nodes:
        if p_list[node] - 1 in reachable_nodes:
            a += 1
# print('a = %s'%(a))
all_reachable_nodes = []
for reachable_nodes in reachable_nodes_list:
    all_reachable_nodes.extend(reachable_nodes)

unreachable_nodes = [i for i in range(n) if i not in all_reachable_nodes]

b = 0
for node in unreachable_nodes:
    if p_list[node]-1 == node:
     b += 1
# print('b = %s'%(b))
print(a+b)

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 union(self, x, y):

        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x

            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):

        return self.find(x) == self.find(y)


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

union = UnionFind(N)
for x,y in xy:
    union.union(x-1,y-1)

for i in p:
    if union.same_check(p[i-1]-1,i-1):
        result += 1

print(result)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n)]
        # 木の高さを格納する（初期状態は0）
        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 union(self, x, y):
        """併合"""
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        """同じ集合に属するか判定"""
        return self.find(x) == self.find(y)


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

union = UnionFind(N)
for x,y in xy:
    union.union(x-1,y-1)

for i in p:
    if union.same_check(p[i-1]-1,i-1):
        result += 1

print(result)

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 全てのノードを-1(root)として初期化
    def __init__(self,n):
        self._roots = [-1 for _ in range(n)]

    # vのrootを探索
    def find(self,v):
        if self._roots[v] == -1 : return v
        else : return self.find(self._roots[v])

    # グラフの結合
    def union(self,f,t):
        f_r = self.find(f)
        t_r = self.find(t)

        # 同一rootの場合
        if t_r == f_r:
            self._roots[f_r] = self._roots[t_r]
        else:
            self._roots[f_r] = t_r

    # iとjが同一グラフ内にあるか
    def is_same(self,i,j):
        return self.find(i) == self.find(j)

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

t = UnionFind(n)

xy = tuple(tuple(int(i) for i in input().split()) for _ in range(m))


for side in xy:
    t.union(side[0]-1,side[1]-1)


total = 0

for i,j in enumerate(p):
    total += t.is_same(i,j-1)

print(total)

Submission status: Runtime Error

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

par = [i for i in range(n)]
#rootの計算量は、parが最初の状態に近いほど値は小さくて、高々O(n)
def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
		return

for i in range(m):
	x, y = map(int, input().split())
	merge(x-1, y-1)
	print(par)

ans = 0

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

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
sigma = list(map(int, input().split()))
gokans = []

for i in range(M):
    pair = list(map(int, input().split()))
    gokans.append(pair)

def connected(i, j, paths, chains):
    old_chain = []
    if i == 1:
        for pair in chains:
            paths.remove(pair)
    narabi = [couple[0] for couple in chains] + [couple[1] for couple in chains]
    if j in narabi:
        return True

    while chains != old_chain:
        old_chain = chains
        for pair in chains:
            new_chain = [couple for couple in paths if set(couple) & set(pair) != set()]
            chains += new_chain
            for pair in new_chain:
                paths.remove(pair)
        narabi = [couple[0] for couple in chains] + [couple[1] for couple in chains]
        if j in narabi:
            return True
    return False

count = 0
chain = []
for i in range(1, N+1):
    if i != sigma[i-1]:
        gokans1 = gokans.copy()
        chain += [pair for pair in gokans if i in pair]
        if ([pair for pair in gokans if i in pair] != []) and [pair for pair in paths if sigma[i-1] in pair] and connected(i, sigma[i-1], gokans1, chain):
            count += 1
    else:
        count += 1

print(count)

Submission status: Runtime Error

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

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

def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		return
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += rank[x]
		else:
			par[x] = y
			rank[x] += rank[y]
	return

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

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
p = list(map(int, input().split()))
par = list(range(n))
rank = [0 for x in range(n)]

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		pass
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += rank[x]
		else:
			par[x] = y
			rank[x] += rank[y]
	pass

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

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
p = list(map(int, input().split()))
par = list(range(n))
rank = [0 for x in range(n)]

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		pass
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += 1
		else:
			par[x] = y
			rank[x] += 1
	pass

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

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
p = list(map(int, input().split()))
par = list(range(n))
rank = [0 for x in range(n)]

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		pass
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += 1
		else:
			par[x] = y
			rank[x] += 1
	pass

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

ans = 0

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

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = map(int, input().split())
p = list(map(int, input().split()))
par = np.arange(n)
rank = np.zeros(n)

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		pass
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += 1
		else:
			par[x] = y
			rank[x] += 1
	pass

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

ans = 0

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

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = map(int, input().split())
p = np.array(list(map(int, input().split())))
p = p-1
q = np.zeros((m,2), dtype='uint32')
for i in range(m):
	q[i] = list(map(int, input().split()))
q=q-1
par = np.arange(n)
rank = np.zeros(n)

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		pass
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += 1
		else:
			par[x] = y
			rank[x] += 1
	pass

for x,y in q:
	merge(x,y)

ans = 0

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

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = map(int, input().split())
p = np.array(list(map(int, input().split())))
p = p-1
q = np.zeros((m,2), dtype='uint32')
for i in range(m):
	q[i] = list(map(int, input().split()))
q=q-1
par = np.arange(n)

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
	pass

for x,y in q:
	merge(x,y)

tree = dict()
tree2 = dict()

for i in range(n):
	tree.setdefault(root(i), set())
	tree2.setdefault(root(i), set())
	tree[root(i)].add(i) 
	tree2[root(i)].add(p[i])

ans = 0

for value, value2 in zip(tree.values(), tree2.values()):
	ans += len(value & value2)

print(ans)

Submission status: Runtime Error

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

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

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


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))
 
Swap.sort(key=lambda x:x[0])

for i in range(M):
    if (Group[Swap[i][1]],Group[Swap[i][0]])!=(min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])):
        Group[Swap[i][1]],Group[Swap[i][0]]=min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])
        print(Group)

Swap.reverse()

for i in range(M):
    if (Group[Swap[i][1]],Group[Swap[i][0]])!=(min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])):
        Group[Swap[i][1]],Group[Swap[i][0]]=min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])
        print(Group)


count=0

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


print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

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

A = np.identity(N, dtype=int)
for i in range(M):
    x_i, y_i = map(int, input().split())
    A[x_i-1][y_i-1] = 1
    A[y_i-1][x_i-1] = 1

B = A
for i in range(N + 1):
    B = np.dot(B, A)

for i in range(N):
    for j in range(N):
        if B[i][j] > 0:
            B[i][j] = j + 1

count = 0

for i in range(N):
    if B[i][P[i]-1]:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
class UnionFind:
  def __init__(self, n):
    self.table = [-1 for _ in range(n)]
    
  def root(self, x):
    if self.table[x] < 0:
      return x
    else:
      return self.table[x] = self.root(self.table[x])
  
  def unite(self, x, y):
    s1, s2 = self.root(x), self.root(y)
    if s1 != s2:
      if self.table[s1] != self.table[s2]:
        if self.table[s1] < self.table[s2]:
          self.table[s2] = s1
        else:
          self.table[s1] = s2
      else:
        self.table[s1] += -1
        self.table[s2] = s1
    return
  
  def find Set(self, x, y):
    return self.root(x) == self.root(y)
uf = UnionFind(N)
for i in range(M):
  px, py = map(int, input().split())
  px -= 1
  py -= 1
  uf.unite(px, py)
ans = 0
for i, v in enumerate(p):
  if uf.findSet(i,v):
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = map(int, input().split())
p = np.array(list(map(int, input().split())))
p = p-1
q = np.zeros((m,2), dtype='uint32')
for i in range(m):
	q[i] = list(map(int, input().split()))
q=q-1
par = np.arange(n)

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
	pass

for x,y in q:
	merge(x,y)

tree = dict()
tree2 = dict()

for i in range(n):
	tree.setdefault(root(i), set())
	tree2.setdefault(root(i), set())
	tree[root(i)].add(i) 
	tree2[root(i)].add(p[i])

ans = set()

for value, value2 in zip(tree.values(), tree2.values()):
	ans = ans | value & value2

print(len(ans))

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = map(int, input().split())
p = np.array(list(map(int, input().split())))
p = p-1
q = np.zeros((m,2), dtype='uint32')
for i in range(m):
	q[i] = list(map(int, input().split()))
q=q-1
print(p)
print(q)
par = np.arange(n)
print(par)

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
	pass

for x,y in q:
	merge(x,y)

tree = dict()
tree2 = dict()

for i in range(n):
	tree.setdefault(root(i), set())
	tree2.setdefault(root(i), set())
	tree[root(i)].add(i) 
	tree2[root(i)].add(p[i])

print(par)

ans = set()

for value in tree.items():
	print(value)

for item in tree2.items():
	print(item)


for value, value2 in zip(tree.values(), tree2.values()):
	ans = ans | value & value2

print(len(ans))

Submission status: Runtime Error

Solution code:

from collections import defaultdict

from copy import deepcopy


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


def dp(start, to, used):
    cused = deepcopy(used)
    if start == to:
        return True
    if start in x_y:
        is_ok = False
        for next_start in x_y[start]:
            if not next_start in used:
                #remove used
                used.append(next_start)
                if dp(next_start, to, cused):
                    return True
        return is_ok

    else:
        return False




x_y = defaultdict(lambda:set())
for _ in range(m):
    x, y = map(int, input().split())
    x_y[x].add(y)
    x_y[y].add(x)



count = 0
for index in range(len(p)):
    start = index + 1
    to = p[index]
    used = []
    if dp(start, to, used):
        # 交換可能
        count += 1
print(count)

Submission status: Runtime Error

Solution code:

from collections import defaultdict



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

def dp(start, to, used):
    if start == to:
        return True
    if start in x_y:
        is_ok = False
        for next_start in x_y[start]:
            if not next_start in used:
                #remove used
                used.append(next_start)
                if dp(next_start, to, used):
                    return True
        return is_ok

    else:
        return False




x_y = defaultdict(lambda:set())
for _ in range(m):
    x, y = map(int, input().split())
    x_y[x].add(y)
    x_y[y].add(x)


count = 0
for index in range(len(p)):
    start = index + 1
    to = p[index]
    used = []
    if dp(start, to, used):
        # 交換可能
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
M, N = map(int, input().split())
p = list(map(int, input().split()))
pairs = []
for i in range(0,N):
    pairs.append(list(map(int, input().split())))
allset= set(range(1,M+1))
score = 0
while (allset):
    n = {allset.pop()}
    for j in range(0,2)
    	for i in pairs:
        	if (n & set(i)):
            	n = n | set(i)
           		pairs.remove(i)
    for i in list(n):
        if p[i-1] in n:
            score += 1
    allset = (allset - (allset & n))
print(score)

Submission status: Runtime Error

Solution code:

from collections import defaultdict



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

def dp(start, to, used):
    if start == to:
        return True
    if start in x_y:
        is_ok = False
        for next_start in x_y[start]:
            if not next_start in used:
                #remove used
                used.append(next_start)
                if dp(next_start, to, used):
                    return True
        return is_ok

    else:
        return False




x_y = defaultdict(lambda:set())
for _ in range(m):
    x, y = map(int, input().split())
    x_y[x].add(y)
    x_y[y].add(x)


count = 0
for index in range(len(p)):
    start = index + 1
    to = p[index]
    used = []
    if dp(start, to, used):
        # 交換可能
        p[start-1] ,p[to -1] = p[to -1] ,p[start -1] 
        count += 1
print(count)

Submission status: Runtime Error

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=list(range(M))

Y[0]=Y[0]|Swap[0]
Unstacked.remove(0)
j=0
k=0

while True:
    while Unstacked !=[]:
        s=Unstacked[j]

        if Y[k] & Swap[s] !=set():

            Y[k]=Y[k]|Swap[s]
            Unstacked.remove(s)
            #print(Y,j,Unstacked)
            j=0

        elif j <len(Unstacked)-1:
            j+=1

        else: break

    if Unstacked != []:
        
        k+=1
        Y[k]=Swap[Unstacked[0]]
        Unstacked.remove(Unstacked[0])

    else:
        break


#print(Y,j,k,Unstacked)

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]
    #print(l,Y,Other)

#print(Other)

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            #print(i,j,P[j-1],Y[i])
            count+=1
        

for m in Other:
    if P[m-1]==m:
        #print(m)
        count+=1

print(count)

Submission status: Runtime Error

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
for i in range(0, m):
    e = list(map(int, input().split()))
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            c.append(e[1])
        elif e[1] in c:
            c.append(e[0])
    if len(do) == 0:
        cG.append(e)

res = 0
bebe = [-1] * n
for i, c in enumerate(cG):
    for e in c:
        bebe[e - 1] = i

for i in range(n):
    if bebe[i] == bebe[p[i] - 1]:
        re += 1

print(res)

Submission status: Runtime Error

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
for i in range(0, m):
    e = list(map(int, input().split()))
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            c.append(e[1])
        elif e[1] in c:
            c.append(e[0])
    if len(do) == 0:
        cG.append(e)

res = 0
bebe = [-1] * n
for c, i in enumerate(cG):
    for e in c:
        bebe[e - 1] = i

for i in range(n):
    if bebe[i] == bebe[p[i] - 1]:
        re += 1

print(res)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n+1)]
group = [0]*n+1
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p,1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += group[num]-group[i]
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n)]
group = [-1]*n
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x-1].append(y)
    graph[y-1].append(x)
for i, num in enumerate(p):
    space = [i]
    for point in space:
        if group[point]+1:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n)]
group = [0]*n
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x-1].append(y)
    graph[y-1].append(x)
for i, num in enumerate(p):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i+1
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n)]
group = [0]*n
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i+1
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()];a.insert(0,0)
p = [int(i) for i in range(n+1)]
def f(x):return p[x] if p[x]==x else f(p[x])
def u(x,y):p[f(x)]=f(y)
xy = [u(*[int(i) for i in input().split()]) for _ in range(m)]
out = [f(i+1)==f(a[i+1]) for i in range(n)]
print(sum(out))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()];a.insert(0,0)
p = [int(i) for i in range(n+1)]
f = lambda x: p[x] if p[x]==x else f(p[x])
def u(x,y):p[f(x)]=f(y)
xy = [u(*[int(i) for i in input().split()]) for _ in range(m)]
out = [f(i+1)==f(a[i+1]) for i in range(n)]
print(sum(out))

Submission status: Runtime Error

Solution code:
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  belongs = [[] for i in range(n)]
  
  def get_root(x):
    p = pare_inds[x]
    if p == x:
      return (x, 0)
    a = get_root(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = get_root(x), get_root(y)
    if r_x < r_y:
      pare_inds[y] = r_x
      pare_inds[r_y] = r_x
    else:
      pare_inds[x] = r_y
      pare_inds[r_x] = r_y
  
  for i in range(n):
    belongs[get_root(i)].append(i)
  
  ans = 0
  for lst in belongs:
    for i in lst:
      if plst[i] - 1 in lst:
        ans += 1
  
  print(ans)
solve()

Submission status: Runtime Error

Solution code:
global visited,num,graph

def dfs(subtree):
    global visited,num,graph
    if visited[subtree] != 0:
        return

    visited[subtree] = num
    for node in graph[subtree]:
        if visited[node] != 0:
            continue
        dfs(node)

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

starting = list(map(int,input().split()))
graph = [[] for x in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [0 for x in range(N+1)]
num = 1
for i in range(1,N+1):
    if visited[i] == 0:
        dfs(i)
        num += 1

ans = 0
for i in range(1,N+1):
    if visited[i] == visited[starting[i-1]]:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())		# 5 7
P = list( map(int, input().split()) )	# 1 2 3 4 5 ...


L=[[0] for i in range(n+1)]
X=[0 for i in range(n+1)]

def solve(x,y):
	#print("solve  :", x,y,)
	if (x==0) or (y==0): return 0
	
	if x==y: return 1

	if X[x]>0: return 0
	X[x]=1
	
	#print("L[x]=", L[x])
	for a in L[x]:
		#print("a,y=", a,y)
		#return 0
		i = solve(a,y)
		if i == 1: return 1
	
	return 0



for i in range(m):
	x, y = map(int, input().split())		# 5 7
	if x>y: x,y=y,x
	L[x].append(y)
	L[y].append(x)
	

#print(n,m)
#print("P", P)
#print("L", L)
#print("X", X)


ans=0
for i, x in enumerate(P):
	X=[0 for i in range(n+1)]
	#print(i,x)
	j = solve(i+1,x)
	#print("i,x,j=", i,x,j)
	#print("")
	ans += j


print(ans)

Submission status: Runtime Error

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

for i in range(m):
    for j in range(1,m-i):
            if a[i][0] == a[i+j][0] and [a[i][1],a[i+j][1]] not in a:
                a.append([a[i][1],a[i+j][1]])
            elif a[i][1] == a[i+j][1] and [a[i][0],a[i+j][0]] not in a:
                a.append([a[i][0],a[i+j][0]])
            elif a[i][0] == a[i+j][1] and [a[i][1],a[i+j][0]] not in a:
                a.append([a[i][1],a[i+j][0]])
            elif a[i][1] == a[i+j][0] and [a[i][0],a[i+j][1]] not in a:
                a.append([a[i][0],a[i+j][1]])

for i in range(len(a)):
    for j in range(1,len(a)-i):
            if a[i][0] == a[i+j][0] and [a[i][1],a[i+j][1]] not in a:
                a.append([a[i][1],a[i+j][1]])
            elif a[i][1] == a[i+j][1] and [a[i][0],a[i+j][0]] not in a:
                a.append([a[i][0],a[i+j][0]])
            elif a[i][0] == a[i+j][1] and [a[i][1],a[i+j][0]] not in a:
                a.append([a[i][1],a[i+j][0]])
            elif a[i][1] == a[i+j][0] and [a[i][0],a[i+j][1]] not in a:

for j in range(m):
    for i in a:
        if p[i[0]-1] != i[0] and p[i[1]-1] != i[1]:
            b = p[i[0]-1]
            p[i[0]-1] = p[i[1]-1]
            p[i[1]-1] = b
print(p)

Submission status: Runtime Error

Solution code:
s = input()
z = int(input())
list = [chr(i) for i in range(97,97+26)]
d = []
flag = 0
for j in list:
  indexes = [i for i,x in enumerate(s) if x==j]
  if len(indexes)==0:
    continue
  for k in indexes:
    for l in range(len(s)-k):
      d.append(s[k:l+k+1])
  if len(d)==k:
    break
print(sorted(set(d))[z-1])

Submission status: Runtime Error

Solution code:
col = input().split()
n = int(col[0])
m = int(col[1])

p = [int(i) for i in input().split()]

xy = []
for i in range(0, m):
    xy.append(input().split())

xy2 = []
for i in xy:
    i[0] = int(i[0])
    i[1] = int(i[1])
    if i[0] > i[1]:
        i[0], i[1] = i[1], i[0]
    xy2.append((i[0], i[1]))

for i in range(0, len(xy2)):
    for j in range(i+1, len(xy2)):
        if xy2[i][1] == xy2[j][0]:
            xy2.append((xy2[i][0], xy2[j][1]))

xy3 = list(set(xy2))

for i in xy3:
    if i[0] == p[i[1]-1] and i[1] == p[i[0]-1]:
        p[i[0]-1], p[i[1]-1] == p[i[1]-1], p[i[0]-1]
    elif i[0] == p[i[1]-1] and i[1] != p[i[0]-1]:
        p[i[0]-1], p[i[1]-1] == p[i[1]-1], p[i[0]-1]
    elif i[0] != p[i[1]-1] and i[1] == p[i[0]-1]:
        p[i[0]-1], p[i[1]-1] == p[i[1]-1], p[i[0]-1]

count = 0
for i in p:
    if i+1 == p[i]:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
import time
import copy
N=int(input())
M=int(input())
p=[]
for i in range(N):
    p.append(int(input()))
x=[]
y=[]
for i in range(M):
    x.append(int(input()))
    y.append(int(input()))
k=0
max=0
def dfs(x,y,p,N,M,k,max):
    if k==M-1:
        maxx=0
        for i in range(N):
            if p[i]==i+1:
                maxx=maxx+1
        if max<=maxx:
            max=maxx
        return max
    if k<M-1:
        dfs(x,y,p,N,M,k+1,max)
        s=copy.deepcopy(p)
        aa=p[x[k]]
        bb=p[y[k]]
        s[x[k]]=bb
        s[y[k]]=aa
        dfs(x,y,s,N,M,k+1,max)
aaa=dfs(x,y,p,N,M,k,max)
print(aaa)