Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has $N$ vases in a row (numbered $1$ through $N$, initially from left to right). He wants to sort them in a particular order which he finds the most beautiful. You are given a permutation $p_{1}, p_{2}, \ldots, p_{N}$ of the integers $1$ through $N$; for each valid $i$, Chef wants the $i$-th vase to end up as the $p_{i}$-th vase from the left.

In order to achieve this, Chef can swap vases. Any two vases can be swapped in $1$ minute. Chef also has a very efficient, but limited, robot at his disposal. You are given $M$ pairs $(X_{1},Y_{1}), (X_{2},Y_{2}), \ldots, (X_{M},Y_{M})$. For each valid $i$, the robot can instantly swap two vases whenever one of them is at the position $X_{i}$ and the other at the position $Y_{i}$. Note that the initial positions of the vases are irrelevant to the robot.

Formally, Chef, at any moment, may choose to perform one of the following actions, until the vases are sorted in the desired order:
Choose two indices $i$ and $j$ ($1 ≤ i, j ≤ N$) and swap the vases that are currently at the positions $i$ and $j$. It takes $1$ minute to perform this action.
Choose an integer $k$ ($1 ≤ k ≤ M$) and order the robot to swap the vases that are currently at the positions $X_{k}$ and $Y_{k}$. It takes $0$ minutes to perform this action.

Chef cannot perform multiple operations at the same time ― if he chooses to perform some operation of the first type, he has to wait for $1$ minute before performing any further operations.

What is the minimum number of minutes that Chef needs to sort the vases?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
The second line contains $N$ space-separated integers $p_{1}, p_{2}, \ldots, p_{N}$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $X_{i}$ and $Y_{i}$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum number of minutes Chef needs to sort the vases.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 18$
$0 ≤ M ≤ 18$
$1 ≤ p_{i} ≤ N$ for each valid $i$
$1 ≤ X_{i}, Y_{i} ≤ N$ for each valid $i$
$X_{i} \neq Y_{i}$ for each valid $i$
$N > 10$ holds in at most one test case

------  Subtasks ------
Subtask #1 (20 points): $M = 0$

Subtask #2 (20 points): $N ≤ 5$

Subtask #3 (60 points): original constraints

----- Sample Input 1 ------ 
3

3 1

2 3 1

2 3

5 10

2 4 5 1 3

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

4 5

4 1

3 1 4 2

1 2
----- Sample Output 1 ------ 
1

0

2
----- explanation 1 ------ 
Example case 1: Chef can ask the robot to swap the vases at the positions $2$ and $3$, and then he can swap the vases at the positions $1$ and $2$.

Example case 2: The robot can swap each pair of vases, so the answer is $0$.

Example case 3: Chef can swap the vases at the positions $1$ and $4$, then ask the robot to swap the vases at the positions $1$ and $2$, and then swap the vases at the positions $3$ and $4$, taking a total of two minutes.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Directed graphs

Dynamic programming

Data structures


Solutions:
import math
from collections import deque

def bfs(graph, vertex1):
	queue = deque([vertex1])
	visited = {vertex1: True}
	while queue:
		v = queue.popleft()
		for n in graph[v]:
			if n not in visited:
				queue.append(n)
				visited[n] = True
	return visited

class findcycles:

	def __init__(self):
		self.allcycles = []
		self.stack = []
		self.blockset = []
		self.blockmap = {}

	def unblock(self, v):
		if v in self.blockset:
			self.blockset.remove(v)
		while v in self.blockmap:
			temp = self.blockmap[v]
			del self.blockmap[v]
			if temp in self.blockset:
				self.blockset.remove(temp)
			v = temp

	def johnson(self, adj, v, start):
		foundcycle = False
		self.stack.append(v)
		self.blockset.append(v)
		for i in adj[v]:
			if i == start:
				self.stack.append(start)
				cycle = self.stack.copy()
				self.stack.pop()
				self.allcycles.append(cycle)
				foundcycle = True
			elif i not in self.blockset:
				gotcycle = self.johnson(adj, i, start)
				foundcycle = foundcycle or gotcycle
		if foundcycle:
			self.unblock(v)
		else:
			for i in adj[v]:
				self.blockmap[i] = v
		self.stack.pop()
		return foundcycle

	def ret(self):
		if len(self.allcycles) > 0:
			self.allcycles.sort(key=lambda x: len(x))
			return self.allcycles[0]
		else:
			return []
t = int(input())
for rep in range(t):
	(n, m) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	for i in range(n):
		p[i] -= 1
	adj = [[] for _ in range(n)]
	for rep2 in range(m):
		(x, y) = list(map(int, input().split()))
		if y - 1 not in adj[x - 1]:
			adj[x - 1].append(y - 1)
		if x - 1 not in adj[y - 1]:
			adj[y - 1].append(x - 1)
	c = 0
	l = []
	vis = {}
	c = 0
	for i in range(n):
		if i not in vis:
			temp = bfs(adj, i)
			l.append(temp)
			for j in temp:
				vis[j] = c
			c += 1
	adj2 = [[] for _ in range(c)]
	for i in range(n):
		if i != p[i]:
			if vis[i] != vis[p[i]]:
				adj2[vis[i]].append(vis[p[i]])
	cyc = []
	count = 0
	for i in range(len(adj2)):
		while len(adj2[i]) > 0:
			ob = findcycles()
			ob.johnson(adj2, i, i)
			cyc = ob.ret()
			for j in range(len(cyc) - 1):
				adj2[cyc[j]].remove(cyc[j + 1])
			count += len(cyc) - 2
	print(count)


for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	P = [0]
	P.extend(list(map(int, input().split())))
	xy = []
	for _ in range(M):
		xy.append(list(map(int, input().split())))
	Tree = [[] for _ in range(N + 1)]
	for (i, j) in xy:
		Tree[i].append(j)
		Tree[j].append(i)
	DjSets = []
	Used = [True]
	Used.extend([False for _ in range(N)])
	for i in range(len(Tree)):
		if Used[i]:
			continue
		pack = [i]
		for j in pack:
			for l in Tree[j]:
				if l not in pack and (not Used[l]):
					pack.append(l)
					Used[l] = True
		DjSets.append(pack)
	for i in range(len(DjSets)):
		DjSets[i].sort()
	(table, Lno) = ([[0 for _ in range(len(DjSets))] for _ in range(len(DjSets))], [-1 for _ in range(N + 1)])
	for i in range(1, N + 1):
		for j in range(len(DjSets)):
			if P[i] in DjSets[j]:
				Lno[i] = j
				break
	for i in range(len(DjSets)):
		for k in DjSets[i]:
			if Lno[k] != i:
				table[i][Lno[k]] += 1
	(res, tot) = (0, sum([sum(i) for i in table]))
	while tot > 0:
		(J, K) = (-1, -1)
		for i in range(len(table)):
			for j in range(len(table)):
				if table[i][j]:
					(J, K) = (i, j)
					break
			if J != -1:
				break
		if J == -1:
			break
		(I, All, wor) = (J, [[J, K]], [])
		for i in All:
			f = False
			for j in range(len(table)):
				if table[i[-1]][j]:
					if j == I:
						i.append(j)
						(wor, f) = (i, True)
					if j in i:
						continue
					news = [n for n in i]
					news.append(j)
					All.append(news)
			if f:
				break
		for i in range(len(wor) - 1):
			table[wor[i]][wor[i + 1]] -= 1
		res += len(wor) - 2
		tot -= len(wor) - 1
	print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = [0] + list(map(int, input().split()))
	(cor, tree, res) = ([sorted(list(map(int, input().split()))) for i in range(m)], [[] for i in p], 0)
	for (i, j) in cor:
		tree[i].append(j)
		tree[j].append(i)
	lis = sorted([p[i] for i in range(1, n + 1)])
	(vis, pic) = ([0 for i in range(n)], [])
	for j in range(len(lis)):
		if vis[j]:
			continue
		pack = [lis[j]]
		for k in pack:
			for l in tree[k]:
				if l in lis and l not in pack:
					pack.append(l)
					vis[lis.index(l)] = 1
		pic.append(pack)
	(PIC, lno) = (len(pic), [-1 for i in p])
	for j in range(PIC):
		for k in pic[j]:
			lno[k] = j
	(exc, tot) = ([[0 for i in range(PIC)] for i in range(PIC)], 0)
	for j in range(PIC):
		for k in pic[j]:
			exc[j][lno[p[k]]] += 1
	for j in range(PIC):
		exc[j][j] = 0
	for j in range(PIC):
		for k in range(j + 1, PIC):
			tot += exc[j][k] + exc[k][j]
	while tot > 0:
		(J, K) = (-1, -1)
		for j in range(PIC):
			for k in range(PIC):
				if exc[j][k]:
					(J, K) = (j, k)
					break
			if J != -1:
				break
		(I, All, wor) = (J, [[J, K]], [])
		for j in All:
			flag = 0
			for k in range(PIC):
				if exc[j[-1]][k]:
					if k == I:
						j.append(I)
						(wor, flag) = (j, 1)
						break
					if k in j:
						continue
					news = [i for i in j]
					news.append(k)
					All.append(news)
			if flag:
				break
		for i in range(len(wor) - 1):
			exc[wor[i]][wor[i + 1]] -= 1
		res += len(wor) - 2
		tot -= len(wor) - 1
	print(res)


