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:
N, M = list(map(int, input().split()))
P    = list(map(int, input().split()))

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

for m in range(M):
    x, y = list(map(int, input().split()))
    flag = False
    for i in range(len(G)):
        for j in range(len(G)):
            if (x-1) in G[i] and (y-1) in G[j]:
                G[i] = G[i] + G[j]
                G[j] = []
                flag = True
                break
        if flag:
            break

while True:
    try:
        G.remove([])
    except:
        break

r = 0

for i in range(N):
    for g in G:
        if i in g:
            if i+1 in [P[j] for j in g]:
                r += 1

print(r)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
p = [0] + list(map(int, input().split()))
union = [0] * (n + 1)
tm = 1
for i in range(m):
  x,y = map(int, input().split())
  if 0 in (union[x], union[y]):
    k = max(union[x], union[y])
    if k > 0:
      union[x] = union[y] = k
    else:
      union[x] = union[y] = tm
      tm += 1
  elif union[x] != union[y]:
    union = [union[x] if i == union[y] else i for i in union]
print(sum([1 if union[p[i]] == union[i] else 0 for i in range(1,n+1)]))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)


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

a = [int(x) for x in input().split()]

d = {}
for _ in range(m):
    x = input()
    t = [int(x) for x in x.split()]
    d.setdefault(t[0],[])
    d[t[0]].append(t[1])
    d.setdefault(t[1],[])
    d[t[1]].append(t[0])



def search(n,o,g,visited):
    l = d.get(n,[])

    if n == g:
        return True

    if l==[]:
        return False
    if g in l:
        return True

    target = set(l) - visited

    for nn in target:
        if nn in visited:
            continue
        else:
            if nn not in d[o]:
                d.get(o,[]).append(nn)
            if o not in d[nn]:
                d.get(nn,[]).append(o)
            visited.add(nn)
        if search(nn,o,g,visited):
            return True
        else:
            return False
    return False

count=0   
for i, n in enumerate(a):
    visited = set([n])
    if search(n,n,i+1,visited):
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)


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

a = [int(x) for x in input().split()]

d = {}
for _ in range(m):
    x = input()
    t = [int(x) for x in x.split()]
    d.setdefault(t[0],[])
    d[t[0]].append(t[1])
    d.setdefault(t[1],[])
    d[t[1]].append(t[0])



def search(n,o,g,visited):
    l = d.get(n,[])

    if l==[]:
        return False
    if g in l:
        return True


    target = list(set(l) & set(visited))

    for nn in target:
        if nn in visited:
            continue
        else:
            visited.add(nn)

        for v in visited:
            if nn not in d[v]:
                d.get(v,[]).append(nn)
            if v not in d[nn]:
                d.get(nn,[]).append(v)
        if search(nn,o,g,visited):
            return True
    return False

count=0   
for i, n in enumerate(a):
    visited = set([n])
    if search(n,n,i+1,visited):
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)


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

a = [int(x) for x in input().split()]

d = {}
for _ in range(m):
    x = input()
    t = [int(x) for x in x.split()]
    d.setdefault(t[0],[])
    d[t[0]].append(t[1])
    d.setdefault(t[1],[])
    d[t[1]].append(t[0])



def search(n,o,g,visited):
    l = d.get(n,[])

    if l==[]:
        return False
    if g in l:
        return True


    target = list(set(l)-set(visited))

    for nn in target:
        if nn in visited:
            continue
        else:
            visited.add(nn)

        for v in visited:
            if nn not in d[v]:
                d.get(v,[]).append(nn)
            if v not in d[nn]:
                d.get(nn,[]).append(v)
        if search(nn,o,g,visited):
            return True
    return False

count=0   
for i, n in enumerate(a):
    visited = set([n])
    if search(n,n,i+1,visited):
        count+=1
print(count)

Submission status: Wrong Answer

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

t = []
pt = []
ans = 0

for i in range(m):
  x, y = map(int, input().split())
  for j in range(len(t)):
    if x in t[j] or y in t[j]:
      t[j].add(x)
      t[j].add(y)
      pt[j].add(p[x-1])
      pt[j].add(p[y-1])
      continue
  t.append({x, y})
  pt.append({p[x-1], p[y-1]})
  p[x-1] = -1
  p[y-1] = -1

