Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

2 ≤ N ≤ 10^5

1 ≤ M ≤ 10^5

p is a permutation of integers from 1 through N.

1 ≤ x_j,y_j ≤ N

x_j ≠ y_j

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

5 2
5 3 1 4 2
1 3
5 4

Sample Output 1

2

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

Sample Input 2

3 2
3 2 1
1 2
2 3

Sample Output 2

3

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

Sample Input 3

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

Sample Output 3

8

Sample Input 4

5 1
1 2 3 4 5
1 5

Sample Output 4

5

We do not have to perform the operation. 



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


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))


forest = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    while forest[x] != x:
        x = forest[x]
    a = rank[x]
    
    while forest[y] != y:
        y = forest[y]
    b = rank[y]
    
    if a <= b:
        if a == b:
            rank[x] += 1
        forest[y] = x
    else:
        forest[x] = y


def Find(x):
    if forest[x] != x:
        rank[x] = 1
        forest[x] = Find(forest[x])
        return forest[x]
    else:
        return x
    
    for xi in Q:
        forest[xi] = x
        rank[xi] = 1
    
    return x

    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    x = Find(i)
    y = Find(List[i-1])
    if x == y:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))


forest = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    while forest[x] != x:
        x = forest[x]
    a = rank[x]
    
    while forest[y] != y:
        y = forest[y]
    b = rank[y]
    
    if a <= b:
        if a == b:
            rank[x] += 1
        forest[y] = x
    else:
        forest[x] = y


def Find(x):
    Q = []
    while forest[x] != x:
        x = forest[x]
        Q.append(x)
    """
    for xi in Q:
        forest[xi] = x
        rank[xi] = 1
    """
    return x

    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    x = Find(i)
    y = Find(List[i-1])
    if x == y:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))


forest = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    while forest[x] != x:
        x = forest[x]
    a = rank[x]
    
    while forest[y] != y:
        y = forest[y]
    b = rank[y]
    
    if a <= b:
        if a == b:
            rank[x] += 1
        forest[y] = x
    else:
        forest[x] = y


def Find(x):
    Q = []
    while forest[x] != x:
        x = forest[x]
        Q.append(x)
    
    for xi in Q:
        forest[xi] = x
        rank[xi] = 1

    return x

    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    x = Find(i)
    y = Find(List[i-1])
    if x == y:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))


forest = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    while forest[x] != x:
        x = forest[x]
    a = rank[x]
    
    while forest[y] != y:
        y = forest[y]
    b = rank[y]
    
    if a <= b:
        if a == b:
            rank[x] += 1
        forest[y] = x
    else:
        forest[x] = y


def Find(x,y):
    Q = []
    P = []
    while forest[x] != x:
        x = forest[x]
        Q.append(x)
            
    while forest[y] != y:
        y = forest[y]
        P.append(y)
    for xi in Q:
        forest[xi] = x
        rank[xi] = 1
    for yi in P:
        forest[yi] = y
        rank[yi] = 1
    if x == y:
        return 1
    else:
        return 0
    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    cnt += Find(i,List[i-1])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))

class Tree:
    def __init__(self,par):
        self.par = par

forest = [Tree(i) for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    while forest[x].par != x:
        x = forest[x].par
    a = rank[x]
    
    while forest[y].par != y:
        y = forest[y].par
    b = rank[y]
    
    if a <= b:
        if a == b:
            rank[x] += 1
        forest[y].par = x
    else:
        forest[x].par = y


def Find(x,y):
    Q = []
    P = []
    while forest[x].par != x:
        x = forest[x].par
        Q.append(x)
            
    while forest[y].par != y:
        y = forest[y].par
        P.append(y)
    for xi in Q:
        forest[xi].par = x
        rank[xi] = 1
    for yi in P:
        forest[yi].par = y
        rank[yi] = 1
    if x == y:
        return 1
    else:
        return 0
    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    cnt += Find(i,List[i-1])
print(cnt)

Submission status: Time Limit Exceeded

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 = {}

def addToDict(a,b):
    d.setdefault(a,set())
    d.setdefault(b,set())
    d[a].add(b)
    d[b].add(a)

for _ in range(m):
    x = input()
    t = [int(x) for x in x.split()]
    addToDict(t[0],t[1])

def addVisited(s,visited,acc):
    dif = set(s.difference(visited | acc))

    if len(dif) == 0:
        acc |= visited
        return False

    for num in dif:
        visited.add(num)
        for v in visited:
            addToDict(v,num)
        addVisited(d[num],visited,acc)




def allPath():
    acc=set()    
    for i, num in enumerate(a):
        n = i+1

        d.setdefault(n,set())
        d[n].add(n)

        visited=set([n])
        acc.add(n)
        # if n in d[n]:
        #     continue
        addVisited(d[n],visited,acc)

count=0   

allPath()

for i in range(n):
    num = i+1
    if a[num-1] in d[num]:
        count+=1
print(count)

Submission status: Time Limit Exceeded

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

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:
            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)
            visited.add(nn)
        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: Time Limit Exceeded

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

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,depth,depthM,visited):
    l = d.get(n,[])
    if n == g:
        return True
    if l==[]:
        return False

    if g in l:
        return True

    for nn in l:
        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 depth>depthM:
        #     return False
        if search(nn,o,g,depth+1,depthM,visited):
            #print("True")
            return True
    return False

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