from collections import defaultdict

def minSwaps(arr):
	n = len(arr)
	arrpos = [*enumerate(arr)]
	arrpos.sort(key=lambda it: it[1])
	vis = {k: False for k in range(n)}
	ans = 0
	for i in range(n):
		if vis[i] or arrpos[i][0] == i:
			continue
		cycle_size = 0
		j = i
		while not vis[j]:
			vis[j] = True
			j = arrpos[j][0]
			cycle_size += 1
		if cycle_size > 0:
			ans += cycle_size - 1
	return ans

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def DFSUtil(self, v, visited, shanik):
		visited[v] = True
		shanik.append(v)
		for i in self.graph[v]:
			if visited[i] == False:
				self.DFSUtil(i, visited, shanik)

	def DFS(self, v, shanik):
		visited = [False] * (max(self.graph) + 1)
		self.DFSUtil(v, visited, shanik)
javal = 1
if javal == 1:
	T = int(input())
	for _ in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		li = []
		a = input().split()
		aukat_wali_jagah = [0] * n
		for i in range(n):
			a[i] = int(a[i])
			aukat_wali_jagah[a[i] - 1] = i
		g = Graph()
		for i in range(m):
			shanik = input().split()
			li.append([int(shanik[0]), int(shanik[1])])
		li.sort()
		for i in range(m):
			shanik = li[i]
			g.addEdge(int(shanik[0]) - 1, int(shanik[1]) - 1)
			g.addEdge(int(shanik[1]) - 1, int(shanik[0]) - 1)
		flag = 0
		for i in range(n):
			g.addEdge(i, i)
		dost = []
		for i in range(n):
			shanik = []
			flag = 0
			for j in range(len(dost)):
				if i in dost[j]:
					flag = 1
					break
			if flag == 0:
				g.DFS(i, shanik)
				dost.append(shanik)
		if len(dost) == 1:
			print('0')
		elif m == 0:
			swaps = minSwaps(a)
			print(swaps)
		else:
			badlaw = []
			dontknow = []
			for i in range(n):
				for j in range(len(dost)):
					if i in dost[j]:
						shanik1 = j
					if aukat_wali_jagah[i] in dost[j]:
						shanik2 = j
				if shanik1 != shanik2:
					badlaw.append([shanik1, shanik2])
				dontknow.append([shanik1, shanik2])
			parivartan = []
			samay1 = 0
			for i in range(len(badlaw)):
				if badlaw[i] != []:
					if [badlaw[i][1], badlaw[i][0]] in badlaw:
						samay1 += 1
						t2 = badlaw.index([badlaw[i][1], badlaw[i][0]])
						badlaw[i] = []
						badlaw[t2] = []
					else:
						parivartan.append(badlaw[i])
			if len(parivartan) > 0:
				samay = samay1
				ginna = 0
				t1 = len(parivartan)
				parivartan.sort()
				for i in range(t1):
					palpal = parivartan[i][0]
					palpal2 = parivartan[i][1]
					flag = 0
					flag1 = 0
					nikal_l = []
					for k1 in range(t1):
						for j in range(t1):
							if parivartan[j][0] == palpal2:
								palpal2 = parivartan[j][1]
								flag += 1
								nikal_l.append(parivartan[j])
							if flag > 2:
								break
							if palpal2 == palpal:
								flag1 = 1
								break
						if flag1 == 1:
							break
					if flag1 == 1:
						ginna += flag
						nikal_l.append(parivartan[i])
						for i in range(len(nikal_l)):
							q = parivartan.index(nikal_l[i])
							parivartan[q] = [-1, -2]
				samay += ginna
				iskimaaka = []
				for i in range(t1):
					if parivartan[i] != [-1, -2]:
						iskimaaka.append(parivartan[i])
				parivartan = iskimaaka
				t1 = len(parivartan)
				parivartan.sort()
				ginna = 0
				for i in range(t1):
					palpal = parivartan[i][0]
					palpal2 = parivartan[i][1]
					flag = 0
					flag1 = 0
					nikal_l = []
					for k1 in range(t1):
						for k2 in range(t1):
							for j in range(t1):
								if parivartan[j][0] == palpal2:
									palpal2 = parivartan[j][1]
									flag += 1
									nikal_l.append(parivartan[j])
								if flag > 3:
									break
								if palpal2 == palpal:
									flag1 = 1
									break
							if flag1 == 1:
								break
						if flag1 == 1:
							break
					if flag1 == 1:
						ginna += flag
						nikal_l.append(parivartan[i])
						for i in range(len(nikal_l)):
							q = parivartan.index(nikal_l[i])
							parivartan[q] = [-1, -2]
				samay += ginna
				iskimaaka = []
				for i in range(t1):
					if parivartan[i] != [-1, -2]:
						iskimaaka.append(parivartan[i])
				parivartan = iskimaaka
				t1 = len(parivartan)
				parivartan.sort()
				ginna = 0
				for i in range(t1):
					palpal = parivartan[i][0]
					palpal2 = parivartan[i][1]
					flag = 0
					flag1 = 0
					nikal_l = []
					for k1 in range(t1):
						for k2 in range(t1):
							for k3 in range(t1):
								for j in range(t1):
									if parivartan[j][0] == palpal2:
										palpal2 = parivartan[j][1]
										flag += 1
										nikal_l.append(parivartan[j])
									if flag > 4:
										break
									if palpal2 == palpal:
										flag1 = 1
										break
								if flag1 == 1:
									break
							if flag1 == 1:
								break
						if flag1 == 1:
							break
					if flag1 == 1:
						ginna += flag
						nikal_l.append(parivartan[i])
						for i in range(len(nikal_l)):
							q = parivartan.index(nikal_l[i])
							parivartan[q] = [-1, -2]
				samay += ginna
				iskimaaka = []
				for i in range(t1):
					if parivartan[i] != [-1, -2]:
						iskimaaka.append(parivartan[i])
				parivartan = iskimaaka
				t1 = len(parivartan)
				ginna = 0
				for i in range(t1):
					palpal = parivartan[i][0]
					palpal2 = parivartan[i][1]
					flag = 0
					flag1 = 0
					if parivartan[i] != [-1, -2]:
						for k1 in range(t1):
							for k2 in range(t1):
								for k3 in range(t1):
									for k4 in range(t1):
										for k5 in range(t1):
											for k6 in range(t1):
												for k7 in range(t1):
													for k8 in range(t1):
														for k9 in range(t1):
															for k10 in range(t1):
																for k11 in range(t1):
																	for k12 in range(t1):
																		for k13 in range(t1):
																			for k14 in range(t1):
																				for j in range(t1):
																					if parivartan[j][0] == palpal2:
																						palpal2 = parivartan[j][1]
																						flag += 1
																						parivartan[j] = [-1, -2]
																					if palpal2 == palpal:
																						flag1 = 1
																						break
																				if flag1 == 1:
																					break
																			if flag1 == 1:
																				break
																		if flag1 == 1:
																			break
																	if flag1 == 1:
																		break
																if flag1 == 1:
																	break
															if flag1 == 1:
																break
														if flag1 == 1:
															break
													if flag1 == 1:
														break
												if flag1 == 1:
													break
											if flag1 == 1:
												break
										if flag1 == 1:
											break
									if flag1 == 1:
										break
								if flag1 == 1:
									break
							if flag1 == 1:
								break
					if flag1 == 1:
						ginna += flag
					parivartan[i] = [-1, -2]
				samay = samay + ginna
			else:
				samay = samay1
			print(samay)


