Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

2 ≤ N ≤ 10^5

1 ≤ M ≤ 10^5

p is a permutation of integers from 1 through N.

1 ≤ x_j,y_j ≤ N

x_j ≠ y_j

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

5 2
5 3 1 4 2
1 3
5 4

Sample Output 1

2

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

Sample Input 2

3 2
3 2 1
1 2
2 3

Sample Output 2

3

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

Sample Input 3

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

Sample Output 3

8

Sample Input 4

5 1
1 2 3 4 5
1 5

Sample Output 4

5

We do not have to perform the operation. 



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


Sample output:
2

Submission status: Time Limit Exceeded

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

l = [-1 for _ in range(n)]
gn = 0
g = []

for _ in range(m):
    x,y = map(int, input().split())
    if l[x-1] == -1 and l[y-1] == -1:
        l[x-1] += 1 + gn
        l[y-1] += 1 + gn
        g.append([x,y])
        gn += 1
    elif l[x-1] != -1 and l[y-1] != -1:
        if l[x-1] == l[y-1]:
            pass
        else:
            if l[x-1]<l[y-1]:
                tmp = []+g[l[y-1]]
                for z in g[l[y-1]]:
                    l[z-1] = 0 + l[x-1]
                g[l[x-1]] += tmp
            else:
                tmp = []+g[l[x-1]]
                for z in g[l[x-1]]:
                    l[z-1] = 0 + l[y-1]
                g[l[y-1]] += tmp 
    else:
        if l[x-1] == -1:
            l[x-1] = 0+l[y-1]
            g[l[y-1]].append(x)
        else:
            l[y-1] = 0+l[x-1]
            g[l[x-1]].append(y)

ans = 0
for i in range(n):
    if p[i] == i+1:
        ans += 1
    else:
        if l[i] != -1:
            if p[i] in g[l[i]]:
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import queue