Submission status: Time Limit Exceeded

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,depth,depthM,visited):
    l = d.get(n,[])
    if n == g:
        return True
    if l==[]:
        return False

    if g in l:
        return True

    for nn in l:
        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 depth>depthM:
        #     return False
        if search(nn,o,g,depth+1,depthM,visited):
            #print("True")
            return True
    return False

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)


n,m = [int(x) for x in input().split()]
#n,m = int(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,depth,depthM,visited):
    l = d.get(n,[])
    # print("depth")
    # print(depth)
    if n == g:
        return True
    if l==[]:
        return False
    for nn in l:
        if nn in visited:
            continue
        else:
            visited.add(nn)

        if nn == g:
            #print("true")
            return True
        
        elif nn == o:
            continue
        elif depth>depthM:
            return False
        else:
            if search(nn,o,g,depth+1,depthM,visited):
                #print("True")
                return True
    return False

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
g = []
for i in range(m):
    g.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in g:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
x =  [0]*n
for i in range(n):
  x[p[i]-1] = i+1
ans = 0
#Union find
y = [-1] * n
for i in range(0,n):
  if y[i] == -1:
    y[i] = i
  c = l[i+1]
  while len(c) > 0:
    z = c.pop()
    y[z-1] = y[i]
    for j in range(len(l[z])):
      if y[l[z][j]-1] == -1:
        c.append(l[z][j])
    
for i in range(n):
  c = x[i]
  if y[c-1] == y[i]:
    ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
p = list(map(int, input().split()))
pairs = [[int(c) for  c in l.strip().split()] for l in sys.stdin]

d1 = [set(pairs[0])]

for i in range(1,M):
  flag = -1
  for j in range(len(d1)):
    if len(d1[j] & set(pairs[i])) != 0:
      if flag != -1:
        d1[j] |= d1[flag]
        del d1[flag]
        break
      else:
        d1[j] |= set(pairs[i])
        flag = j
  if flag == -1:
    d1.append(set(pairs[i]))

ans = 0
for sub in d1:
  sub2 = {p.index(i)+1 for i in sub}
  ans += len(sub & sub2)

res = set(range(1,N+1))
for sub in d1:
  res -= sub

for c in res:
  if p[c-1] == c:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
p = list(map(int, input().split()))
pairs = [[int(c) for  c in l.strip().split()] for l in sys.stdin]

d1 = [set(pairs[0])]

for i in range(1,M):
  flag = -1
  flag2 = 0
  for j in range(len(d1)):
    if len(d1[j] & set(pairs[i])) != 0:
      if flag != -1:
        d1[j] |= d1[flag]
        del d1[flag]
        break
      else:
        d1[j] |= set(pairs[i])
        flag = j
  if flag == -1:
    d1.append(set(pairs[i]))

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self,n):
        self.par=[i for i in range(n)]
    def root(self, x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.root(self.par[x])
            return self.par[x]
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x!=y:
            self.par[x]=y

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

uf=UnionFind(n)
for pi in pair:
    uf.unite(pi[0],pi[1])

cnt=0
for i in range(n):
    if uf.same(i,p.index(i)):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

N, M = map(int, input().split())
P = [0] + list(map(int, input().split()))
XY = [list(map(int, input().split())) for i in range(M)]

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

for xy in XY:
    G[xy[0]].append(xy[1])
    G[xy[1]].append(xy[0])

searched = []
B = []
F = [0] * (1 + N)
blocknum = -1
for i, g in enumerate(G):
    if i in searched:
        continue
    blocknum += 1  # 何番目のブロックか
    stack = [i]  # 未探索
    searched_small = [i]  # 探索済
    F[i] = blocknum
    while True:
        for j in G[stack.pop()]:
            if j not in searched_small:
                stack.append(j)
                searched_small.append(j)
            F[j] = blocknum

        if len(stack) == 0:
            B.append(searched_small)
            searched.extend(searched_small)
            break

ans = -1
#print(F)
#print(B)
for i, p in enumerate(P):
    if i in [P[b] for b in B[F[i]]]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

        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

            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
for i in range(1, N+1):
    if i != sigma[i-1]:
        gokans1 = gokans.copy()
        if connected(i, sigma[i-1], gokans1):
            count += 1
    else:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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]
        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)
            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):
            count += 1
    else:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

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):
    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):
        gokans1 = gokans.copy()
        if connected(i, j, gokans1):
            table1[i-1].append(j)