from collections import defaultdict

def minSwaps(arr):
	n = len(arr)
	arrpos = [*enumerate(arr)]
	arrpos.sort(key=lambda it: it[1])
	vis = {k: False for k in range(n)}
	ans = 0
	for i in range(n):
		if vis[i] or arrpos[i][0] == i:
			continue
		cycle_size = 0
		j = i
		while not vis[j]:
			vis[j] = True
			j = arrpos[j][0]
			cycle_size += 1
		if cycle_size > 0:
			ans += cycle_size - 1
	return ans

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def DFSUtil(self, v, visited, temp):
		visited[v] = True
		temp.append(v)
		for i in self.graph[v]:
			if visited[i] == False:
				self.DFSUtil(i, visited, temp)

	def DFS(self, v, temp):
		visited = [False] * (max(self.graph) + 1)
		self.DFSUtil(v, visited, temp)
T = int(input())
for _ in range(T):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	li = []
	a = input().split()
	indices = [0] * n
	for i in range(n):
		a[i] = int(a[i])
		indices[a[i] - 1] = i
	g = Graph()
	for i in range(m):
		temp = input().split()
		li.append([int(temp[0]), int(temp[1])])
	li.sort()
	for i in range(m):
		temp = li[i]
		g.addEdge(int(temp[0]) - 1, int(temp[1]) - 1)
		g.addEdge(int(temp[1]) - 1, int(temp[0]) - 1)
	flag = 0
	for i in range(n):
		g.addEdge(i, i)
	groups = []
	for i in range(n):
		temp = []
		flag = 0
		for j in range(len(groups)):
			if i in groups[j]:
				flag = 1
				break
		if flag == 0:
			g.DFS(i, temp)
			groups.append(temp)
	if len(groups) == 1:
		print('0')
	elif m == 0:
		swaps = minSwaps(a)
		print(swaps)
	else:
		change = []
		dontknow = []
		for i in range(n):
			for j in range(len(groups)):
				if i in groups[j]:
					temp1 = j
				if indices[i] in groups[j]:
					temp2 = j
			if temp1 != temp2:
				change.append([temp1, temp2])
			dontknow.append([temp1, temp2])
		change1 = []
		time1 = 0
		for i in range(len(change)):
			if change[i] != []:
				if [change[i][1], change[i][0]] in change:
					time1 += 1
					t2 = change.index([change[i][1], change[i][0]])
					change[i] = []
					change[t2] = []
				else:
					change1.append(change[i])
		if len(change1) > 0:
			time = time1
			counting = 0
			t1 = len(change1)
			change1.sort()
			for i in range(t1):
				temporary = change1[i][0]
				tempss = change1[i][1]
				flag = 0
				flag1 = 0
				removing = []
				for k1 in range(t1):
					for j in range(t1):
						if change1[j][0] == tempss:
							tempss = change1[j][1]
							flag += 1
							removing.append(change1[j])
						if flag > 2:
							break
						if tempss == temporary:
							flag1 = 1
							break
					if flag1 == 1:
						break
				if flag1 == 1:
					counting += flag
					removing.append(change1[i])
					for i in range(len(removing)):
						q = change1.index(removing[i])
						change1[q] = [-1, -2]
			time += counting
			qwert = []
			for i in range(t1):
				if change1[i] != [-1, -2]:
					qwert.append(change1[i])
			change1 = qwert
			t1 = len(change1)
			change1.sort()
			counting = 0
			for i in range(t1):
				temporary = change1[i][0]
				tempss = change1[i][1]
				flag = 0
				flag1 = 0
				removing = []
				for k1 in range(t1):
					for k2 in range(t1):
						for j in range(t1):
							if change1[j][0] == tempss:
								tempss = change1[j][1]
								flag += 1
								removing.append(change1[j])
							if flag > 3:
								break
							if tempss == temporary:
								flag1 = 1
								break
						if flag1 == 1:
							break
					if flag1 == 1:
						break
				if flag1 == 1:
					counting += flag
					removing.append(change1[i])
					for i in range(len(removing)):
						q = change1.index(removing[i])
						change1[q] = [-1, -2]
			time += counting
			qwert = []
			for i in range(t1):
				if change1[i] != [-1, -2]:
					qwert.append(change1[i])
			change1 = qwert
			t1 = len(change1)
			change1.sort()
			counting = 0
			for i in range(t1):
				temporary = change1[i][0]
				tempss = change1[i][1]
				flag = 0
				flag1 = 0
				removing = []
				for k1 in range(t1):
					for k2 in range(t1):
						for k3 in range(t1):
							for j in range(t1):
								if change1[j][0] == tempss:
									tempss = change1[j][1]
									flag += 1
									removing.append(change1[j])
								if flag > 4:
									break
								if tempss == temporary:
									flag1 = 1
									break
							if flag1 == 1:
								break
						if flag1 == 1:
							break
					if flag1 == 1:
						break
				if flag1 == 1:
					counting += flag
					removing.append(change1[i])
					for i in range(len(removing)):
						q = change1.index(removing[i])
						change1[q] = [-1, -2]
			time += counting
			qwert = []
			for i in range(t1):
				if change1[i] != [-1, -2]:
					qwert.append(change1[i])
			change1 = qwert
			t1 = len(change1)
			counting = 0
			for i in range(t1):
				temporary = change1[i][0]
				tempss = change1[i][1]
				flag = 0
				flag1 = 0
				if change1[i] != [-1, -2]:
					for k1 in range(t1):
						for k2 in range(t1):
							for k3 in range(t1):
								for k4 in range(t1):
									for k5 in range(t1):
										for k6 in range(t1):
											for k7 in range(t1):
												for k8 in range(t1):
													for k9 in range(t1):
														for k10 in range(t1):
															for k11 in range(t1):
																for k12 in range(t1):
																	for k13 in range(t1):
																		for k14 in range(t1):
																			for j in range(t1):
																				if change1[j][0] == tempss:
																					tempss = change1[j][1]
																					flag += 1
																					change1[j] = [-1, -2]
																				if tempss == temporary:
																					flag1 = 1
																					break
																			if flag1 == 1:
																				break
																		if flag1 == 1:
																			break
																	if flag1 == 1:
																		break
																if flag1 == 1:
																	break
															if flag1 == 1:
																break
														if flag1 == 1:
															break
													if flag1 == 1:
														break
												if flag1 == 1:
													break
											if flag1 == 1:
												break
										if flag1 == 1:
											break
									if flag1 == 1:
										break
								if flag1 == 1:
									break
							if flag1 == 1:
								break
						if flag1 == 1:
							break
				if flag1 == 1:
					counting += flag
				change1[i] = [-1, -2]
			time = time + counting
		else:
			time = time1
		print(time)


import math
import random

def rotatecc(tej, rat):
	for i in range(len(rat) - 1):
		(tej[rat[i]], tej[rat[i + 1]]) = (tej[rat[i + 1]], tej[rat[i]])
	return tej

