Problem:


Score : 400 points

Problem Statement

We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N.
We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M).
AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i = i is maximized:

Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.

Find the maximum possible number of i such that p_i = i after operations.

Constraints

2 ≤ N ≤ 10^5

1 ≤ M ≤ 10^5

p is a permutation of integers from 1 through N.

1 ≤ x_j,y_j ≤ N

x_j ≠ y_j

If i ≠ j, \{x_i,y_i\} ≠ \{x_j,y_j\}.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the maximum possible number of i such that p_i = i after operations.

Sample Input 1

5 2
5 3 1 4 2
1 3
5 4

Sample Output 1

2

If we perform the operation by choosing j=1, p becomes 1 3 5 4 2, which is optimal, so the answer is 2.

Sample Input 2

3 2
3 2 1
1 2
2 3

Sample Output 2

3

If we perform the operation by, for example, choosing j=1, j=2, j=1 in this order, p becomes 1 2 3, which is obviously optimal.
Note that we may choose the same j any number of times.

Sample Input 3

10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

Sample Output 3

8

Sample Input 4

5 1
1 2 3 4 5
1 5

Sample Output 4

5

We do not have to perform the operation. 



Sample input:
5 2
5 3 1 4 2
1 3
5 4


Sample output:
2

Submission status: Wrong Answer

Solution code:
class UnionFindSet:
    def __init__(self):
        self.dic = dict()

    def find(self, x):
        if x not in self.dic:
            return x
        else:
            self.dic[x] = self.find(self.dic[x])
            return self.dic[x]

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx != fy:
            self.dic[fx] = fy

n, m = map(int, input().split())
p = [None] + list(map(int, input().split()))
s = UnionFindSet()
for _ in range(m):
    x, y = map(int, input().split())
    s.union(p[x], p[y])
for i in range(n, 0, -1):
    if s.find(i) == s.find(p[i]):
        print(i)
        break

Submission status: Wrong Answer

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]:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
cGT = []
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])
            cGT.append(e[1])
        elif e[1] in c:
            c.append(e[0])
            cGT.append(e[0])
    if len(do) == 0:
        cG.append(e)
        cGT = cGT + e

cGT = set(cGT)
res = 0
for i in list(set(p) - cGT):
    if p[i - 1] == i:
        res = res + 1
for c in cG:
    res += len(list(filter(lambda x: p.index(x) + 1 in c, c)))
print(res)

Submission status: Wrong Answer

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
cGT = []
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])
            cGT.append(e[1])
        elif e[1] in c:
            c.append(e[0])
            cGT.append(e[0])
    if len(do) == 0:
        cG.append(e)
        cGT = cGT + e

cGT = set(cGT)
res = 0
for i in list(set(p) - cGT):
    if p[i - 1] == i:
        res = res + 1

for c in cG:
    res += len(list(filter(lambda x: p.index(x) in c, c)))
print(res)

Submission status: Wrong Answer

Solution code:
#入力関係
nm = list(map(int,input().split()))
N = nm[0]
M = nm[1]
p = list(map(int,input().split()))
xy = []
for i in range(M):
    xy_ = tuple(map(int,input().split()))
    xy.append(xy_)

#順列pのp[i]=iとなるiの数を数える関数
def count00():
    cnt00 = 0
    for i in range(N):
        if i+1==p[i]:
            cnt00+=1
    return cnt00

#順列pの場所を交換する関数
def swap(a,x,y):
    a[x],a[y] = a[y],a[x]

#操作をしてp[i]=iとなるiの数を数える関数
def count01():
    cnt01 = 0
    for j in range(N):
        if j+1==p[j]:
            cnt01+=1
    return cnt01

def judge():
    if cnt00<cnt01:
        return 1
    else:
        return 0

for i in range(M):
    cnt00 = count00()
    swap(p,xy[i][0]-1,xy[i][1]-1)
    cnt01 = count01()
    judge()
    if judge()==1:
        cnt00=cnt01
    elif judge()==0:
        break
print(cnt00)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[]]*(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: Wrong Answer

Solution code:
n,m = (int(i) for i in input().split())
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
for i,j in x: unite(i,j)
ans = 0
for i,j in enumerate([0]+p):
	if root(i)==root(j): ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = (int(i) for i in input().split())
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
for i,j in x: unite(i,j)
ans = 0
for i,j in enumerate(p):
	if root(i)==root(j): ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
cGT = []
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])
            cGT.append(e[1])
            break
        elif e[1] in c:
            c.append(e[0])
            cGT.append(e[0])
            break
    cG.append(e)
    cGT = cGT + e