def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def main():
    N, M = lii()
    p = lii()
    p = np.array(p) - 1
    G = [set() for _ in range(N)]  # linked list of graph
    for _ in range(M):
        x, y = lii()
        G[x-1].add(y-1)
        G[y-1].add(x-1)

    visited = [0 for _ in range(N)]
    connect_list = []
    for n in range(N):
        if not visited[n]:
            c = {n}
            q = queue.Queue()
            for t in G[n]:
                q.put(t)

            while not q.empty():
                s = q.get()
                c.add(s)
                visited[s] = 1
                for t in G[s]:
                    if not t in c:
                        q.put(t)

            connect_list.append(c)

    ans = 0
    for c in connect_list:
        over = len(set(p[list(c)]).intersection(c))
        ans += over

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return 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[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

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

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return 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[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	if uf.find(x - 1) != uf.find(y - 1):
		uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return 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[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	if uf.find(x - 1) != uf.find(y - 1):
		uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return 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[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return


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

uf = UnionFind(n)

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

ans = 0
for i, pp in enumerate(p):
	if uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return 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[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return


n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]
x = [xy[i][0] for i in range(m)]
y = [xy[i][1] for i in range(m)]

uf = UnionFind(n)

for i in range(m):
	uf.union(x[i] - 1, y[i] - 1)

ans = 0
for i, pp in enumerate(p):
	if uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return 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[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return


n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]
x = [xy[i][0] for i in range(m)]
y = [xy[i][1] for i in range(m)]

uf = UnionFind(n)

for i in range(m):
	uf.union(x[i] - 1, y[i] - 1)

ans = 0
for i in range(n):
	if uf.find(p[i] - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

n,m=map(int, input().split())
p=list(map(int, input().split()))
q=list()
for i in range(m):
    q.append(set(map(int, input().split())))
count=0
while count!=5000:
    a=q.pop()
    for j in q:
        if len(j&a) != 0:
            j |=a
            count=0
            break
    else:q=[a]+q
    if count>len(q): break
    count+=1

q2=copy.copy(set(p))
for i in q:
    q2 -= i
    
count2=len([i for i in q2 if i==p[i-1]])

for i in q:
    r=list()
    for j in list(i):
        r.append(p[j-1])
    #print(i,r)
    count2 += len(i&set(r))
print(count2)

Submission status: Time Limit Exceeded

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

parent = list(range(N))
rank = [0] * N
key = [[i] for i in range(N)]
val = [[p-1] for p in P]

# union-find
def getRoot(x):
  p = parent[x]
  if p == x:
    return p
  ret = getRoot(p)
  parent[x] = ret
  return ret

def join(x, y):
  rx = getRoot(x)
  ry = getRoot(y)
  if rank[rx] < rank[ry]:
    parent[rx] = ry
    key[ry] += key[rx]
    val[ry] += val[rx]
  else:
    parent[ry] = rx
    key[rx] += key[ry]
    val[rx] += val[ry]
    if rank[rx] == rank[ry]:
      rank[rx] += 1

for _ in range(M):
  x, y = map(int, input().split())
  join(x-1, y-1)

ans = 0
for i in range(N):
  if parent[i] == i:
    ans += len(set(key[i]).intersection(set(val[i])))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = tuple(input().split(" "))
N = int(N)
M = int(M)
sList = []

pList = map(int, input().split(" "))

for i in range(M):
    x, y = map(int, input().split(" "))
    xt = None
    yt = None
    for t in sList:
        if x in t:
            xt = t
            break
    
    for t in sList:
        if y in t:
            yt = t
            break
            
    if xt == None:
        if yt == None:
            sList.append(set((x, y)))
        
        else:
            yt.add(x)
        
    else:
        if yt == None:
            xt.add(y)
        
        elif xt is not yt:
            sList.append(xt | yt)
            sList.remove(xt)
            sList.remove(yt)
    
num = 0
i = 1
for p in pList:
    if p == i:
        num += 1
    else:
        for t in sList:
            if p in t and i in t:
                num += 1
                break
    i += 1
                
print(num)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind0:
    def __init__(self, size):
        self.table = list(range(1,size+1))

    def find(self, x):
        return self.table[x-1]

    def union(self, x, y):
        x1 = self.find(x)
        y1 = self.find(y)
        if x1 == y1: return False
        # 併合
        for i in range(len(self.table)):
            if self.table[i] == y1: self.table[i] = x1
        return True

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

DF = UnionFind0(N)

for m in range(M):
    a,b = map(int,input().split())
    DF.union(a,b) #O(N)
    
ans = 0
for i in range(1,N+1):
    #現在位置のグループ＝＝その位置にいる数字くんの行きたい位置のグループ
    if DF.find(i)==DF.find(P[i-1]): ans+=1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p  = list(map(int, input().split()))
group = [-1] * (n+1)
member = []
for i in range(m):
    x, y = map(int, input().split())
    if group[x] == -1 and group[y] == -1:
        #addnewgroup
        member.append({x,y})
        group[x] = group[y] = len(member) - 1
    elif group[x] == -1:
        group[x] = group[y]
        member[group[x]].add(x)
    elif group[y] == -1:
        group[y] = group[x]
        member[group[x]].add(y)
    elif group[x] != group[y]:
            old = group[y]
            member[group[x]] |= member[group[y]]
            for m in member[old]:
                group[m] = group[x]
            member[old].clear()

ans = 0
for i in range(1, n+1):
    if group[i] == -1:
        if p[i-1] == i:
            ans += 1
    elif p[i-1] in member[group[i]]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
ALPHA = "abcdefghijklmnopqrstuvwxyz"


def solve(pi, tuples):
    # ids = {i + 1: None for i in range(len(pi))}
    leave = set(range(1, len(pi) + 1))
    connects_sets_new = {0: set()}
    aaaaa = 0
    ids = [None] * len(pi)
    for x, y in tuples:
        if x in leave:
            leave.remove(x)
        if y in leave:
            leave.remove(y)
        x, y = x - 1, y - 1
        if ids[x] is not None:
            if ids[y] is not None:
                n_from = ids[y]
                n_to = ids[x]
                if n_from != n_to:
                    s = connects_sets_new[n_to]
                    for n in connects_sets_new[n_from]:
                        ids[n] = n_to
                        s.add(n)
                    del connects_sets_new[n_from]
            else:
                ids[y] = ids[x]
                connects_sets_new[ids[x]].add(y)
        else:
            if ids[y] is not None:
                ids[x] = ids[y]
                connects_sets_new[ids[y]].add(x)
            else:
                ids[x] = aaaaa
                ids[y] = aaaaa
                connects_sets_new[aaaaa] = {x, y}
                aaaaa += 1

    res = 0
    for l in leave:
        if l == pi[l - 1]:
            res += 1

    for s in connects_sets_new.values():
        indexies = set([pi[i] - 1 for i in s])
        inter = indexies.intersection(s)
        res += len(inter)
    return res


def main():
    N, M = [int(a) for a in input().split()]
    pi = [int(a) for a in input().split()]
    tuples = [[int(a) for a in input().split()] for _ in range(M)]
    res = solve(pi, tuples)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]),int(input_raw[1])]
    p_list = []
    input_raw = read_func().strip().split()
    for i in range(N):
        p_list.append(int(input_raw[i]))
    swap_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [x, y] =  [int(input_raw[0]),int(input_raw[1])]
        if x not in swap_list:
            swap_list[x] = [y]
        else:
            swap_list[x].append(y)
        if y not in swap_list:
            swap_list[y] = [x]
        else:
            swap_list[y].append(x)

    done_list = [False for i in range(N + 1)]
    done_list[0] = True

    adj_set_list = [set([]) for i in range(N + 1)]
    
    for i in range(1, N + 1):

        if done_list[i] == True:
            continue
        nd_list = deque([i])
        while 1:
            if len(nd_list) == 0:
                break
            nd = nd_list.popleft()
            done_list[nd] = True
            adj_set_list[i].add(nd)
            adj_set_list[nd] = adj_set_list[i]
            if nd in swap_list:
                for adj in swap_list[nd]:
                    if done_list[adj] == True:
                        continue
                    nd_list.append(adj)
    count = 0
    for i in range(len(p_list)):
        if p_list[i] in adj_set_list[i + 1]:
            count += 1
    print count




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ps = list(map(int,input().split()))
lis = [[] for i in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    lis[tmp[0]-1].append(tmp[1])
    lis[tmp[1]-1].append(tmp[0])

def bfs(graph, start):
    queue = [start]
    visited = []
    while queue:
        label = queue.pop(0)
        if label not in visited:
            visited.append(label)
            queue += [x for x in graph[label - 1] if x not in visited]
    return visited

an = [bfs(lis,1)]

for i in range(2,n+1):
    flag = True
    for j in an:
        if i in j:
            flag = False
            break
    if flag:
        an += [bfs(lis,i)]


ans = 0
for i in range(n):
    for j in range(len(an)):
        if (i+1) in an[j] and ps[(i)] in an[j]:
            ans += 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]),int(input_raw[1])]
    p_list = []
    input_raw = read_func().strip().split()
    for i in range(N):
        p_list.append(int(input_raw[i]))
    swap_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [x, y] =  [int(input_raw[0]),int(input_raw[1])]
        if x not in swap_list:
            swap_list[x] = [y]
        else:
            swap_list[x].append(y)
        if y not in swap_list:
            swap_list[y] = [x]
        else:
            swap_list[y].append(x)

    done_list = [False for i in range(N + 1)]
    done_list[0] = True

    adj_set_list = [set([]) for i in range(N + 1)]
    
    for i in range(1, N + 1):
        nd_list = deque([])
        if done_list[i] == True:
            continue
        nd_list.append(i)
        while 1:
            if len(nd_list) == 0:
                break
            nd = nd_list.popleft()
            done_list[nd] = True
            adj_set_list[i].add(nd)
            adj_set_list[nd] = adj_set_list[i]
            if nd in swap_list:
                for adj in swap_list[nd]:
                    if done_list[adj] == True:
                        continue
                    nd_list.append(adj)
    count = 0
    for i in range(len(p_list)):
        if p_list[i] in adj_set_list[i + 1]:
            count += 1
    print count




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import random
import numpy as np
import time
import copy