def addcc(sasi, maxcc, tej, manarr):
	for i in range(len(manarr)):
		manarr[i] = manarr[i] + 1
		tej = rotatecc(tej, sasi[i])
		if manarr[i] == maxcc[i]:
			manarr[i] = 0
		else:
			break
	return [tej, manarr]
t = int(input())
ppppp = 0
while t > 0:
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	x = len(a)
	a = list(dict.fromkeys(a))
	y = len(a)
	b = []
	rr = []
	for i in range(n + 1):
		qqq = [100000 for x in range(n + 1)]
		rr.append(qqq)
	for i in range(n + 1):
		rr[i][i] = 0
	for i in range(m):
		(x1, y1) = map(int, input().split())
		(x, y) = (min(x1, y1), max(x1, y1))
		b.append([x, y])
		rr[x][y] = 0
		rr[y][x] = 0
	a.insert(0, 0)
	for k in range(1, n + 1):
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				rr[i][j] = min(rr[i][j], rr[i][k] + rr[k][j])
	family = []
	vis = [0 for x in range(n + 1)]
	for i in range(1, n + 1):
		if vis[i] == 0:
			zzz = []
			for j in range(1, n + 1):
				if vis[j] == 0:
					if rr[i][j] < 100000:
						zzz.append(j)
						vis[j] = 1
			family.append(zzz)
	belong = [0 for x in range(n + 1)]
	for i in range(len(family)):
		for j in family[i]:
			belong[j] = i
	sasi = []
	maxcc = []
	manarr = []
	dill = 1
	for i in family:
		if len(i) > 1:
			sasi.append(i)
			maxcc.append(len(i))
			manarr.append(0)
			dill = dill * len(i)
	aa = []
	for i in range(1, n + 1):
		aa.append(i)
	eee = a.copy()
	s = 100
	vis = [0 for x in range(n + 1)]
	for qqq in range(dill):
		s1 = 0
		st = []
		eee = a.copy()
		for i in aa:
			if a[i] != i:
				st = []
				ff = [0 for x in range(len(family))]
				st.append([i, belong[i]])
				ff[belong[i]] = 1
				vis[i] = 1
				kk = i
				while a[i] != i:
					gg = a[kk]
					if ff[belong[gg]] == 0:
						vis[gg] = 1
						ff[belong[gg]] = 1
						st.append([gg, belong[gg]])
						kk = gg
					else:
						bb = belong[gg]
						fff = len(st) - 1
						mmmm = gg
						xx = 0
						vis[gg] = 1
						while st[fff][1] != bb:
							fffffff = 1
							(a[st[fff][0]], a[st[fff - 1][0]]) = (a[st[fff - 1][0]], a[st[fff][0]])
							ff[st[fff][1]] = 0
							st.pop()
							fff = fff - 1
							xx = xx + 1
						z1 = st[fff][0]
						z2 = a[st[fff][0]]
						(a[z1], a[z2]) = (a[z2], a[z1])
						s1 = s1 + xx
						kk = z1
		s = min(s, s1)
		if len(sasi) == 0:
			break
		else:
			tej = eee.copy()
			kiran = addcc(sasi, maxcc, tej, manarr)
			tej = kiran[0]
			manarr = kiran[1]
		a = tej
	print(s)
	t = t - 1


import copy
import random
from collections import deque, defaultdict
from math import inf

class UnionFind:

	def __init__(self, N):
		self.count = N
		self.id = list(range(N))

	def union(self, p, q):
		pID = self.find(p)
		qID = self.find(q)
		if pID == qID:
			return
		for i in range(len(self.id)):
			if self.id[i] == pID:
				self.id[i] = qID
		self.count -= 1

	def find(self, p):
		return self.id[p]

def find_cycle(graph):
	if not graph:
		return None
	source = random.sample(list(graph.keys()), 1)[0]
	Q = deque()
	Q.append((source,))
	visited = set()
	visited.add(source)
	cycles = []
	while Q:
		path = Q.popleft()
		node = path[-1]
		for neighbor in graph[node]:
			if neighbor == path[0]:
				cycles.append(path)
			elif neighbor not in visited:
				path0 = list(path)
				path0.append(neighbor)
				visited.add(neighbor)
				Q.append(tuple(path0))
	return random.sample(cycles, 1)[0]

def remove_cycle(graph, path):
	for i in range(len(path)):
		left = path[i]
		right = path[(i + 1) % len(path)]
		graph[left].remove(right)
		if not graph[left]:
			del graph[left]

def compute_swaps(graph):
	swaps = 0
	cycle = find_cycle(graph)
	while cycle is not None:
		if len(cycle) > 1:
			swaps += len(cycle) - 1
		remove_cycle(graph, cycle)
		cycle = find_cycle(graph)
	return swaps

def solve(arr, robots):
	target = [0 for _ in arr]
	for (n, i) in enumerate(arr):
		target[i - 1] = n + 1
	uf = UnionFind(len(arr) + 1)
	for (x, y) in robots:
		uf.union(target[x - 1], target[y - 1])
	target = tuple((uf.find(t) for t in target))
	vases = tuple((uf.find(t) for t in range(1, len(arr) + 1)))
	graph = defaultdict(list)
	for (u, v) in zip(vases, target):
		if u != v:
			graph[u].append(v)
	swaps = inf
	for _ in range(10):
		swaps = min(compute_swaps(copy.deepcopy(graph)), swaps)
	return swaps

def main():
	import sys
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		(N, M) = (int(i) for i in sys.stdin.readline().split())
		arr = [int(i) for i in sys.stdin.readline().split()]
		robots = []
		for _ in range(M):
			(x, y) = (int(i) for i in sys.stdin.readline().split())
			robots.append((x, y))
		print(solve(arr, robots))
main()


def swap_items(l, swapped, ind):
	for i in range(ind, n):
		if swapIndex[l[i]] != swapIndex[i + 1]:
			j = 0
			while j < n:
				if swapIndex[l[i]] == swapIndex[j + 1] and swapIndex[l[j]] == swapIndex[i + 1]:
					break
				j += 1
			if j < n:
				swapped += 1
				(l[i], l[j]) = (l[j], l[i])
			else:
				j = i + 1
				while j < n:
					if swapIndex[l[j]] == swapIndex[i + 1] and swapIndex[l[j]] != swapIndex[j + 1]:
						l2 = l[:]
						(l2[i], l2[j]) = (l2[j], l2[i])
						swap_items(l2, swapped + 1, i + 1)
					j += 1
	isSolved = True
	for i in range(n):
		if swapIndex[l[i]] != swapIndex[i + 1]:
			isSolved = False
			break
	if isSolved:
		swapped_all.append(swapped)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	swapped_all = []
	swaps = []
	for i in range(1, n + 1):
		swaps.append(set([i]))
	for _ in range(m):
		(s1, s2) = map(int, input().split())
		(s1i, s2i) = (-1, -1)
		i = 0
		for swap in swaps:
			if s1 in swap:
				s1i = i
			if s2 in swap:
				s2i = i
			i += 1
		if s1i == s2i:
			continue
		swap1 = swaps.pop(s1i)
		if s1i < s2i:
			swap2 = swaps.pop(s2i - 1)
		else:
			swap2 = swaps.pop(s2i)
		swaps.append(swap1 | swap2)
	swapIndex = {}
	i = 1
	for swap in swaps:
		for s in swap:
			swapIndex[s] = i
		i += 1
	swap_items(l[:], 0, 0)
	print(min(swapped_all))


rr = lambda : input().strip()
rrm = lambda : map(int, rr().split())