count = 0
for i in range(1, N+1):
    if i < sigma[i-1]:
        if sigma[i-1] in table1[i-1]:
            count += 1
    elif i > sigma[i-1]:
        if i in table1[sigma[i-1]-1]:
            count += 1
    else:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def find(x):
    flag = False
    for i in range(len(setlist)):
        if x in setlist[i]:
            flag=True
            tmp_set={x}|setlist[i]
            setlist[i]={}
            return tmp_set
    if flag==False:
        return {x}

def unite(x,y):
    return find(x) | find(y)

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

for i in range(M):
    x,y = map(int,input().split())
    setlist.append(unite(x,y))
    if {} in setlist:
        setlist.remove({})
count=0
for i in range(len(p)):
    exist = False
    for j in setlist:
        if i+1 in j:
            if p[i] in j:
                count+=1
                exist=True
    if exist==False:
        if i+1==p[i]:
            count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

finish=M

for i in range(1,N+1):
    for j in range(finish):
        if i in Swap[j]:
            k=j
            break
    j+=1
    while j<finish:
        if i in Swap[j]:
            Swap[k]=Swap[k]|Swap[j]
            del Swap[j]
            finish-=1
            j-=1
        j+=1

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

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

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

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

for i in range(1,N+1):
    for j in range(finish):
        if i in Swap[j]:
            k=j
            break
    j+=1
    while j<finish:
        if i in Swap[j]:
            Swap[k]=Swap[k]|Swap[j]
            del Swap[j]
            finish-=1
            j-=1
        j+=1

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

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

judge=1
while judge==1:
    judge=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]])
            judge=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]])
            judge=1


count=0

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


print(count)

Submission status: Time Limit Exceeded

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]=tuple(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=[min(Group[Swap[i][0]], Group[Swap[i][1]])  if (j==Group[Swap[i][0]] or j==Group[Swap[i][1]]) else j for j in Group]

count=0

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


print(count)

Submission status: Time Limit Exceeded

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]=tuple(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=[min(Group[Swap[i][0]], Group[Swap[i][1]])  if (j==Group[Swap[i][0]] or j==Group[Swap[i][1]]) else j for j in Group]

count=0

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


print(count)

Submission status: Time Limit Exceeded

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

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

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


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

judge=1
while judge==1:
    judge=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]])
            judge=1

count=0

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


print(count)

Submission status: Time Limit Exceeded

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

judge=1
while judge==1:
    judge=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]])
            judge=1

count=0

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


print(count)

Submission status: Time Limit Exceeded

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

#print(Swap)
judge=1
while judge==1:
    judge=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]])
            judge=1

    #print(Group)

#print(Group)
#judge=1

#while judge==1:
#    judge=0
#    for i in range(2,N+1):
#        if Group[Group[i]]!=Group[i]:
#            Group[i]=Group[Group[i]]
#            judge=1
#        print(Group)

count=0

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


print(count)

Submission status: Time Limit Exceeded

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

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

Swap=[None]*M

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


i=1
finish=M
judge=1
judge_2=0


while judge==1:
    judge=0
    i=1

    while finish>1 and i <= finish-1:
        for j in range(i):
            if Swap[i] & Swap[j] != set():
                Swap[j]=Swap[i]|Swap[j]
                del Swap[i]
                judge=1
                judge_2=1
                finish-=1
                break

        if judge_2==0:
            i+=1
        else:
            judge_2=0


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)