n,m=map(int,input().split())
p=list(map(int,input().split()))
x=[]
y=[]
ave=[[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):ave[i][i]=1
for _ in range(m):
    X,Y=map(int,input().split())
    ave[X-1][Y-1]=1
    ave[Y-1][X-1]=1
    x.append(X)
    y.append(Y)
do=[]
score=0
for i in range(n):
    pi=p[i]-1
    if(ave[pi][i]==1):
        score+=1
        continue
    queue=[]
    queue.append(i)
    do=[]
    alr=[0 for _ in range(n)]
    while(queue):
        u=queue.pop(0)
        for j in range(n):
            if(i==j):continue
            if(ave[u][j]==1 and alr[j]==0):
                ave[i][j]=1
                ave[j][i]=1
                alr[j]=1
                do.append(j)
                if(j==pi):
                    score+=1
                    queue=[]
                    break
                queue.append(j)
    for d in do:
        for Z in range(n):
            if(ave[d][Z]==1 or ave[i][Z]==1):ave[d][Z]=1
                
print(score)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
p = list(map(int, input().split()))
g = [[] for _ in range(0,n+1)]
visit = [None] * (n+1)
ans = 0
for _ in range(0,m):
    x,y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)
for i in range(1,n+1):
    if visit[i] is not None:
        continue
    stack = [i]
    part = [i]
    visit[i] = 0
    while len(stack) > 0:
        q = stack.pop()
        for qq in g[q]:
            if visit[qq] is None:
                visit[qq] = 0
                part.append(qq)
                stack.append(qq)
    part2 = []
    for i in part:
        part2.append(p[i-1])
    for i in part:
        if i in part2:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import *