def solve(N, M, p):
	(group, count) = ([0] * N, 0)
	j = 1
	for i in range(M):
		(x, y) = rrm()
		if group[x - 1] + group[y - 1] == 0:
			group[x - 1] = group[y - 1] = j
			j += 1
		elif group[x - 1] == 0:
			group[x - 1] = group[y - 1]
		elif group[y - 1] == 0:
			group[y - 1] = group[x - 1]
		else:
			a = min(group[x - 1], group[y - 1])
			b = max(group[x - 1], group[y - 1])
			for k in range(N):
				if group[k] == b:
					group[k] = a
	cp = 0
	while 1:
		if cp == N:
			break
		dp = p[cp] - 1
		if p[cp] == cp + 1 or group[cp] != 0 or group[dp] != 0:
			cp += 1
			continue
		else:
			(p[dp], p[cp]) = (p[cp], p[dp])
			count += 1
	for cp in range(N):
		dp = p[cp] - 1
		if group[dp] != group[cp] and group[dp] == 0:
			(p[dp], p[cp]) = (p[cp], p[dp])
			count += 1
	cp = 0
	while 1:
		if cp == N:
			break
		dp = p[cp] - 1
		if group[cp] == group[dp]:
			cp += 1
			continue
		lis = []
		for i in range(cp + 1, N):
			if group[i] == group[dp]:
				lis.append(i)
				if group[cp] == group[p[i] - 1]:
					(p[i], p[cp]) = (p[cp], p[i])
					count += 1
					break
		else:
			for i in lis:
				c = p[i] - 1
				if group[i] != group[c]:
					(p[i], p[cp]) = (p[cp], p[i])
					count += 1
					break
	return count
T = int(rr())
for _ in range(T):
	(N, M) = rrm()
	p = list(rrm())
	ans = solve(N, M, p)
	print(ans)


import sys
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def deletearrele(arr, ele, no):
	newarr = []
	ite = 0
	for i in range(len(arr)):
		if arr[i] != ele:
			newarr.append(arr[i])
		elif ite < no:
			ite += 1
		else:
			newarr.append(arr[i])
	return newarr
for _ in range(int(ri())):
	(n, m) = Ri()
	a = Ri()
	posicidt = {}
	a = [0] + a
	for i in range(1, n + 1):
		posicidt[a[i]] = i
	par = [i for i in range(n + 1)]
	rank = [1 for i in range(n + 1)]

	def findpar(a):
		if par[a] == a:
			return a
		else:
			swaptemp = findpar(par[a])
			par[a] = swaptemp
			return swaptemp

	def disunion(a, b):
		ap = findpar(a)
		bp = findpar(b)
		if ap != bp:
			par[bp] = ap
			rank[ap] += rank[bp]
	for i in range(m):
		(x, y) = Ri()
		xp = findpar(x)
		yp = findpar(y)
		if xp != yp:
			disunion(x, y)
	ccomp = []
	cid = {}
	ite = 0
	for i in range(1, n + 1):
		if rank[findpar(i)] >= 2:
			if findpar(i) in cid:
				ccomp[cid[findpar(i)]].append(i)
			else:
				cid[findpar(i)] = ite
				ite += 1
				ccomp.append([i])
	ccomp.append([])
	for i in range(1, n + 1):
		if rank[findpar(i)] == 1:
			ccomp[-1].append(i)
	ans = 0
	i = ccomp[-1]
	for j in i:
		if a[j] != j and findpar(j) == findpar(posicidt[j]):
			disunionwant = a[j]
			want = j
			tochange = j
			tobechanged = posicidt[j]
			(a[tochange], a[tobechanged]) = (a[tobechanged], a[tochange])
			posicidt[disunionwant] = posicidt[j]
			posicidt[j] = j
			continue
		if a[j] != j and findpar(j) != findpar(posicidt[j]):
			ans += 1
			disunionwant = a[j]
			want = j
			tochange = j
			tobechanged = posicidt[j]
			(a[tochange], a[tobechanged]) = (a[tobechanged], a[tochange])
			posicidt[disunionwant] = posicidt[j]
			posicidt[j] = j
	ccomp.pop()
	ite = 0
	dp = []
	for i in ccomp:
		swaptemp = []
		for j in i:
			if cid[findpar(a[j])] != ite:
				swaptemp.append(cid[findpar(a[j])])
		dp.append(swaptemp)
		ite += 1
	for i in range(len(dp)):
		for j in range(i + 1, len(dp)):
			val1 = dp[i].count(j)
			val2 = dp[j].count(i)
			minn = min(val1, val2)
			dp[i] = deletearrele(dp[i], j, minn)
			dp[j] = deletearrele(dp[j], i, minn)
			ans += minn
	while True:
		firstele = -1
		for i in range(len(dp)):
			if len(dp[i]) != 0:
				firstele = i
				break
		if firstele == -1:
			break
		cur = firstele
		while True:
			if len(dp[cur]) > 0:
				swaptemp = dp[cur][-1]
				dp[cur].pop()
				cur = swaptemp
				if cur == firstele:
					break
				ans += 1
			else:
				break
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	a = []
	b = [0]
	count = 0
	d = [0] * (n + 1)
	for i in range(m):
		(x, y) = map(int, input().split())
		a.append((x, y))
		a.append((y, x))
	for i in range(n):
		b.append([i + 1])
		c = [i + 1]
		for j in c:
			for k in a:
				if k[0] == j:
					if k[1] not in c:
						b[i + 1].append(k[1])
						c.append(k[1])
	for i in range(n):
		d[p[i]] = i
	if m == 0:
		for i in range(n):
			x = d[i + 1]
			y = i
			if x == y:
				continue
			else:
				count += 1
				temp1 = p[x]
				temp2 = p[y]
				p[x] = p[y]
				p[y] = y + 1
				d[temp1] = y
				d[temp2] = x
	else:
		for i in range(n):
			x = d[i + 1]
			y = i
			if x == y:
				continue
			elif x + 1 in b[y + 1]:
				temp1 = p[x]
				temp2 = p[y]
				p[x] = p[y]
				p[y] = y + 1
				d[temp1] = y
				d[temp2] = x
			else:
				e = -1
				for l in b[x + 1]:
					for j in b[y + 1]:
						if l == p[j - 1]:
							e = j - 1
							break
					if e != -1:
						break
				if e != -1:
					count += 1
					temp1 = p[e]
					temp2 = p[y]
					p[e] = p[y]
					p[y] = temp1
					d[temp1] = y
					d[temp2] = e
					temp1 = p[p[y] - 1]
					temp2 = p[x]
					p[x] = temp1
					p[p[y] - 1] = temp2
					d[temp1] = x
					d[temp2] = p[y] - 1
					temp1 = p[p[y] - 1]
					temp2 = p[y]
					d[temp2] = p[y] - 1
					d[temp1] = y
					p[p[y] - 1] = temp2
					p[y] = temp1
				elif len(b[y + 1]) == 1:
					count += 1
					temp1 = p[x]
					temp2 = p[y]
					p[x] = p[y]
					p[y] = y + 1
					d[temp1] = y
					d[temp2] = x
				else:
					pass
		for i in range(n):
			x = d[i + 1]
			y = i
			if x == y:
				continue
			elif x + 1 in b[y + 1]:
				temp1 = p[x]
				temp2 = p[y]
				p[x] = p[y]
				p[y] = y + 1
				d[temp1] = y
				d[temp2] = x
			else:
				e = -1
				for l in b[x + 1]:
					for j in b[y + 1]:
						if l == p[j - 1]:
							e = j - 1
							break
					if e != -1:
						break
				if e != -1:
					count += 1
					temp1 = p[e]
					temp2 = p[y]
					p[e] = p[y]
					p[y] = temp1
					d[temp1] = y
					d[temp2] = e
					temp1 = p[p[y] - 1]
					temp2 = p[x]
					p[x] = temp1
					p[p[y] - 1] = temp2
					d[temp1] = x
					d[temp2] = p[y] - 1
					temp1 = p[p[y] - 1]
					temp2 = p[y]
					d[temp2] = p[y] - 1
					d[temp1] = y
					p[p[y] - 1] = temp2
					p[y] = temp1
				else:
					pass
		z = []
		for i in range(1, n + 1):
			count3 = 0
			for j in b[i]:
				if p[j - 1] != j:
					count3 += 1
			if count3 == 0:
				pass
			else:
				z.append((count3, i - 1))
		z.sort()
		for j in z:
			i = j[1]
			x = d[i + 1]
			y = i
			if x == y:
				continue
			elif x + 1 in b[y + 1]:
				temp1 = p[x]
				temp2 = p[y]
				p[x] = p[y]
				p[y] = y + 1
				d[temp1] = y
				d[temp2] = x
			else:
				e = -1
				for l in b[x + 1]:
					for j in b[y + 1]:
						if l == p[j - 1]:
							e = j - 1
							break
					if e != -1:
						break
				if e != -1:
					count += 1
					temp1 = p[e]
					temp2 = p[y]
					p[e] = p[y]
					p[y] = temp1
					d[temp1] = y
					d[temp2] = e
					temp1 = p[p[y] - 1]
					temp2 = p[x]
					p[x] = temp1
					p[p[y] - 1] = temp2
					d[temp1] = x
					d[temp2] = p[y] - 1
					temp1 = p[p[y] - 1]
					temp2 = p[y]
					d[temp2] = p[y] - 1
					d[temp1] = y
					p[p[y] - 1] = temp2
					p[y] = temp1
				else:
					count += 1
					temp1 = p[x]
					temp2 = p[y]
					p[x] = p[y]
					p[y] = y + 1
					d[temp1] = y
					d[temp2] = x
	print(count)