cant = list(set(p) - set(cGT))
res = 0
for i in cant:
    if p[i - 1] == i:
        res = res + 1

for i in range(1, n + 1):
    for c in cG:
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1
print(res)

Submission status: Wrong Answer

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

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

uf = UnionFind(N)

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

Ans = 0
for i,p in enumerate(P):
    Ans += 1 if uf.check(i,p) else 0

print(Ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def spam(xys):
    while True:
        for i in range(len(xys) - 1):
            a = xys[i]
            b = xys[i + 1]
            if set(a) & set(b):
                xys.remove(a)
                xys.remove(b)
                xys.append(list(set(a) | set(b)))
                break
        else:
            break


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ps = [int(x) for x in stdin.readline().rstrip().split()]
    xys = [[int(x) for x in stdin.readline().rstrip().split()]
           for _ in range(M)]
    spam(xys)
    result = 0
    for item in xys:
        foo = set([ps[i - 1] for i in item]) & set(item)
        if foo:
            result += len(foo)
    xys2 = [flatten for inner in xys for flatten in inner]
    for i in [x for x in range(1, N + 1) if not x in xys2]:
        if (ps[i - 1] == i):
            result += 1
    print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin


def spam(xys):
    while True:
        for i in range(len(xys) - 1):
            a = xys[i]
            b = xys[i + 1]
            if set(a) & set(b):
                xys.remove(a)
                xys.remove(b)
                xys.append(list(set(a) | set(b)))
                break
        else:
            break


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ps = [int(x) for x in stdin.readline().rstrip().split()]
    xys = [[int(x) for x in stdin.readline().rstrip().split()]
           for _ in range(M)]
    spam(xys)
    print(xys)
    result = 0
    for item in xys:
        foo = set([ps[i - 1] for i in item]) & set(item)
        if foo:
            result = max(result, max(foo))
    print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,M=map(int, raw_input().split())
p=map(int, raw_input().split())

#print "p:",p

a = []
for i in range(M):
	x,y=map(int,raw_input().split())
	if x<=y: a.append((x-1,y-1))
	else: a.append((y-1,x-1))

a=sorted(a, key=lambda x: x[0])


#Union Find
par=[ i for i in range(N) ]

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

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


def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	elif x<=y:
		par[y]=x
	else:
		par[x]=y


for x,y in a:
	if not same(x,y):
		unite(x,y)

#print "gr:",par

C=set(par)


ans=0
for gr in C:
	num=defaultdict(lambda: 0)

	for idx,i in enumerate(par):
		if i==gr:
			num[ p[idx] ]=1


	for idx,i in enumerate(par):
		if i==gr and num[idx+1]==1:
			ans+=1
print ans

Submission status: Wrong Answer

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

a = []
for i in range(M):
	x,y=map(int,raw_input().split())
	if x<=y: a.append((x-1,y-1))
	else: a.append((y-1,x-1))

a=sorted(a, key=lambda x: x[0])

#Union Find
par=[ i for i in range(N) ]

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

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


def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	elif x<=y:
		par[y]=x
	else:
		par[x]=y


for x,y in a:
	if not same(x,y):
		unite(x,y)


C=set(par)

D=[]
E=[]
for gr in C:
	tmp=set()
	tmp2=set()
	for idx,i in enumerate(par):
		if i==gr:
			tmp.add(p[idx])
			tmp2.add(idx+1)
	D.append( (tmp,tmp2) )


ans=0
for x,y in D:
	ans+=len(x&y)
    
print ans

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = list(map(int,input().split()))
d = {}
dl = []
XY = []
j = 0
for i in range(M):
    x,y = map(int,input().split())
    if x not in d and y not in d:
        d[x] = j
        d[y] = j
        add = True
    if x not in d:
        d[x] = d[y]
    if y not in d:
        d[y] = d[x]
    if d[x] != d[y]:
        s = dl[d[x]].union(dl[d[y]])
        dl[d[x]] = s
        dl[d[y]] = s
    if add:
        dl.append({x,y})
        j += 1
        add = False
    else:
        dl[d[x]] = dl[d[x]].union({x,y})

t = 0
for i in range(N):
    if p[i]==i+1:
        t += 1
    elif i+1 in d:
        if p[i] in dl[d[i+1]]:
            t += 1
print(t)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N, M = map(int, input().split(' '))
Ps = list(map(int, input().split(' ')))
Points = [list(map(int, input().split(' '))) for _ in range(M)]
Parent = []
for p in Points:
    for par in Parent:
        if p[0] in par or p[1] in par:
            par.add(p[0])
            par.add(p[1])
            break
    else:
        Parent.append(set(p))
flag = 0
while flag == 0:
    if len(Parent) >= 2: p = Parent.pop(0)
    else: break
    for i in range(len(Parent)):
        if p & Parent[i] != set([]):
            Parent[i] = Parent[i] | p
            break
        else:
            Parent.append(p)
    else:
        flag = 1
cnt = 0
for par in Parent:
    for p in par:
        if Ps[p-1] in par: cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
p = list(map(int, input().split()))
link = [-1 for _ in range(N + 1)]
group_cnt = 0
for _ in range(M):
    x, y = map(int, input().split())
    if link[x] == -1 and link[y] == -1:
        link[x] = group_cnt
        link[y] = group_cnt
        group_cnt += 1
    elif link[x] == -1 or link[y] == -1:
        if link[x] != -1:
            link[y] = link[x]
        else:
            link[x] = link[y]
    else:
        a = 1
        for idx, v in enumerate(link, 0):
            if v == a:
                link[idx] = link[x]

cnt = 0
for idx, v in enumerate(p, 1):
    if idx == v:
        cnt += 1
    elif link[idx] == link[v]:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N,M=map(int,raw_input().split(' '))
p=map(int,raw_input().split(' '))

gr=[]
for _ in range(M):
  x,y=map(int,raw_input().split(' '))
  if len(gr)==0:
    gr.append(set([x,y]))
  else:
    il=[]
    for i in range(len(gr)):
      if x in gr[i] or y in gr[i]:
        il.append(i)

    if len(il)==0:
      gr.append(set([x,y]))
    elif len(il)==1:
      gr[il[0]] = gr[il[0]]|set([x,y])
    else:
      i_ = il[0]
      gr[i_]=gr[i_]|set([x,y])
      for i in il[1:]:
        gr[i_] = gr[i_]|gr[i]

      c=0
      for i in il[1:]:
        del gr[i-c]
        c+=1



r_=0
for i in range(len(p)):
  if i==p[i]-1:
    r_+=1

r=0
for g in gr:
  s=set()
  for n in g:
    s.add(p[n-1])
  r += len(g&s)

print max(r,r_)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = list(map(int,input().split()))
d = {}
dl = []
XY = []
j = 0
for i in range(M):
    x,y = map(int,input().split())
    if x not in d and y not in d:
        d[x] = j
        d[y] = j
        add = True
    if x not in d:
        d[x] = d[y]
    if y not in d:
        d[y] = d[x]
        
    if add:
        dl.append({x,y})
        j += 1
        add = False
    else:
        dl[d[x]] = dl[d[x]].union({x,y})

t = 0
for i in range(N):
    if p[i]==i+1:
        t += 1
    elif i+1 in d:
        if p[i] in dl[d[i+1]]:
            t += 1
print(t)

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())