import time

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


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

D=[ [] for x in range(N+1)]

for i in range(M):
    x,y=map(int, raw_input().split())
    D[x].append(y)
    D[y].append(x)

t=time.time()
K=0

U=list(range( 1,N+1) )
V=[0 for u in range(N+1) ]
S=0
tmp=0
ans=0

while( len(U)>S ):
    while V[tmp+1]==1:
        tmp+=1
    c=U[tmp]
    S+=1
    V[c]=1
    a=[c]
    w=D[c]
    SS=0
    while(len(w)>SS):
        ww=w[SS]
        if not V[ww]:
            V[ww]=1
            a.append(ww)
            w += [ d for d in D[ww] if V[d]==0 ]
            S+=1
            SS+=1
    #k=time.time()
    P =set([p[i-1] for i in a])
    Q =set(a)
    ans+=len( P & Q )
    #K+=time.time()-k
print ans

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
x=[]
y=[]
ave=[[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):ave[i][i]=1
for _ in range(m):
    X,Y=map(int,input().split())
    ave[X-1][Y-1]=1
    ave[Y-1][X-1]=1
    x.append(X)
    y.append(Y)
do=[]
score=0
for i in range(n):
    pi=p[i]-1
    if(ave[pi][i]==1):
        score+=1
        continue
    queue=[]
    queue.append(i)
    do=[]
    alr=[0 for _ in range(n)]
    while(queue):
        u=queue.pop(0)
        for j in range(n):
            if(i==j):continue
            if(ave[u][j]==1 and alr[j]==0):
                ave[i][j]=1
                ave[j][i]=1
                alr[j]=1
                do.append(j)
                if(j==pi):
                    score+=1
                    queue=[]
                    break
                queue.append(j)
    for d in do:
        for Z in range(n):
            if(ave[d][Z]==1 or ave[i][Z]==1):ave[d][Z]=1
                
print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]),int(input_raw[1])]
    p_list = []
    input_raw = read_func().strip().split()
    for i in range(N):
        p_list.append(int(input_raw[i]))
    swap_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [x, y] =  [int(input_raw[0]),int(input_raw[1])]
        if x not in swap_list:
            swap_list[x] = [y]
        else:
            swap_list[x].append(y)
        if y not in swap_list:
            swap_list[y] = [x]
        else:
            swap_list[y].append(x)

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

    adj_set_list = [set([]) for i in range(N + 1)]
    
    for i in range(1, N + 1):
        nd_list = deque([])
        if done_list[i] == True:
            continue
        nd_list.append(i)
        while 1:
            if len(nd_list) == 0:
                break
            nd = nd_list.popleft()
            done_list[nd] = True
            adj_set_list[i].add(nd)
            adj_set_list[nd] = adj_set_list[i]
            if nd in swap_list:
                for adj in swap_list[nd]:
                    if done_list[adj] == True:
                        continue
                    nd_list.append(adj)
    count = 0
    for i in range(len(p_list)):
        if p_list[i] in adj_set_list[i + 1]:
            count += 1
    print count




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import random
import numpy as np
import time