for i in range(len(t)):
  ans += len(t[i]&pt[i])

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

print(ans)

Submission status: Wrong Answer

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

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

def connected(i, j, paths, chain_i, chain_j):
    if [pair for pair in paths if i in pair] and [pair for pair in paths if j in pair]:
        new_chain_i = [pair for pair in paths if i in pair]
        new_chain_j = [pair for pair in paths if j in pair]
        for pair in set(new_chain_i + new_chain_j):
            paths.remove(pair)
        chain_i += new_chain_i
        chain_j += new_chain_j

        narabi_i = set([couple[0] for couple in chain_i] + [couple[1] for couple in chain_i])
        narabi_j = set([couple[0] for couple in chain_j] + [couple[1] for couple in chain_j])
        if narabi_i & narabi_j != set():
            return True

        while new_chain_i and new_chain_j:
            new_chain_i_kari = []
            new_chain_j_kari = []

            for pair in new_chain_i:
                new_chain_i_kari += [couple for couple in paths if set(couple) & set(pair) != set()]
            for pair in new_chain_j:
                new_chain_j_kari += [couple for couple in paths if set(couple) & set(pair) != set()]
            new_chain_i = new_chain_i_kari
            new_chain_j = new_chain_j_kari
            chain_i += new_chain_i
            chain_j += new_chain_j

            for pair in set(new_chain_i + new_chain_j):
                paths.remove(pair)
            narabi_i = set([couple[0] for couple in new_chain_i] + [couple[1] for couple in new_chain_i])
            narabi_j = set([couple[0] for couple in new_chain_j] + [couple[1] for couple in new_chain_j])
            if narabi_i & narabi_j != set():
                return True
        return False
    else:
        return False

count = 0
chain1 = []
chain2 = []
for i in range(1, N+1):
    if i != sigma[i-1]:
        gokans1 = gokans.copy()
        if connected(i, sigma[i-1], gokans1, chain1, chain2):
            count += 1
    else:
        count += 1
print(count)

Submission status: Wrong Answer

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

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

def connected(i, j, paths):
    if [pair for pair in paths if i in pair] and [pair for pair in paths if j in pair]:
        chain_i = [pair for pair in paths if i in pair]
        chain_j = [pair for pair in paths if j in pair]
        print(i, j)
        print(chain_i)
        print(chain_j)
        for pair in set(chain_i + chain_j):
            paths.remove(pair)
        narabi_i = set([couple[0] for couple in chain_i] + [couple[1] for couple in chain_i])
        narabi_j = set([couple[0] for couple in chain_j] + [couple[1] for couple in chain_j])
        if narabi_i & narabi_j != set():
            return True
        new_chain_i = [0]
        new_chain_j = [1]
        while new_chain_i or new_chain_j:
            new_chain_i = []
            new_chain_j = []
            for pair in chain_i:
                new_chain_i += [couple for couple in paths if set(couple) & set(pair) != set()]
            for pair in chain_j:
                new_chain_j += [couple for couple in paths if set(couple) & set(pair) != set()]
            for pair in set(new_chain_i + new_chain_j):
                paths.remove(pair)
            print(new_chain_i)
            print(new_chain_j)
            chain_i += new_chain_i
            chain_j += new_chain_j
            narabi_i = set([couple[0] for couple in new_chain_i] + [couple[1] for couple in new_chain_i])
            narabi_j = set([couple[0] for couple in new_chain_j] + [couple[1] for couple in new_chain_j])
            if narabi_i & narabi_j != set():
                return True
        return False
    else:
        return False

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

Submission status: Wrong Answer

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 gokans if sigma[i-1] in pair] != []) and connected(i, sigma[i-1], gokans1, chain):
            count += 1
    else:
        count += 1

print(count)

Submission status: Wrong Answer

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 connected(i, sigma[i-1], gokans1, chain):
            count += 1
    else:
        count += 1

print(count)

Submission status: Wrong Answer

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 = []
    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 connected(i, sigma[i-1], gokans1, chain):
            count += 1
    else:
        count += 1