print(1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(2000000000)


class Node:
    def __init__(self, index):
        self.index = index
        self.neighbors = set()

    def __repr__(self):
        return '{}: {}'.format(self.index, self.neighbors)


def can_go_to_dst(nodes, src_index, dst_index, past_indices):
    if nodes[src_index] is None:
        return False

    neighbor_indices = nodes[src_index].neighbors - past_indices
    if dst_index in neighbor_indices:
        return True

    return any(
        [can_go_to_dst(nodes, ni, dst_index, past_indices | {src_index})] for ni
        in neighbor_indices)


# line_index = 0
#
# def input():
#     global line_index
#     lines = ['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']
#
#     line = lines[line_index]
#     line_index += 1
#     return line


if __name__ == '__main__':
    N, M = map(int, input().split())

    p = []
    desirable_swaps = []
    for i, s in enumerate(input().split()):
        s_value = int(s) - 1
        if i != s_value:
            desirable_swaps.append((s_value, i))

    nodes = [None] * N
    for _ in range(M):
        xy_str = input().split()
        x, y = int(xy_str[0]) - 1, int(xy_str[1]) - 1
        if nodes[x] is None:
            nodes[x] = Node(x)
        if nodes[y] is None:
            nodes[y] = Node(y)

        nodes[x].neighbors |= {y}
        nodes[y].neighbors |= {x}

    first_n_equals = N - len(desirable_swaps)

    n_op_equals = 0
    for src_index, dst_index in desirable_swaps:
        if can_go_to_dst(nodes, src_index, dst_index, set()):
            n_op_equals += 1

    answer = first_n_equals + n_op_equals
    if answer % 2 == 1:
        answer -= 1
    print(answer)
    # print(desirable_swaps)
    # print(nodes)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = [int(i) for i in input().split()]
swaps = []
[swaps.append([int(i) for i in input().split()]) for j in range(M)]


canmoves = []
for swap in swaps:
    for i in range(len(canmoves)):
        if swap[0] in canmoves[i]:
            if swap[1] not in canmoves[i]:
                canmoves[i].append(swap[1])
                break
            else:
                break
        elif swap[1] in canmoves[i]:
            if swap[0] not in canmoves[i]:
                canmoves[i].append(swap[0])
                break
    else:
        canmoves.append(swap)

ans = 0
for i in range(N):
    if p[i] == i+1:
        ans += 1
    else:
        for canmove in canmoves:
            if p[i] in canmove and i+1 in canmove:
                ans += 1
                break

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def check(pi):
    result = 0
    for i, x in enumerate(pi):
        if i + 1 == x:
            result = x
    return result


def spam(xyi):
    for i in range(len(xyi) - 1):
        a = xyi[i]
        b = xyi[i + 1]
        if set(a) & set(b):
            xyi.remove(a)
            xyi.remove(b)
            xyi.append(list(set(a) | set(b)))
            return True
    return False


def check_max(pi, item):
    result = 0
    a = [pi[i - 1] for i in item]
    a = set(a) & set(item)
    if not a:
        return 0

    return max(list(a))


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    pi = [int(x) for x in stdin.readline().rstrip().split()]
    xyi = [[int(x) for x in stdin.readline().rstrip().split()]
           for _ in range(M)]
    while True:
        result = spam(xyi)
        if not result:
            break
    result = 0
    for item in xyi:
        result = max(result, check_max(pi, item))
    print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,raw_input().split(' '))