n,m=map(int,input().split())
p=list(map(int,input().split()))
x=[]
y=[]
ave=[[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):ave[i][i]=1
for _ in range(m):
    X,Y=map(int,input().split())
    ave[X-1][Y-1]=1
    ave[Y-1][X-1]=1
    x.append(X)
    y.append(Y)
do=[]
score=0
for i in range(n):
    pi=p[i]-1
    if(ave[pi][i]==1):
        score+=1
        continue
    queue=[]
    queue.append(i)
    do=[]
    alr=[0 for _ in range(n)]
    while(queue):
        u=queue.pop(0)
        for j in range(n):
            if(i==j):continue
            if(ave[u][j]==1 and alr[j]==0):
                ave[i][j]=1
                ave[j][i]=1
                alr[j]=1
                do.append(j)
                if(j==pi):
                    score+=1
                    queue=[]
                    break
                queue.append(j)
                
print(score)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ps = list(map(int,input().split()))
lis = [[] for i in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    lis[tmp[0]-1].append(tmp[1])
    lis[tmp[1]-1].append(tmp[0])

def bfs(graph, start, end):
    queue = [start]
    visited = []
    while queue:
        label = queue.pop(0)
        if label == end:
            return True
        if label not in visited:
            visited.append(label)
            queue += [x for x in graph[label - 1] if x not in visited]
    return False

ans = 0
for i in range(n):
    ans += int(bfs(lis,i+1, ps[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import *

import time

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


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

D=[ [] for x in range(N+1)]

for i in range(M):
    x,y=map(int, raw_input().split())
    D[x].append(y)
    D[y].append(x)

t=time.time()
K=0

U=list(range( 1,N+1) )
V=[0 for u in range(N+1) ]
S=0
tmp=0
ans=0

while( len(U)>S ):
    tmp = V[1:].index(0)
    c=U[tmp]
    S+=1
    V[c]=1
    a=[c]
    w=D[c]
    SS=0
    while(len(w)>SS):
        ww=w[SS]
        if not V[ww]:
            V[ww]=1
            a.append(ww)
            w += [ d for d in D[ww] if V[d]==0 ]
            S+=1
            SS+=1
    P =set([p[i-1] for i in a])
    Q =set(a)
    ans+=len( P & Q )

print ans

Submission status: Time Limit Exceeded

Solution code:
ALPHA = "abcdefghijklmnopqrstuvwxyz"


def solve(pi, tuples):
    ids = {i + 1: None for i in range(len(pi))}
    aaaaa = 0
    for x, y in tuples:
        if ids[x] is not None:
            if ids[y] is not None:
                n_from = ids[y]
                n_to = ids[x]
                for n in range(1, len(pi) + 1):
                    if ids[n] == n_from:
                        ids[n] = n_to
            else:
                ids[y] = ids[x]
        else:
            if ids[y] is not None:
                ids[x] = ids[y]
            else:
                ids[x] = aaaaa
                ids[y] = aaaaa
                aaaaa += 1

    # connects_sets = []
    # for x, y in tuples:
    #     f = False
    #     for i, s in enumerate(connects_sets):
    #         if x in s or y in s:
    #             s.add(x)
    #             s.add(y)
    #             f = True
    #             break
    #     if not f:
    #         s = set()
    #         s.add(x)
    #         s.add(y)
    #         connects_sets.append(s)

    # connects_sets_new = []
    # added = set()
    # for i, s1 in enumerate(connects_sets):
    #     if i in added:
    #         continue
    #     flag = True
    #     for j, s2 in enumerate(connects_sets[i + 1:]):
    #         if len(s1.intersection(s2)) != 0:
    #             connects_sets_new.append(s1.union(s2))
    #             flag = False
    #             added.add(i)
    #             added.add(j + i + 1)
    #             break
    #     if flag:
    #         connects_sets_new.append(s1)
    #         added.add(i)

    connects_sets_new = {}
    for n in range(1, len(pi) + 1):
        if ids[n] not in connects_sets_new:
            connects_sets_new[ids[n]] = set()
        connects_sets_new[ids[n]].add(n)

    leave = connects_sets_new[None] if None in connects_sets_new else []

    res = 0
    for l in leave:
        if l == pi[l - 1]:
            res += 1

    if None in connects_sets_new:
        del connects_sets_new[None]

    for s in connects_sets_new.values():
        indexies = set([pi[i - 1] for i in s])
        inter = indexies.intersection(s)
        res += len(inter)
    return res


def main():
    N, M = [int(a) for a in input().split()]
    pi = [int(a) for a in input().split()]
    tuples = [[int(a) for a in input().split()] for _ in range(M)]
    res = solve(pi, tuples)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import *

import time

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


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

D=[ [] for x in range(N+1)]

for i in range(M):
    x,y=map(int, raw_input().split())
    D[x].append(y)
    D[y].append(x)

t=time.time()
K=0

U=list(range( 1,N+1) )
V=[0 for u in range(N+1) ]
A=[]
S=0
tmp=0
while( len(U)>S ):
    while V[tmp+1]==1:
        tmp+=1
    c=U[tmp]
    S+=1
    V[c]=1
    a=[c]
    w=D[c]
    while(len(w)!=0):
        ww=w.pop(0)
        if not V[ww]:
            V[ww]=1
            a.append(ww)
            w += [ d for d in D[ww] if V[d]==0 ]
            S+=1

    A.append(a)

tt=time.time()

ans=0
for a in A:
    P =set([p[i-1] for i in a])
    Q =set(a)
    ans+=len( P & Q )

print ans