from sys import stdin
from copy import deepcopy

def main():
	for _ in range(int(stdin.readline())):
		(n, m) = map(int, stdin.readline().split())
		pos = list(map(int, stdin.readline().split()))
		cycles = []
		for i in range(len(pos)):
			if pos[i] != i + 1:
				cycles.append(i + 1)
		shi = []
		if m != 0:
			l = [set(list(map(int, stdin.readline().split())))]
		else:
			l = []
		for i in range(m - 1):
			(x, y) = map(int, stdin.readline().split())
			fl = 0
			for j in l:
				if x in j:
					fl = 1
					j.add(y)
				if y in j:
					fl = 1
					j.add(x)
			if fl == 0:
				l.append(set([x, y]))
		fin = []
		while len(l):
			l1 = deepcopy(l)
			d = l[0].copy()
			while True:
				fl2 = 0
				for x in range(len(l)):
					if len(d.union(l[x])) != len(d) + len(l[x]):
						fl2 = 1
						d = d.union(l[x])
						l1.remove(l[x])
				fin.append(d)
				l = deepcopy(l1)
				if fl2 == 0:
					break
		di = {d: set() for d in range(1, n + 1)}
		for ll in fin:
			ll = list(ll)
			for lll in range(len(ll)):
				di[ll[lll]] = set(ll[:lll] + ll[lll + 1:])
		for xx in di.keys():
			if xx in cycles:
				for yy in di[xx]:
					if yy > xx and yy in cycles:
						shi.append([xx, yy])
		ans = 0
		cy1 = set(cycles)
		cy2 = cy1.copy()
		for x in cy1:
			if di[x] == set() and x in cy2:
				ans += 1
				a = pos.index(x)
				pos[a] = pos[x - 1]
				pos[x - 1] = x
				cy2.remove(x)
				if pos[a] == a + 1:
					cy2.remove(a + 1)
				if len(cy2) == 0:
					break
		cy1 = cy2.copy()
		while len(cy1):
			fl = 0
			for x in cy1:
				if pos[x - 1] in di[x]:
					fl = 1
					a = pos[x - 1]
					if [min(a, x), max(a, x)] in shi:
						shi.remove([min(a, x), max(a, x)])
					pos[x - 1] = pos[a - 1]
					pos[a - 1] = a
					cy2.remove(a)
					if pos[x - 1] == x:
						cy2.remove(x)
					if len(cy2) == 0:
						break
			if fl == 0:
				for x in cy1:
					fl1 = 0
					a = pos.index(x)
					if pos[x - 1] in di[a + 1]:
						fl1 = 1
						ans += 1
						pos[a] = pos[x - 1]
						pos[x - 1] = x
						cy2.remove(x)
						if pos[a] == a + 1:
							cy2.remove(a + 1)
						break
				if fl1 == 0:
					fl3 = 0
					for x in cy1:
						a = pos.index(x)
						if pos[x - 1] == a + 1:
							fl3 = 1
							ans += 1
							pos[a] = pos[x - 1]
							pos[x - 1] = x
							cy2.remove(x)
							if pos[a] == a + 1:
								cy2.remove(a + 1)
							break
					if fl3 == 0:
						fl4 = 0
						for x in shi:
							if x[0] in cy2 and x[1] in cy2:
								fl4 = 1
								(a, b) = (x[0], x[1])
								shi.remove(x)
								temp = pos[a - 1]
								pos[a - 1] = pos[b - 1]
								pos[b - 1] = temp
								if pos[a - 1] == a:
									cy2.remove(a)
								if pos[b - 1] == b:
									cy2.remove(b)
								break
						if fl4 == 0:
							for x in cy1:
								a = pos.index(x)
								ans += 1
								pos[a] = pos[x - 1]
								pos[x - 1] = x
								cy2.remove(x)
								if pos[a] == a + 1:
									cy2.remove(a + 1)
								break
			cy1 = cy2.copy()
		print(ans)
main()


def checkConnection(a, b):
	if a not in swapMap:
		return False
	if b in swapMap[a]:
		return True
	return False

def useShortcut():
	j = 0
	while j < n:
		if pArr[j] - 1 != j:
			aPos = j
			bPos = pArr[j] - 1
			if checkConnection(aPos, bPos):
				(pArr[aPos], pArr[bPos]) = (pArr[bPos], pArr[aPos])
			else:
				j += 1
		else:
			j += 1

def imprvPos(bPos, newCand):
	if pArr[bPos] == newCand:
		return True
	if bPos in swapMap:
		for pos in swapMap[bPos]:
			if pArr[pos] == newCand:
				(pArr[pos], pArr[bPos]) = (pArr[bPos], pArr[pos])
				return True
	return False

def createMap():
	swapMap = dict()
	for q in range(m):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		if a not in swapMap:
			swapMap[a] = set()
		swapMap[a].add(b)
		if b not in swapMap:
			swapMap[b] = set()
		swapMap[b].add(a)
		for p in swapMap[a]:
			swapMap[b].add(p)
		for p in swapMap[b]:
			swapMap[a].add(p)
		for p in swapMap[a]:
			swapMap[p] = swapMap[p].union(swapMap[a])
		for p in swapMap[b]:
			swapMap[p] = swapMap[p].union(swapMap[b])
	return swapMap

def killerMoves(a):
	i = 0
	while i < n:
		if i in swapMap and pArr[i] - 1 != i:
			aPos = i
			bPos = pArr[i] - 1
			newCand = i + 1
			imprvPos(bPos, newCand)
			(pArr[aPos], pArr[bPos]) = (pArr[bPos], pArr[aPos])
			a += 1
			if m > 0:
				useShortcut()
		else:
			i += 1
	return a

def revKM(a):
	i = n - 1
	while i >= 0:
		if i in swapMap and pArr[i] - 1 != i:
			aPos = i
			bPos = pArr[i] - 1
			newCand = i + 1
			imprvPos(bPos, newCand)
			(pArr[aPos], pArr[bPos]) = (pArr[bPos], pArr[aPos])
			a += 1
			if m > 0:
				useShortcut()
		else:
			i -= 1
	return a

def regularMoves(a):
	i = 0
	while i < n:
		if pArr[i] - 1 != i:
			aPos = i
			bPos = pArr[i] - 1
			newCand = i + 1
			imprvPos(bPos, newCand)
			(pArr[aPos], pArr[bPos]) = (pArr[bPos], pArr[aPos])
			a += 1
			if m > 0:
				useShortcut()
		else:
			i += 1
	return a