p=map(int,raw_input().split(' '))

gr=[]
for _ in range(M):
  x,y=map(int,raw_input().split(' '))
  if len(gr)==0:
    gr.append(set([x,y]))
  else:
    il=[]
    for i in range(len(gr)):
      if x in gr[i] or y in gr[i]:
        il.append(i)

    if len(il)==0:
      gr.append(set([x,y]))
    elif len(il)==1:
      gr[il[0]] = gr[il[0]]|set([x,y])
    else:
      i_ = il[0]
      for i in il[1:]:
        gr[i_] = gr[i_]|gr[i]

      c=0
      for i in il[1:]:
        del gr[i-c]
        c+=1



r_=0
for i in range(len(p)):
  if i==p[i]-1:
    r_+=1

r=0
for g in gr:
  s=set()
  for n in g:
    s.add(p[n-1])
  r += len(g&s)

print max(r,r_)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def check(pi):
    result = 0
    for i, x in enumerate(pi):
        if i + 1 == x:
            result = x
    return result


def spam(xyi):
    for i in range(len(xyi) - 1):
        a = xyi[i]
        b = xyi[i + 1]
        if set(a) & set(b):
            xyi.remove(a)
            xyi.remove(b)
            xyi.append(list(set(a) | set(b)))
            return True
    return False


def check_max(pi, item):
    result = 0
    a = [pi[i - 1] for i in item]
    a = set(a) | set(item)
    if not a:
        return 0

    return max(list(a))


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    pi = [int(x) for x in stdin.readline().rstrip().split()]
    xyi = [[int(x) for x in stdin.readline().rstrip().split()]
           for _ in range(M)]
    while True:
        result = spam(xyi)
        if not result:
            break
    result = 0
    for item in xyi:
        result = max(result, check_max(pi, item))
    print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
p = list(map(int,input().split()))
l=[]
for i in range(m):
    _x=list(map(int,input().split()))
    l.append(_x)