print(count)

Submission status: Wrong Answer

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 = []
    for pair in chains:
        paths.remove(pair)

    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 chain] + [couple[1] for couple in chain]
        if j in narabi:
            return True
    return False

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

print(count)

Submission status: Wrong Answer

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)
'''
table = [[]]*M
for i in range(M):
    for j in range(M):
        if (i != j) and (set(gokans[i]) & set(gokans[j]) != set()):
            table[i].append(j)
'''
gokans1 = gokans.copy()
def connected(i, j, paths):
    if [pair for pair in paths if i in pair] and [pair for pair in paths if j in pair]:
        i_start = [pair for pair in paths if i in pair]
        chain = i_start
        old_chain = []
        for pair in chain:
            paths.remove(pair)

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

table1 = [[] for _ in range(N)]
for i in range(1, N+1):
    for j in range(i+1, N+1):
        #iとjが同じ連結成分にある場合:
        if connected(i, j, gokans1):
            #print(i, j)
            table1[i-1].append(j)

for i in range(1, N+1):
       #iが孤立成分である場合とそうでないときにiを含む連結成分について、iから少なくとも
       #二つ互換が伸びているとき。
    if len([gokans[j] for j in range(M) if i in gokans[j]]) != 1:
        table1[i-1].append(i)

'''
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

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a


s = UnionFind3(N)
for i in range(N):
    for j in range(i, N):
        if x < n:
            s.union(i, n)

stop = False
not_id = [i+1 for i in range(N) if sigma[i] != i+1]
_id = [i+1 for i in range(N) if sigma[i] == i+1]
count = len(_id)

for i in range(1,N+1):
    for j in range(M):
        for k in range(M):
            if (i in gokans[j]) and (sigma[i-1] in gokans[k]) and (s.find(j) == s.find(k)) and (stop == False):
                count += 1
                stop = True
            elif 1 <= len([table[n] for n in range(M) if i in table[n]][0]) <= 2:
                count += 1
                stop = True
    stop = False
'''
count = 0
for i in range(1, N+1):
    if i < sigma[i-1]:
        if sigma[i-1] in table1[i]:
            count += 1
    elif i > sigma[i-1]:
        if i in table1[sigma[i-1]-1]:
            count += 1
    else:
        count += 1
#print(table1)
print(count)

Submission status: Wrong Answer

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)
'''
table = [[]]*M
for i in range(M):
    for j in range(M):
        if (i != j) and (set(gokans[i]) & set(gokans[j]) != set()):
            table[i].append(j)
'''
gokans1 = gokans.copy()
def connected(i, j, paths):
    if [pair for pair in paths if i in pair] and [pair for pair in paths if j in pair]:
        i_start = [pair for pair in paths if i in pair]
        chain = i_start
        old_chain = []
        for pair in chain:
            paths.remove(pair)

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

table1 = [[] for _ in range(N)]
for i in range(1, N+1):
    for j in range(i+1, N+1):
        #iとjが同じ連結成分にある場合:
        if connected(i, j, gokans1):
            print(i, j)
            table1[i-1].append(j)

for i in range(1, N+1):
       #iが孤立成分である場合とそうでないときにiを含む連結成分について、iから少なくとも
       #二つ互換が伸びているとき。
    if len([gokans[j] for j in range(M) if i in gokans[j]]) != 1:
        table1[i-1].append(i)

'''
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

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a


s = UnionFind3(N)
for i in range(N):
    for j in range(i, N):
        if x < n:
            s.union(i, n)

stop = False
not_id = [i+1 for i in range(N) if sigma[i] != i+1]
_id = [i+1 for i in range(N) if sigma[i] == i+1]
count = len(_id)

for i in range(1,N+1):
    for j in range(M):
        for k in range(M):
            if (i in gokans[j]) and (sigma[i-1] in gokans[k]) and (s.find(j) == s.find(k)) and (stop == False):
                count += 1
                stop = True
            elif 1 <= len([table[n] for n in range(M) if i in table[n]][0]) <= 2:
                count += 1
                stop = True
    stop = False
'''
count = 0
for i in range(1, N+1):
    if i < sigma[i-1]:
        if sigma[i-1] in table1[i]:
            count += 1
    elif i > sigma[i-1]:
        if i in table1[sigma[i-1]-1]:
            count += 1
    else:
        count += 1