def revRM(a):
	i = n - 1
	while i >= 0:
		if pArr[i] - 1 != i:
			aPos = i
			bPos = pArr[i] - 1
			newCand = i + 1
			imprvPos(bPos, newCand)
			(pArr[aPos], pArr[bPos]) = (pArr[bPos], pArr[aPos])
			a += 1
			if m > 0:
				useShortcut()
		else:
			i -= 1
	return a

def extraKillerMoves(a):
	i = 0
	while i < n:
		if pArr[i] - 1 != i:
			aPos = i
			bPos = pArr[i] - 1
			newCand = i + 1
			if imprvPos(bPos, newCand):
				(pArr[aPos], pArr[bPos]) = (pArr[bPos], pArr[aPos])
				a += 1
				if m > 0:
					useShortcut()
			else:
				i += 1
		else:
			i += 1
	return a

def revEKM(a):
	i = n - 1
	while i >= 0:
		if pArr[i] - 1 != i:
			aPos = i
			bPos = pArr[i] - 1
			newCand = i + 1
			if imprvPos(bPos, newCand):
				(pArr[aPos], pArr[bPos]) = (pArr[bPos], pArr[aPos])
				a += 1
				if m > 0:
					useShortcut()
			else:
				i -= 1
		else:
			i -= 1
	return a
t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	oArr = list(map(int, input().split()))
	swapMap = createMap()
	ans = n
	for e in range(n):
		for f in range(n):
			temp = oArr.copy()
			(temp[e], temp[f]) = (temp[f], temp[e])
			initailAns = 0
			if e != f and checkConnection(e, f) is False:
				initailAns += 1
			a1 = initailAns
			pArr = temp.copy()
			if m > 0:
				useShortcut()
			a1 = regularMoves(a1)
			a2 = initailAns
			pArr = temp.copy()
			if m > 0:
				useShortcut()
			a2 = revRM(a2)
			ans = min(ans, a1, a2)
	print(ans)


class UnionFind:

	def __init__(self, n):
		self.size = [1 for _ in range(n)]
		self.parent = [i for i in range(n)]

	def find(self, i):
		while self.parent[i] != self.parent[self.parent[i]]:
			self.parent[i] = self.parent[self.parent[i]]
		return self.parent[i]

	def union(self, i, j):
		(rooti, rootj) = (self.find(i), self.find(j))
		if rooti == rootj:
			return
		if self.size[rooti] > self.size[rootj]:
			(rooti, rootj) = (rootj, rooti)
		self.parent[rooti] = rootj
		self.size[rootj] += self.size[rooti]

def solve(N, M, nums, pairs):
	nums = [n - 1 for n in nums]
	pairs = [[x - 1, y - 1] for (x, y) in pairs]
	uf = UnionFind(N)
	for (x, y) in pairs:
		uf.union(x, y)
	group = [uf.find(i) for i in range(N)]
	res = N * N

	def valid(val, i):
		return group[i] == group[val]

	def swap(i, j):
		(nums[i], nums[j]) = (nums[j], nums[i])

	def search(i, cnt):
		nonlocal res
		if i >= N - 1:
			res = min(res, cnt)
			return
		if valid(nums[i], i):
			search(i + 1, cnt)
			return
		for j in range(i + 1, N):
			if valid(nums[j], i):
				swap(i, j)
				search(i + 1, cnt + 1)
				swap(i, j)
	search(0, 0)
	return res

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for t in range(T):
		(N, M) = list(map(int, stdin.readline().strip().split()))
		nums = list(map(int, stdin.readline().strip().split()))
		pairs = [list(map(int, stdin.readline().strip().split())) for _ in range(M)]
		out = solve(N, M, nums, pairs)
		print(out)
main()


import math
import collections
from sys import stdin, stdout
T = int(stdin.readline())

def solve(x, y, i, j, ans):
	tmp = y[i]
	y[i] = y[j]
	y[j] = tmp
	l = len(x)
	if x == y:
		return ans
	finans = 10 ** 6
	res = False
	for i in range(l):
		if x[i] == y[i]:
			continue
		for j in range(l):
			if y[j] == x[i] and x[j] != y[j]:
				res = True
				finans = min(finans, solve(x.copy(), y.copy(), i, j, ans + 1))
		if res:
			break
	return finans
for _ in range(T):
	(n, m) = list(map(int, stdin.readline().split()))
	g = []
	for i in range(n + 1):
		g.append([])
	p = [0] + list(map(int, stdin.readline().split()))
	for i in range(m):
		(x, y) = list(map(int, stdin.readline().split()))
		g[x].append(y)
		g[y].append(x)
	exp = {}
	num = {}
	t = 0
	for i in range(1, n + 1, 1):
		if i in exp:
			continue
		a = [i]
		while a:
			u = a.pop()
			num[u] = t
			exp[u] = True
			for v in g[u]:
				if v not in exp:
					a.append(v)
		t += 1
	x = [-1]
	y = [-1]
	for i in range(1, n + 1, 1):
		y.append(num[p[i]])
		x.append(num[i])
	ans = 0
	l = len(x)
	res = True
	while res:
		res = False
		for i in range(l):
			if x[i] == y[i]:
				continue
			yj = x[i]
			xj = y[i]
			for j in range(i + 1, l, 1):
				if y[j] == yj and x[j] == xj:
					y[i] = x[i]
					y[j] = x[j]
					ans += 1
					res = True
					break
			if res:
				break
	ans = solve(x.copy(), y.copy(), 0, 0, ans)
	print(ans)


papa_array = []
cg = []

def spapa(kx):
	if papa_array[kx] != kx:
		sl = spapa(papa_array[kx])
		papa_array[kx] = sl
	return papa_array[kx]

def add_edge(kx, ky):
	sx = spapa(kx)
	sy = spapa(ky)
	if sx != sy:
		if cg[sx] == cg[sy]:
			papa_array[sy] = sx
			cg[sx] += 1
		elif cg[sx] > cg[sy]:
			papa_array[sy] = sx
		else:
			papa_array[sx] = sy

def check_empty(c):
	cnt = 0
	for i in c:
		for j in i:
			cnt += 1
	if cnt > 0:
		return False
	else:
		return True
for _ in range(int(input())):
	(n, m) = [int(kx) for kx in input().split()]
	arr = [int(kx) for kx in input().split()]
	papa_array = []
	cg = [0] * (n + 1)
	for i in range(n + 1):
		papa_array.append(i)
	for _i in range(m):
		(u, v) = [int(kx) for kx in input().split()]
		add_edge(u, v)
	c = []
	r = []
	for i in range(n):
		c.append([])
		r.append([])
	for i in range(n):
		r[spapa(i + 1) - 1].append(i + 1)
	for i in range(n):
		rem = []
		for j in r[i]:
			c[i].append(arr[j - 1])
	for i in range(n):
		rem = []
		for kz1 in r[i]:
			if kz1 in c[i]:
				rem.append(kz1)
		for kz1 in rem:
			c[i].remove(kz1)
			r[i].remove(kz1)
	ans = 0
	while check_empty(c) == False:
		for i in range(n - 1):
			j = i + 1
			while j < n:
				idx1 = idx2 = -1
				for kz1 in r[i]:
					if kz1 in c[j]:
						idx1 = kz1
				for kz1 in r[j]:
					if kz1 in c[i]:
						idx2 = kz1
				if idx1 < 0 or idx2 < 0:
					j += 1
					continue
				r[i].remove(idx1)
				c[j].remove(idx1)
				r[j].remove(idx2)
				c[i].remove(idx2)
				ans += 1
				j -= 1
		if check_empty(c) == False:
			j = 0
			ssz = 10000
			for i in range(n):
				for k in c[i]:
					if ssz > len(c[i]):
						j = i
						ssz = len(c[i])
						break
			kz1 = r[j][0]
			kz2 = c[j][0]
			iiiii = 0
			for i in range(n):
				if i != j:
					if kz1 in c[i]:
						iiiii = i
			r[j].remove(kz1)
			c[j].remove(kz2)
			c[iiiii].remove(kz1)
			c[iiiii].append(kz2)
			ans += 1
	print(ans)