not_out = True
while not_out:
    f = False
    for a in l:
        if p[a[0]-1]==a[1] or p[a[1]-1]==a[0]:
            t = p[a[0]-1]
            p[a[0]-1] = p[a[1]-1]
            p[a[1]-1] = t
            f = True
    if f == False:
        not_out = False

c = 0
for i,b in enumerate(p):
    if b == i+1:
        c+=1
print(c)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
xy = [sorted([int(i) for i in input().split()]) for _ in range(m)]
count = 0
for i in range(n):
    if p[i]!=i+1:
        if p[i] in [j[0]*(j[0]!=i)+j[1]*(j[1]!=i) for j in xy if i in j]:
            count += 1
    else:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html

class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


N, M = [int(i) for i in input().split()]
p = [int(i) - 1 for i in input().split()]

uf = UnionFind3(N + 1)
for i in range(M):
    x, y = [int(i)-1 for i in input().split()]
    uf.union(x, y)

count = 0
for i in range(N):
    if p[i] != i:
        if uf.find(p[i]) == uf.find(i):
            count += 1
            pi = p[i]
            ppi = p[pi]
            p[i], p[pi] = ppi, pi
    else:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
pairs = []
for i in range(0, m):
    pairs.append(list(map(int, input().split())))
cG = []
for e in pairs:
    aru = False
    do = []
    for c in cG:
        if e[0] in c:
            aru = True
            c.append(e[1])
        if e[1] in c:
            aru = True
            c.append(e[0])
    if not aru:
        cG.append(e)
for e in pairs:
    ax = []
    bx = []
    for c in cG:
        if e[0] in c:
            ax = c
        if e[1] in c:
            bx = c
    if not ax == bx:
        cG.remove(ax)
        cG.remove(bx)
        cG.append(ax + bx)

cant = []
for i in range(1, n + 1):
    cc = False
    for c in cG:
        if i in c:
            cc = True
            break
    if not cc:
        cant.append(i)

res = 0
for c in cG:
    for i in range(1, n + 1):
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1

for i in cant:
    if p[i - 1] == i:
        res = res + 1
print(res)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
P = list(map(int,input().split()))
X,Y = [],[]
for i in range(M):
    x,y = map(int,input().split())
    X.append(x-1)
    Y.append(y-1)
T = [-1]*N
group = 0
for i in range(M):
    if T[X[i]] == -1 and T[Y[i]] == -1:
        T[X[i]] = group
        T[Y[i]] = group
        group += 1
    elif T[X[i]] != -1 and T[Y[i]] != -1:
        minG = min(T[X[i]],T[Y[i]])
        maxG = max(T[X[i]],T[Y[i]])
        for i in range(N):
            if T[i] == maxG:
                T[i] = minG
    else:
        if T[X[i]] == -1 and T[Y[i]] != -1:
            T[X[i]] = T[Y[i]]
        if T[Y[i]] == -1 and T[X[i]] != -1:
            T[Y[i]] = T[X[i]]
uniqueT = list(set(T))
uniqueT.sort()
ansT = [[] for _ in range(len(uniqueT))]
ansP = [[] for _ in range(len(uniqueT))]
for i in range(len(uniqueT)):
    if i != -1:
        for j in range(N):
            if T[j] == uniqueT[i]:
                ansT[i].append(j)
                ansP[i].append(P[j]-1)
Ans = 0
for i in range(len(uniqueT)):
    Ans += len(list(set(ansT[i]) & set(ansP[i])))
for i in range(N):
    if T[i] == -1 and P[i]-1 == i:
        Ans += 1