print(count)

Submission status: Wrong Answer

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)

table = [[]]*M
for i in range(M):
    for j in range(M):
        if (i != j) and (set(gokans[i]) & set(gokans[j]) != set()):
            table[i].append(j)

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

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a


s = UnionFind3(M)
for x in range(M):
    for n in table[x]:
        if x < n:
            s.union(x, n)

stop = False
not_id = [i+1 for i in range(N) if sigma[i] != i+1]
_id = [i+1 for i in range(N) if sigma[i] == i+1]
count = len(_id)

for i in not_id:
    for j in range(M):
        for k in range(M):
            if (i in gokans[j]) and (sigma[i-1] in gokans[k]) and (s.find(j) == s.find(k)) and (stop == False):
                count += 1
                stop = True
    stop = False

print(count)

Submission status: Wrong Answer

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

Swap.sort(key=lambda x:x[1])

for i in range(M-1,-1,-1):
    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]])

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

count=0

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


print(count)

Submission status: Wrong Answer

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

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

for i in range(M-1,-1,-1):
    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]])

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

count=0

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


print(count)

Submission status: Wrong Answer

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

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

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):
    Swap[i]=set(Swap[i])

i=1
finish=M
judge=1
judge_2=0
Matome=[]

for i in range(M):
    for j in range(i):
        if Swap[i] & Swap[j] != set():
            Matome=Matome+[j]
        for k in range(len(Matome)):
            Swap[i]=Swap[i]|Swap[k]
            Swap[k]=set()

Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]

count=0

for i in range(finish):
    for j in Swap[i]:
        if P[j-1] in Swap[i]:
            count+=1

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)

Submission status: Wrong Answer

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

for i in range(M-1,-1,-1):
    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]])


count=0

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


print(count)

Submission status: Wrong Answer

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)

for i in range(M-1,-1,-1):
    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]])


count=0

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


print(count)

Submission status: Wrong Answer

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
pairs = sorted([sorted(i) for i in pairs])
while (allset):
    n = {allset.pop()}
    for i in pairs:
        if (n & set(i)):
            n = n | set(i)
            pairs.remove(i)
    for i in pairs:
        if (n & set(i)):
            n = n | set(i)
    for i in list(n):
        if p[i-1] in n:
            score += 1
    allset = (allset - (allset & n))
print(score)

Submission status: Wrong Answer

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
pairs = sorted([sorted(i) for i in pairs])
while (allset):
    n = {allset.pop()}
    for i in pairs:
        if (n  & set(i)):
            n = n | set(i)
    for i in pairs:
        if (n  & set(i)):
            n = n | set(i)
    for i in list(n):
        if p[i-1] in n:
            score += 1
    allset = (allset - (allset & n))
print(score)

Submission status: Wrong Answer

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 i in range(0,2):
        for i in pairs:
            if (n  & set(i)):
                n = n | set(i)
    for i in list(n):
        if p[i-1] in n:
            score += 1
    allset = (allset - (allset & n))
print(score)

Submission status: Wrong Answer

Solution code:
import re
from copy import deepcopy

num,man = map(int,input().split())
line = list(map(int,input().split()))
m = []
for i in range(man):
    m.append(list(map(int,input().split())))
m = [[i[0]-1,i[1]-1] for i in m]
candidate = []
def func(lis):
    candidate.append(deepcopy(lis))
    for i in m:
        lis[i[0]],lis[i[1]] = lis[i[1]],lis[i[0]]
        if(lis in candidate):
            return
        func(lis)
func(line)
line = "".join([str(i) for i in line])
n = []
for i in candidate:
    s = "".join([str(j) for j in i])
    total = 0
    for a,b in zip(sorted(line),s):
        if(a==b):
            total += 1
    n.append(total)
print(max(n))

Submission status: Wrong Answer

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 Unstacked!=[]:
    while j <len(Unstacked):

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

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

        else:
            j+=1

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


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

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
        

print(count)