from collections import defaultdict

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def DFSUtil(self, v, visited, ans1):
		visited[v] = True
		ans1.append(v)
		for i in self.graph[v]:
			if visited[i] == False:
				self.DFSUtil(i, visited, ans1)

	def fillOrder(self, v, visited, stack):
		visited[v] = True
		for i in self.graph[v]:
			if visited[i] == False:
				self.fillOrder(i, visited, stack)
		stack = stack.append(v)

	def getTranspose(self):
		g = Graph(self.V)
		for i in self.graph:
			for j in self.graph[i]:
				g.addEdge(j, i)
		return g

	def printSCCs(self):
		stack = []
		visited = [False] * self.V
		for i in range(self.V):
			if visited[i] == False:
				self.fillOrder(i, visited, stack)
		gr = self.getTranspose()
		visited = [False] * self.V
		while stack:
			i = stack.pop()
			if visited[i] == False:
				ans1 = []
				gr.DFSUtil(i, visited, ans1)
				ans.append(ans1)
t = int(input())
while t:
	t -= 1
	(n, m) = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	g = Graph(n + 1)
	for i in range(m):
		(aa, bb) = [int(i) for i in input().split()]
		g.addEdge(aa, bb)
		g.addEdge(bb, aa)
	ans = []
	g.printSCCs()
	ans.remove([0])
	a = p[:]
	a.sort()
	count = 0
	temp = 1
	connected = [-1] * (n + 1)
	for i in range(len(ans)):
		for j in ans[i]:
			connected[j] = i
	while temp == 1:
		temp = 0
		for i in range(len(p)):
			if p[i] != i + 1:
				for scc in ans:
					if i + 1 in scc and p[i] in scc:
						temp = 1
						x = p[p[i] - 1]
						p[p[i] - 1] = p[i]
						p[i] = x
	temp = 0
	while a != p:
		for i in range(len(p)):
			temp = 0
			if p[i] != i + 1:
				for scc in ans:
					if i + 1 in scc and p[i] in scc:
						x = p[p[i] - 1]
						p[p[i] - 1] = p[i]
						p[i] = x
		temp = 0
		for i in range(len(p)):
			if p[i] != i + 1:
				for scc in ans:
					if i + 1 in scc and p[p[i] - 1] in scc:
						count += 1
						x = p[p[i] - 1]
						p[p[i] - 1] = p[i]
						p[i] = x
						temp = 1
						break
				if temp == 1:
					break
		for i in range(len(p)):
			temp = 0
			if p[i] != i + 1:
				for scc in ans:
					if i + 1 in scc and p[i] in scc:
						x = p[p[i] - 1]
						p[p[i] - 1] = p[i]
						p[i] = x
		for i in range(len(p)):
			if p[i] != i + 1:
				for scc in ans:
					if i + 1 in scc:
						comp1 = scc
					if p[i] in scc:
						comp2 = scc
				for j in comp2:
					if p[j - 1] in comp1:
						count += 1
						first = p[i]
						second = p[j - 1]
						change = p[p[i] - 1]
						temp = p[second - 1]
						p[i] = temp
						p[j - 1] = change
						p[first - 1] = first
						p[second - 1] = second
						break
		for i in range(len(p)):
			temp = 0
			if p[i] != i + 1:
				for scc in ans:
					if i + 1 in scc and p[p[i] - 1] in scc:
						count += 1
						x = p[p[i] - 1]
						p[p[i] - 1] = p[i]
						p[i] = x
						temp = 1
						break
				if temp == 1:
					break
		for i in range(len(p)):
			temp = 0
			if p[i] != i + 1:
				for scc in ans:
					if i + 1 in scc and p[i] in scc:
						x = p[p[i] - 1]
						p[p[i] - 1] = p[i]
						p[i] = x
		check = [0] * len(ans)
		for i in range(len(p)):
			temp = 0
			if p[i] != i + 1:
				check[connected[p[i]]] += 1
		zeroes = check.count(0)
		check2 = check[:]
		for i in range(zeroes):
			check2.remove(0)
		if len(check2) > 0:
			count += 1
			mini = min(check2)
			miniindex = check.index(mini)
			comp = ans[miniindex]
			temp = 0
			for i in comp:
				if p[i - 1] != i:
					second = p[i - 1]
					for j in range(len(p)):
						if p[j] == i:
							first = p[j]
							p[i - 1] = first
							p[j] = second
							temp = 1
							break
				if temp == 1:
					break
	print(count)


import random
visited = []
group = []
graph = {}
pendingSwaps = {}
totalSwitches = 0
pendingSwitches = 0
countTypes = 0

def bfs(root, nodeGroup):
	visited[root] = 1
	group[root] = nodeGroup
	queue = []
	queue.append(root)
	while queue:
		s = queue.pop(0)
		for neighbour in graph[s]:
			if visited[neighbour] != 1:
				visited[neighbour] = 1
				group[neighbour] = nodeGroup
				queue.append(neighbour)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	graph = {}
	pendingSwaps = {}
	visited = [0 for i in range(n)]
	group = [-1 for i in range(n)]
	for i in range(n):
		graph[i] = []
	for i in range(m):
		(x, y) = list(map(int, input().split(' ')))
		graph[x - 1].append(y - 1)
		graph[y - 1].append(x - 1)
	countTypes = 0
	for i in range(n):
		if visited[i] == 0:
			bfs(i, countTypes)
			countTypes += 1
	totalSwitches = 0
	pendingSwitches = 0
	for i in range(n):
		if group[i] != group[arr[i] - 1]:
			if pendingSwaps.get((group[i], group[arr[i] - 1])):
				if pendingSwaps[group[i], group[arr[i] - 1]] == 1:
					del pendingSwaps[group[i], group[arr[i] - 1]]
				else:
					pendingSwaps[group[i], group[arr[i] - 1]] -= 1
				totalSwitches += 1
				pendingSwitches -= 1
			else:
				if pendingSwaps.get((group[arr[i] - 1], group[i])):
					pendingSwaps[group[arr[i] - 1], group[i]] += 1
				else:
					pendingSwaps[group[arr[i] - 1], group[i]] = 1
				pendingSwitches += 1
	numLoopsTracker = [[] for i in range(countTypes)]
	numLoopsLeft = [0 for i in range(countTypes)]
	for i in pendingSwaps.keys():
		numLoopsTracker[i[0]].extend([i[1]] * pendingSwaps[i])
		numLoopsLeft[i[0]] += pendingSwaps[i]
	remainingNodes = []
	for i in range(countTypes):
		if numLoopsLeft[i] > 0:
			remainingNodes.append(i)
	remainingNodes = sorted(remainingNodes, key=lambda x: numLoopsLeft[x], reverse=True)
	for i in range(countTypes):
		random.shuffle(numLoopsTracker[i])
	countCycles = 0
	while remainingNodes != []:
		remainingNodes = sorted(remainingNodes, key=lambda x: numLoopsLeft[x], reverse=True)
		countCycles += 1
		initialEle = remainingNodes[0]
		currentEle = numLoopsTracker[initialEle][0]
		buffer = [initialEle]
		while currentEle != initialEle and currentEle not in buffer:
			tempEle = numLoopsTracker[currentEle][0]
			buffer.append(currentEle)
			currentEle = tempEle
		startPos = buffer.index(currentEle)
		for i in buffer[startPos:]:
			numLoopsTracker[i].pop(0)
			numLoopsLeft[i] -= 1
			if numLoopsLeft[i] == 0:
				remainingNodes.remove(i)
	print(totalSwitches - countCycles + pendingSwitches)