print(Ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
P = list(map(int,input().split()))
X,Y = [],[]
for i in range(M):
    x,y = map(int,input().split())
    X.append(x-1)
    Y.append(y-1)
T = [-1]*N
group = 0
for i in range(M):
    if T[X[i]] == -1 and T[Y[i]] == -1:
        T[X[i]] = group
        T[Y[i]] = group
        group += 1
    elif T[X[i]] != -1 and T[Y[i]] != -1:
        minG = min(T[X[i]],T[Y[i]])
        maxG = max(T[X[i]],T[Y[i]])
        for i in range(N):
            if T[i] == maxG:
                T[i] = minG
    else:
        if T[X[i]] == -1 and T[Y[i]] != -1:
            T[X[i]] = T[Y[i]]
        if T[Y[i]] == -1 and T[X[i]] != -1:
            T[Y[i]] = T[X[i]]
uniqueT = list(set(T))
uniqueT.sort()
ansT = [[] for _ in range(len(uniqueT))]
ansP = [[] for _ in range(len(uniqueT))]
for i in range(len(uniqueT)):
    for j in range(N):
        if T[j] == uniqueT[i]:
            ansT[i].append(j)
            ansP[i].append(P[j]-1)
Ans = 0
for i in range(len(uniqueT)):
    Ans += len(list(set(ansT[i]) & set(ansP[i])))
print(Ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = list(map(int,input().split()))
d = {}
XY = []
for i in range(M):
    x,y = map(int,input().split())
    XY.append((x,y))
    if x not in d:
        d[x] = {x,y}
    if y not in d:
        d[y] = {x,y}
    s = d[x].union(d[y])
    d[x] = s
    d[y] = s
for j in range(3):
    for i in range(M):
        x,y = XY[i]
        if x not in d:
            d[x] = {x,y}
        if y not in d:
            d[y] = {x,y}
        s = d[x].union(d[y])
        d[x] = s
        d[y] = s
t = 0
for i in range(N):
    if p[i]==i+1:
        t += 1
    elif i+1 in d:
        if p[i] in d[i+1]:
            t += 1
print(t)

Submission status: Wrong Answer

Solution code:
import itertools
n,m = map(int, input().split())
p = list(map(int, input().split()))
x_y = [list(map(int, input().split())) for i in range(m)]
key = [i for i in range(m)]
sum = 0
for i in range(n):
    if i+1==p[i]:
        sum += 1
if sum == n:
    print(sum)
    quit()
update = True
while update:
    update = False
    i = 1
    while i < len(x_y):
        for j in range(len(x_y[i])):
            if x_y[i][j] in x_y[i-1]:
                update = True
                key[i] = key[i-1]
                x_y[i-1] += x_y[i]
                x_y[i-1] = list(set(x_y[i-1]))
                if len(x_y) == 1:
                    break
                del x_y[i]
                i -= 1
        i += 1
lis = []
for i in x_y:
    if len(i) != 0:
        lis += list(itertools.permutations(i))

for i in lis:
    i = list(i)
    v = [i+1 for i in range(n)]
    for j in i:
        v.remove(j)
    for j in v:
        i.insert(j-1,j)
    count = 0
    for j in range(len(i)):
        if j+1 == p[i[j]-1]:
            count += 1
    sum = max(sum, count)
print(sum)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = list(map(int,input().split()))
d = {}
XY = []
for i in range(M):
    x,y = map(int,input().split())
    XY.append((x,y))
    if x not in d:
        d[x] = {x,y}
    if y not in d:
        d[y] = {x,y}
    s = d[x].union(d[y])
    d[x] = s
    d[y] = s
for j in range(3):
    for i in range(M):
        x,y = XY[i]
        if x not in d:
            d[x] = {x,y}
        if y not in d:
            d[y] = {x,y}
        s = d[x].union(d[y])
        d[x] = s
        d[y] = s
t = 0
for i in range(N):
    if i+1 in d:
        if p[i] in d[i+1] or p[i]==i:
            t += 1
print(t)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = list(map(int,input().split()))
d = {}
XY = []
for i in range(M):
    x,y = map(int,input().split())
    XY.append((x,y))
    if x not in d:
        d[x] = {x,y}
    if y not in d:
        d[y] = {x,y}
    s = d[x].union(d[y])
    d[x] = s
    d[y] = s
for j in range(10):
    for i in range(M):
        x,y = XY[i]
        if x not in d:
            d[x] = {x,y}
        if y not in d:
            d[y] = {x,y}
        s = d[x].union(d[y])
        d[x] = s
        d[y] = s
t = 0
for i in range(N):
    if i+1 in d:
        if p[i] in d[i+1]:
            t += 1
print(t)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = [0]*N
Origin = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK[i] = 1
        Origin.append(i)
ans = 0
for i in range(N):
    c = 0
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = Origin.copy()
        Enable.append(i)
        T = OK.copy()
        T[P[i]] = 1
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    T[P[j]] = 1
                    S.append(j)
        Enable = list(set(Enable))
        for j in Enable:
            if T[j] == 1:
                c += 1
        ans = max(ans, c)

print(ans)