You are given two arrays $a$ and $b$, both consisting of $n$ integers.

In one move, you can choose two indices $i$ and $j$ ($1 \le i, j \le n$; $i \neq j$) and swap $a_i$ with $a_j$ and $b_i$ with $b_j$. You have to perform the swap in both arrays.

You are allowed to perform at most $10^4$ moves (possibly, zero). Can you make both arrays sorted in a non-decreasing order at the end? If you can, print any sequence of moves that makes both arrays sorted.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($2 \le n \le 100$) — the number of elements in both arrays.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the first array.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) — the second array.


-----Output-----

For each testcase, print the answer. If it's impossible to make both arrays sorted in a non-decreasing order in at most $10^4$ moves, print -1. Otherwise, first, print the number of moves $k$ $(0 \le k \le 10^4)$. Then print $i$ and $j$ for each move $(1 \le i, j \le n$; $i \neq j)$.

If there are multiple answers, then print any of them. You don't have to minimize the number of moves.


-----Examples-----

Input
3
2
1 2
1 2
2
2 1
1 2
4
2 3 1 2
2 3 2 3
Output
0
-1
3
3 1
3 2
4 3


-----Note-----

None

Difficulty: EASY
Tags: Sorting

Implementation
Skill types: Sorting

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	X = list(zip(a, b))
	Y = list(zip(sorted(a), sorted(b)))
	if Y == sorted(X):
		X_i = sorted((x + (i,) for (i, x) in enumerate(X)))
		a_index = list(range(n))
		b_index = [x[2] for x in X_i]
		moves = []
		for j in range(n):
			if a_index[j] == b_index[j]:
				continue
			a_i = j
			b_i = a_index.index(b_index[j])
			moves.append((a_i, b_i))
			(a_index[a_i], a_index[b_i]) = (a_index[b_i], a_index[a_i])
		print(len(moves))
		if len(moves) > 0:
			print('\n'.join((f'{x + 1} {y + 1}' for (x, y) in moves)))
	else:
		print(-1)


import sys
input = lambda : sys.stdin.readline().strip()

def is_sorted(a):
	last = a[0]
	for i in a:
		if i < last:
			return False
		last = i
	return True

def good(ab):
	a = [l for (l, r) in ab]
	b = [r for (l, r) in ab]
	return is_sorted(a) and is_sorted(b)

def get_sort_seq(ab, ab_sorted):
	idx = 0
	ans = []
	for pair in ab_sorted:
		cur = ab[idx:].index(pair) + idx
		if cur != idx:
			(ab[idx], ab[cur]) = (ab[cur], ab[idx])
			ans.append((cur + 1, idx + 1))
		idx += 1
	return ans
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ab = [*zip(a, b)]
	ba = [*zip(b, a)]
	if good(sorted(ab)):
		sort_seq = get_sort_seq(ab, sorted(ab))
	elif good(sorted(ba)):
		sort_seq = get_sort_seq(ba, sorted(ba))
	else:
		sort_seq = -1
	if sort_seq == -1:
		print(-1)
	else:
		print(len(sort_seq))
		for pair in sort_seq:
			print(*pair)


from math import ceil
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def mlt():
	return map(int, input().split())
mod = int(1000000000.0 + 7)

def initmap():
	return defaultdict(lambda : 0)

class Solution:

	def __init__(self) -> None:
		x = int(input())
		s = [*mlt()]
		z = [*mlt()]
		expectedS = sorted(s)
		expectedZ = sorted(z)
		res = []
		for n in range(x):
			a = [expectedS[n], expectedZ[n]]
			found = 0
			if s[n] == a[0] and z[n] == a[1]:
				continue
			for k in range(n + 1, x):
				if s[k] == a[0] and z[k] == a[1]:
					found = 1
					res.append([n + 1, k + 1])
					(s[n], s[k]) = (s[k], s[n])
					(z[n], z[k]) = (z[k], z[n])
					break
			if found == 0:
				print(-1)
				return
		print(len(res))
		for n in res:
			print(*n, sep=' ')
for _ in range(int(input())):
	Solution()


N = int(input())
for _ in range(N):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	zipped = list(zip(arr1, arr2, range(1, n + 1)))
	zipped.sort()
	second = [x[1] for x in zipped]
	if second != sorted(second):
		print(-1)
		continue
	third = [x[2] for x in zipped]
	l = list(range(1, n + 1))
	count = 0
	toOutput = []
	for i in range(n):
		if third[i] != l[i]:
			toOutput.append((third[i], l[i]))
			(third[third.index(i + 1)], third[i]) = (third[i], third[third.index(i + 1)])
			count += 1
	print(count)
	for (a, b) in toOutput:
		print(a, b)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	asorted = sorted(a)
	bsorted = sorted(b)
	moves = []
	oFlag = False
	for i in range(n):
		ai = asorted[i]
		bi = bsorted[i]
		flag = False
		for j in range(i, n):
			if ai == a[j] and bi == b[j]:
				if i != j:
					moves.append((i, j))
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
				flag = True
				break
		if not flag:
			print('-1')
			oFlag = True
			break
	if not oFlag:
		print(len(moves))
		for k in moves:
			print(str(k[0] + 1), str(k[1] + 1))


t = int(input())
for j in range(t):
	n = int(input())
	a = str(input()).split(' ')
	b = str(input()).split(' ')
	arr = []
	brr = []
	true = []
	inv = []
	for i in range(n):
		arr.append((i, int(a[i]), int(b[i])))
		brr.append((i, int(b[i]), int(a[i])))
		true.append(i)
		inv.append(i)
	arr.sort(key=lambda x: (x[1], x[2]))
	brr.sort(key=lambda x: (x[1], x[2]))
	answer = []
	flag = True
	for i in range(n - 1):
		if arr[i][0] != brr[i][0]:
			flag = False
			break
	if flag:
		for i in range(n - 1):
			if true[arr[i][0]] != i:
				answer.append((true[arr[i][0]], i))
				true[inv[i]] = true[arr[i][0]]
				inv[true[arr[i][0]]] = inv[i]
				true[arr[i][0]] = i
				inv[i] = arr[i][0]
		print(len(answer))
		for i in answer:
			print(i[0] + 1, i[1] + 1)
	else:
		print(-1)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	h = {}
	x = a.copy()
	y = b.copy()
	x.sort()
	y.sort()
	if a == x and b == y:
		print(0)
		t -= 1
		continue
	res = []
	count = 0
	flag = 0
	for i in range(n):
		if a[i] == x[i] and b[i] == y[i]:
			continue
		else:
			for j in range(i + 1, n):
				if a[j] == x[i] and b[j] == y[i]:
					res.append([i, j])
					(a[i], a[j]) = (a[j], a[i])
					(b[i], b[j]) = (b[j], b[i])
					count += 1
					break
		if a[i] == x[i] and b[i] == y[i]:
			continue
		else:
			flag = 1
			break
	if flag == 1:
		print(-1)
	else:
		print(count)
		for i in res:
			print(i[1] + 1, i[0] + 1)
	t -= 1


import sys
import math
from collections import Counter

def gi():
	return list(map(int, sys.stdin.readline().strip().split()))

def gs():
	return sys.stdin.readline().strip()

def fun(a, b):
	l = len(a)
	ans = list(zip(a, b))
	a1 = sorted(a)
	b1 = sorted(b)
	ans1 = list(zip(a1, b1))
	res = []
	for i in range(l):
		if ans[i] == ans1[i]:
			continue
		f = 0
		for j in range(i + 1, l):
			if ans1[i] == ans[j]:
				f = 1
				break
		if f == 0:
			return -1
		(ans[i], ans[j]) = (ans[j], ans[i])
		res.append([j + 1, i + 1])
	return res
for _ in range(int(input())):
	n = input()
	a = gi()
	b = gi()
	x = fun(a, b)
	if x == -1:
		print('-1')
	else:
		print(len(x))
		for i in x:
			print(*i)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sa = sorted(a)
	b = list(map(int, input().split()))
	sb = sorted(b)
	(x, y, xx, k, res) = ([], [], [], 0, [])
	for i in range(n):
		x.append((a[i], b[i]))
		xx.append((a[i], b[i], i))
		y.append((sa[i], sb[i]))
	if y == sorted(x):
		xx.sort()
		i_ns = [pp[2] for pp in xx]
		for j in range(n):
			m = i_ns[j]
			if m == j:
				continue
			o = i_ns.index(j)
			i_ns[o] = m
			i_ns[j] = 'h'
			k += 1
			res.append((j + 1, m + 1))
		print(k)
		for e in res:
			print(*e, sep=' ')
	else:
		print(-1)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	okA = sorted(A)
	okB = sorted(B)
	ans = []
	flag = 0
	for i in range(n):
		if A[i] == okA[i] and B[i] == okB[i]:
			continue
		for j in range(i + 1, n):
			if A[j] == okA[i] and B[j] == okB[i]:
				(A[i], A[j]) = (A[j], A[i])
				(B[i], B[j]) = (B[j], B[i])
				ans.append([i + 1, j + 1])
				break
		if A[i] != okA[i] or B[i] != okB[i]:
			flag = 1
			break
	if flag:
		print(-1)
	else:
		print(len(ans))
		for a in ans:
			print(*a)
t = int(input())
while t != 0:
	solve()
	t -= 1


def swap_times(c, d, pos, res, times):
	if pos == len(c):
		return (times, res)
	if c[pos] != d[pos]:
		times += 1
		for ii in range(pos, len(a)):
			if c[ii] == d[pos]:
				res.append((ii, pos))
				(c[ii], c[pos]) = (c[pos], c[ii])
				break
	return swap_times(c, d, pos + 1, res, times)

def output(c, d):
	for i in range(len(d) - 1):
		if d[i][1] > d[i + 1][1]:
			print(-1)
			return
	res = []
	times = 0
	ans = swap_times(c, d, 0, res, times)
	print(ans[0])
	for i in range(len(ans[1])):
		print(ans[1][i][0] + 1, ans[1][i][1] + 1)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	d = []
	for i in range(n):
		c.append((a[i], b[i]))
		d.append((a[i], b[i]))
	d.sort()
	output(c, d)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	q = sorted(a)
	w = sorted(b)
	answ = []
	for (i, e) in enumerate(zip(q, w)):
		if e[0] == a[i] and e[1] == b[i]:
			continue
		found = False
		for j in range(i + 1, n):
			if e[0] == a[j] and e[1] == b[j]:
				answ.append((i + 1, j + 1))
				(a[j], b[j]) = (a[i], b[i])
				found = True
				break
		if not found:
			answ = [-1]
			break
	if not answ:
		print(0)
		continue
	if answ[0] == -1:
		print(-1)
		continue
	print(len(answ))
	for (i, j) in answ:
		print(i, j)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	L = []
	for i in range(n):
		a = i + A[i:].index(min(A[i:]))
		b = i + B[i:].index(min(B[i:]))
		if A[b] == min(A[i:]) and b != i:
			(A[b], A[i]) = (A[i], A[b])
			(B[b], B[i]) = (B[i], B[b])
			L.append([b + 1, i + 1])
		elif B[a] == min(B[i:]) and a != i:
			(A[a], A[i]) = (A[i], A[a])
			(B[a], B[i]) = (B[i], B[a])
			L.append([a + 1, i + 1])
		elif B[a] == min(B[i:]) and a == i:
			pass
		elif A[b] == min(A[i:]) and b == i:
			pass
		else:
			break
	if i != n - 1 or len(L) > 10 ** 4:
		print(-1)
	else:
		print(len(L))
		for i in range(len(L)):
			print(*L[i])


def is_sorted(l):
	return all((l[i] <= l[i + 1] for i in range(len(l) - 1)))

def find_next(a, b, n, start):
	(idx, mina, minb) = (start, a[start], b[start])
	for i in range(start + 1, n):
		if a[i] < mina or (a[i] == mina and b[i] < minb):
			(idx, mina, minb) = (i, a[i], b[i])
	return idx

def double_sort(a, b, n):
	assert n == len(a) and n == len(b)
	sol = []
	for i in range(n - 1):
		idx = find_next(a, b, n, i)
		if idx != i:
			(a[i], a[idx]) = (a[idx], a[i])
			(b[i], b[idx]) = (b[idx], b[i])
			sol.append((i, idx))
	assert is_sorted(a)
	if not is_sorted(b):
		print(-1)
	else:
		print(len(sol))
		for s in sol:
			print(s[0] + 1, s[1] + 1)
t = int(input())
for c in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	double_sort(a, b, n)


for _ in range(int(input())):
	done = True
	n = int(input())
	(a, b) = (list(map(int, input().split())), list(map(int, input().split())))
	(aa, bb) = (sorted(a), sorted(b))
	res = []
	for i in range(n):
		if a[i] == aa[i] and b[i] == bb[i]:
			continue
		for j in range(i + 1, n):
			if a[j] == aa[i] and b[j] == bb[i]:
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
				res += [(i, j)]
				break
		if a[i] != aa[i] or b[i] != bb[i]:
			done = False
			break
	if not done:
		print(-1)
	else:
		print(len(res))
		for swap in res:
			print(swap[0] + 1, swap[1] + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	oa = a.copy()
	ob = b.copy()
	ml = []
	m = 0
	a.sort()
	b.sort()
	for i in range(n):
		for j in range(i, n):
			if a[i] == oa[j]:
				(oa[i], oa[j]) = (oa[j], oa[i])
				(ob[i], ob[j]) = (ob[j], ob[i])
				if i != j:
					ml.append((i, j))
					m += 1
				break
	for i in range(n):
		for j in range(i, n):
			if b[i] == ob[j]:
				(oa[i], oa[j]) = (oa[j], oa[i])
				(ob[i], ob[j]) = (ob[j], ob[i])
				if i != j:
					ml.append((i, j))
					m += 1
				break
	if oa == a and m <= 10 ** 4:
		print(m)
		for x in ml:
			print(x[0] + 1, x[1] + 1)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(int(input()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	operations = []
	u = sorted(a)
	o = sorted(b)
	can = True
	for i in range(n):
		needed = (u[i], o[i])
		index = None
		for j in range(i, n):
			if (a[j], b[j]) == needed:
				index = j
				break
		if index == None:
			can = False
			break
		else:
			(a[i], a[index]) = (a[index], a[i])
			(b[i], b[index]) = (b[index], b[i])
			if i != index:
				operations.append((i + 1, index + 1))
	if can:
		print(len(operations))
		for item in operations:
			print(*item)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	A = [i for i in a]
	B = [j for j in b]
	A.sort()
	B.sort()
	(ans, move) = ([], 0)
	flag = False
	for i in range(n):
		if a[i] == A[i] and b[i] == B[i]:
			continue
		else:
			pair = (A[i], B[i])
			for j in range(i + 1, n):
				if pair[0] == a[j] and pair[1] == b[j]:
					(a[i], a[j]) = (a[j], a[i])
					(b[i], b[j]) = (b[j], b[i])
					ans.append((i + 1, j + 1))
			if a[i] == pair[0] and b[i] == pair[1]:
				continue
			else:
				flag = True
				break
	if flag:
		print(-1)
	else:
		print(len(ans))
		for i in range(len(ans)):
			print(ans[i][0], ans[i][1])


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = [i for i in sorted(a)]
	y = [i for i in sorted(b)]
	ans = []
	flag = 0
	for i in range(n):
		if a[i] == x[i] and b[i] == y[i]:
			continue
		else:
			for j in range(i + 1, n):
				if a[j] == x[i] and b[j] == y[i]:
					ans.append((i + 1, j + 1))
					(a[i], a[j]) = (a[j], a[i])
					(b[i], b[j]) = (b[j], b[i])
		if a[i] == x[i] and b[i] == y[i]:
			continue
		else:
			flag = 1
			break
	if flag:
		print(-1)
	else:
		print(len(ans))
		for i in ans:
			print(*i)
	t -= 1


t = int(input())
while t:
	n = int(input())
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	d1 = dict()
	d2 = dict()
	C = []
	for i in range(n):
		C.append((A[i], B[i]))
	C.sort()
	res = []
	for i in range(n):
		if A[i] == C[i][0] and B[i] == C[i][1]:
			pass
		else:
			for j in range(i + 1, n):
				if A[j] == C[i][0] and B[j] == C[i][1]:
					(A[i], A[j]) = (A[j], A[i])
					(B[i], B[j]) = (B[j], B[i])
					res.append((i + 1, j + 1))
	temp = True
	for i in range(1, n):
		if C[i][0] >= C[i - 1][0] and C[i][1] >= C[i - 1][1]:
			pass
		else:
			temp = False
	if temp:
		print(len(res))
		for i in res:
			print(i[0], i[1])
	else:
		print('-1')
	t -= 1


def getmin(a, c):
	m = min(a[c:])
	k = set()
	for i in range(c, len(a)):
		if a[i] == m:
			k.add(i)
	return k
t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	ans = []
	flag = True
	while c < len(a):
		sa = getmin(a, c)
		sb = getmin(b, c)
		both = sa.intersection(sb)
		if len(both) == 0:
			flag = False
			break
		if c in both:
			pass
		else:
			z = both.pop()
			ans.append((c, z))
			(a[c], a[z]) = (a[z], a[c])
			(b[c], b[z]) = (b[z], b[c])
		c += 1
		continue
	if flag and len(ans) <= 10 ** 4:
		print(len(ans))
		for el in ans:
			print(el[0] + 1, el[1] + 1)
	else:
		print(-1)


def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	idxl = []
	for i in range(0, n):
		swapidx = i
		for j in range(i + 1, n):
			if a[j] < a[swapidx]:
				swapidx = j
		if swapidx != i:
			(a[i], a[swapidx]) = (a[swapidx], a[i])
			(b[i], b[swapidx]) = (b[swapidx], b[i])
			idxl.append([i, swapidx])
	for i in range(len(b) - 1):
		swapidx = i
		for j in range(i + 1, len(b)):
			if b[j] < b[swapidx] and a[i] == a[j]:
				swapidx = j
		if swapidx != i:
			(a[i], a[swapidx]) = (a[swapidx], a[i])
			(b[i], b[swapidx]) = (b[swapidx], b[i])
			idxl.append([i, swapidx])
	for i in range(1, n):
		if b[i] < b[i - 1]:
			print(-1)
			return
	print(len(idxl))
	if len(idxl) > 0:
		for ls in idxl:
			print(ls[0] + 1, ' ', ls[1] + 1)
t = int(input())
for _ in range(t):
	solve()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = []
	for i in range(n):
		p.append([a[i], b[i]])
	ans = []
	p.sort()
	flag = 1
	for i in range(n):
		if i != 0:
			if p[i][0] >= p[i - 1][0] and p[i][1] >= p[i - 1][1]:
				pass
			else:
				flag = 0
				break
		if a[i] == p[i][0] and b[i] == p[i][1]:
			pass
		else:
			for j in range(i + 1, n):
				if a[j] == p[i][0] and b[j] == p[i][1]:
					(a[i], a[j]) = (a[j], a[i])
					(b[i], b[j]) = (b[j], b[i])
					ans.append([i + 1, j + 1])
	if flag:
		print(len(ans))
		for i in ans:
			print(*i)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = []
	flag = True
	for i in range(n):
		small = (a[i], b[i])
		ii = i
		for j in range(i + 1, n):
			cur = (a[j], b[j])
			if small > cur:
				small = cur
				ii = j
		if ii == i:
			continue
		ans.append((i, ii))
		(a[ii], a[i]) = (a[i], a[ii])
		(b[ii], b[i]) = (b[i], b[ii])
	for i in range(1, n):
		if b[i] < b[i - 1]:
			flag = False
			break
	if not flag:
		print(-1)
	else:
		print(len(ans))
		for (aa, bb) in ans:
			print(aa + 1, bb + 1)


t = int(input())
result = []
for l in range(t):
	n = int(input())
	ai = list(map(int, input().split(' ')))
	bi = list(map(int, input().split(' ')))
	k = 0
	impos = False
	moves = []
	for i in range(n):
		(minai, minbi) = (ai[i], bi[i])
		swapIndice = i
		for j in range(i, n):
			if (ai[j] <= minai) & (bi[j] <= minbi):
				(minai, minbi) = (ai[j], bi[j])
				swapIndice = j
		if swapIndice != i:
			k += 1
			moves.append(str(i + 1) + ' ' + str(swapIndice + 1))
			(ai[i], ai[swapIndice]) = (ai[swapIndice], ai[i])
			(bi[i], bi[swapIndice]) = (bi[swapIndice], bi[i])
	for i in range(n - 1):
		if (ai[i] > ai[i + 1]) | (bi[i] > bi[i + 1]):
			impos = True
	if impos == False:
		result.append(k)
		result += moves
	else:
		result.append(-1)
for i in result:
	print(i)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	ans = []
	cnt = 0
	while cnt < n:
		(ia, ib) = (set(), set())
		(ma, mb) = (101, 101)
		for i in range(cnt, n):
			if A[i] < ma:
				ma = A[i]
				ia = {i}
			elif A[i] == ma:
				ia.add(i)
			if B[i] < mb:
				mb = B[i]
				ib = {i}
			elif B[i] == mb:
				ib.add(i)
		if cnt in ib and cnt in ia:
			cnt += 1
			continue
		prev = len(ans)
		for c in ib:
			if c in ia:
				(A[cnt], A[c]) = (A[c], A[cnt])
				(B[cnt], B[c]) = (B[c], B[cnt])
				ans.append([c + 1, cnt + 1])
				break
		if len(ans) == prev:
			print(-1)
			return
		cnt += 1
	print(len(ans))
	for each in ans:
		print(*each)
	return
for _ in range(int(input())):
	solve()


x = lambda : map(int, input().split())
for t in range(int(input())):
	(n,) = x()
	a = [*x()]
	b = [*x()]
	index = []
	ta = sorted(a)
	tb = sorted(b)
	c = 0
	for i in range(n - 1):
		index_min = i
		for j in range(i + 1, n):
			if a[j] < a[index_min]:
				index_min = j
			elif a[j] == a[index_min]:
				if b[j] < b[index_min]:
					index_min = j
		if index_min != i:
			index.append([index_min + 1, i + 1])
			c += 1
			(temp1, temp2) = (a[i], b[i])
			a[i] = a[index_min]
			a[index_min] = temp1
			b[i] = b[index_min]
			b[index_min] = temp2
	if a != ta or b != tb:
		print(-1)
	else:
		print(c)
		for i in index:
			print(*i)


t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = []
	for i in range(n):
		c.append(b[i])
	ans = []
	for i in range(n):
		m = i
		for j in range(i + 1, n):
			if a[m] > a[j]:
				m = j
			elif a[m] == a[j]:
				if b[m] > b[j]:
					m = j
		(a[i], a[m]) = (a[m], a[i])
		(b[i], b[m]) = (b[m], b[i])
		if i != m:
			ans.append([i + 1, m + 1])
	c.sort()
	flag = True
	for i in range(n):
		if c[i] != b[i]:
			flag = False
			break
	if flag:
		print(len(ans))
		for i in range(len(ans)):
			print(ans[i][0], ans[i][1])
	else:
		print(-1)
	t -= 1


for i in range(int(input())):
	n = int(input())
	a = [int(k) for k in input().split()]
	b = [int(k) for k in input().split()]
	A = sorted(a)
	B = sorted(b)
	if A == a and B == b:
		print(0)
		continue
	else:
		ANS = []
		for k in range(n):
			if a[k] != A[k]:
				for j in range(k + 1, n):
					if A[k] == a[j] and B[k] == b[j]:
						ANS.append([j + 1, k + 1])
						(a[j], a[k]) = (a[k], a[j])
						(b[j], b[k]) = (b[k], b[j])
			if b[k] != B[k]:
				for j in range(k + 1, n):
					if A[k] == a[j] and B[k] == b[j]:
						ANS.append([j + 1, k + 1])
						(a[j], a[k]) = (a[k], a[j])
						(b[j], b[k]) = (b[k], b[j])
		if b == B and a == A:
			print(len(ANS))
			for k in ANS:
				print(*k)
		else:
			print(-1)


t = int(input())
for j in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a.copy()
	d = b.copy()
	c.sort()
	d.sort()
	p = []
	g = []
	v = []
	op = []
	s = 0
	fo = -1
	for k in range(0, n):
		p.append(str(a[k]) + ' ' + str(b[k]))
		g.append(str(c[k]) + ' ' + str(d[k]))
		if p[-1] == g[-1]:
			s += 1
		v.append(0)
		op.append(0)
	if s != n:
		for i in range(0, n):
			fo = -1
			for k in range(0, n):
				if v[k] == 0:
					if p[k] == g[i]:
						v[k] = 1
						op[k] = i
						fo = 0
						break
				else:
					continue
			if fo == -1:
				print(-1)
				break
		bb = []
		cc = 0
		if fo != -1:
			for i in range(0, n):
				mi = i
				for k in range(i + 1, n):
					if op[mi] > op[k]:
						mi = k
				(op[i], op[mi]) = (op[mi], op[i])
				if mi != i:
					cc += 1
					bb.append(str(mi + 1) + ' ' + str(i + 1))
			print(cc)
			for i in bb:
				print(i)
	else:
		print(0)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')

def solve():
	for _ in range(get_int()):
		n = get_int()
		a = get_list()
		b = get_list()
		asor = sorted(a)
		bsor = sorted(b)
		moves = []
		total = 0
		for i in range(n):
			for j in range(i + 1, n):
				if a[i] > a[j]:
					total += 1
					moves.append([i + 1, j + 1])
					(a[i], a[j]) = (a[j], a[i])
					(b[i], b[j]) = (b[j], b[i])
				elif a[i] == a[j]:
					if b[i] > b[j]:
						total += 1
						moves.append([i + 1, j + 1])
						(b[i], b[j]) = (b[j], b[i])
		if asor == a and bsor == b:
			get_print_int(total)
			for i in moves:
				get_print(' '.join(map(str, i)))
		else:
			get_print_int(-1)
solve()


import sys
input = sys.stdin.readline

def solve():
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	L = sorted(A)
	M = sorted(B)
	X = []
	Y = []
	for i in range(N):
		if A[i] != L[i]:
			X.append(i)
		if B[i] != M[i]:
			Y.append(i)
	if X == Y == []:
		print(0)
	else:
		c = 0
		ans = []
		for i in range(N):
			for j in range(i + 1, N):
				if A[i] > A[j]:
					(A[i], A[j]) = (A[j], A[i])
					(B[i], B[j]) = (B[j], B[i])
					ans.append(str(i + 1) + ' ' + str(j + 1))
					c += 1
		for i in range(N):
			for j in range(i + 1, N):
				if B[i] > B[j]:
					(A[i], A[j]) = (A[j], A[i])
					(B[i], B[j]) = (B[j], B[i])
					ans.append(str(i + 1) + ' ' + str(j + 1))
					c += 1
		if A != L or B != M:
			print(-1)
		else:
			print(c)
			for i in ans:
				print(i)
for _ in range(int(input())):
	solve()


t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	b = [int(i) for i in input().split(' ')]
	ans = []
	flag = True
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				if b[i] < b[j]:
					flag = False
					break
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
				ans.append((i, j))
			elif a[i] == a[j]:
				if b[i] > b[j]:
					ans.append((i, j))
					(b[i], b[j]) = (b[j], b[i])
			elif a[i] < a[j]:
				if b[i] > b[j]:
					flag = False
					break
		if flag == False:
			break
	if flag:
		print(len(ans))
		for i in ans:
			print(f'{i[0] + 1} {i[1] + 1}')
	else:
		print(-1)
	t -= 1


li = lambda : list(map(int, input().split()))
lis = lambda : sorted(list(map(int, input().split())))
mp = lambda : map(int, input().split())
it = lambda : int(input())
st = lambda : str(input())
import math

def function(a, b):
	q = []
	for i in range(len(a)):
		for j in range(i):
			if a[j] > a[i]:
				q.append((j + 1, i + 1))
				(a[j], a[i]) = (a[i], a[j])
				(b[j], b[i]) = (b[i], b[j])
	for i in range(len(a)):
		for j in range(i):
			if b[j] > b[i]:
				q.append((j + 1, i + 1))
				(a[j], a[i]) = (a[i], a[j])
				(b[j], b[i]) = (b[i], b[j])
	if a != sorted(a) or b != sorted(b):
		return [(-1, '')]
	else:
		print(len(q))
		return q
for _ in range(int(input())):
	n = input()
	aa = list(map(int, input().split()))
	bb = list(map(int, input().split()))
	[print(i, j) for (i, j) in function(aa, bb)]


def solve():
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			if arr1[i] > arr1[j] or arr2[i] > arr2[j]:
				(arr1[i], arr1[j]) = (arr1[j], arr1[i])
				(arr2[i], arr2[j]) = (arr2[j], arr2[i])
				arr.append([i + 1, j + 1])
	for i in range(n - 1):
		if arr1[i] > arr1[i + 1] or arr2[i] > arr2[i + 1]:
			print(-1)
			return
	print(len(arr))
	if len(arr) > 0:
		for i in arr:
			print(i[0], i[1])
	return
for i in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	ans = []
	a1 = list(map(int, input().split()))
	a2 = list(map(int, input().split()))
	for i in range(n - 1):
		for j in range(i, n):
			if a1[i] > a1[j]:
				ans.append((i + 1, j + 1))
				(a1[i], a1[j]) = (a1[j], a1[i])
				(a2[i], a2[j]) = (a2[j], a2[i])
	for i in range(n - 1):
		for j in range(i, n):
			if a2[i] > a2[j]:
				ans.append((i + 1, j + 1))
				(a1[i], a1[j]) = (a1[j], a1[i])
				(a2[i], a2[j]) = (a2[j], a2[i])
	flag = True
	for i in range(n - 1):
		if a1[i] > a1[i + 1]:
			print(-1)
			flag = False
			break
	if flag:
		print(len(ans))
		for (i, j) in ans:
			print(str(i) + ' ' + str(j))


import sys, math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		n = int(input())
		a = get_ls()
		b = get_ls()
		res = []
		for i in range(n - 1):
			for j in range(i + 1, n):
				if a[i] >= a[j] and b[i] >= b[j]:
					(a[i], a[j]) = (a[j], a[i])
					(b[i], b[j]) = (b[j], b[i])
					res.append([i + 1, j + 1])
		if a == sorted(a) and b == sorted(b):
			print(len(res))
			for x in res:
				print(*x)
		else:
			print(-1)
main()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sa = sorted(a)
	sb = sorted(b)
	if a == sa and b == sb:
		print(0)
		return
	pairs = []
	for i in range(n):
		for j in range(i + 1, n):
			if b[j] <= b[i] and a[j] <= a[i]:
				pairs.append([j + 1, i + 1])
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
			if len(pairs) > 10 ** 4:
				print(-1)
				return
	if a == sa and b == sb:
		print(len(pairs))
		for (i, j) in pairs:
			print(i, j)
		return
	print(-1)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	x = int(input())
	zoop1 = list(map(int, input().split()))
	zoop2 = list(map(int, input().split()))
	zop1 = []
	for i in range(len(zoop1)):
		zop1.append((zoop1[i], zoop2[i]))
	ans = []
	for i in range(x):
		for j in range(i + 1, x):
			if zop1[i] > zop1[j]:
				ans.append((i, j))
				(zop1[i], zop1[j]) = (zop1[j], zop1[i])
	zoop2.sort()
	zz = True
	for i in range(len(zoop2)):
		if zoop2[i] != zop1[i][1]:
			zz = False
			break
	if zz == False:
		print(-1)
	else:
		print(len(ans))
		for i in range(len(ans)):
			print(ans[i][0] + 1, ans[i][1] + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	lst = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[i] > a[j] or b[i] > b[j]:
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
				lst.append((j + 1, i + 1))
	if b == sorted(b) and a == sorted(a):
		print(len(lst))
		for (i, j) in lst:
			print(i, j)
	else:
		print(-1)


def resi():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[i] < a[j] and b[i] > b[j]:
				print(-1)
				return
			if a[i] > a[j] and b[i] < b[j]:
				print(-1)
				return
			if a[i] > a[j] or b[i] > b[j]:
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
				l.append([i, j])
	print(len(l))
	for i in range(len(l)):
		print(l[i][0] + 1, l[i][1] + 1)
for _ in range(int(input())):
	resi()


def sort(a, b):
	x = []
	for i in range(len(a)):
		for j in range(i, len(a)):
			if a[j] < a[i]:
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
				x.append([j + 1, i + 1])
	for i in range(len(a)):
		for j in range(i, len(a)):
			if b[j] < b[i]:
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
				x.append([j + 1, i + 1])
	if b != sorted(b) or a != sorted(a):
		return -1
	else:
		return x
for _ in range(int(input())):
	k = int(input())
	arr1 = [int(i) for i in input().split()]
	arr2 = [int(i) for i in input().split()]
	z = sort(arr1, arr2)
	if z == -1:
		print(-1)
	elif len(z) == 0:
		print(0)
	else:
		print(len(z))
		for x in z:
			print(*x)


for e in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	res = []
	for i in range(n):
		for j in range(i + 1, n):
			if a[j] < a[i] or b[j] < b[i]:
				res.append((j + 1, i + 1))
				(b[i], b[j]) = (b[j], b[i])
				(a[j], a[i]) = (a[i], a[j])
	if not (a == sorted(a) and b == sorted(b)):
		print(-1)
		continue
	print(len(res))
	for i in res:
		print(*i)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	ans = []
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j] or b[i] > b[j]:
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
				ans.append((i + 1, j + 1))
	sa = sorted(a)
	sb = sorted(b)
	if sa == a and sb == b:
		print(len(ans))
		for i in ans:
			print(*i)
	else:
		print(-1)


for i in range(int(input())):
	lenn = int(input())
	list1 = list(map(int, input().split()))
	list2 = list(map(int, input().split()))
	moves = 0
	ans = []
	for i in range(lenn):
		for j in range(i + 1, lenn):
			if list1[i] > list1[j] or list2[i] > list2[j]:
				(list1[i], list1[j]) = (list1[j], list1[i])
				(list2[i], list2[j]) = (list2[j], list2[i])
				ans.append([i + 1, j + 1])
				moves += 1
	if sorted(list1) == list1 and sorted(list2) == list2:
		print(moves)
		for i in ans:
			print(*i)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	res = []
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr1[j] < arr1[i]:
				(arr1[i], arr1[j]) = (arr1[j], arr1[i])
				(arr2[i], arr2[j]) = (arr2[j], arr2[i])
				res.append([j + 1, i + 1])
				c = 1
			elif arr1[j] == arr1[i]:
				if arr2[j] < arr2[i]:
					(arr1[i], arr1[j]) = (arr1[j], arr1[i])
					(arr2[i], arr2[j]) = (arr2[j], arr2[i])
					res.append([j + 1, i + 1])
					c = 1
	if sorted(arr1) == arr1 and sorted(arr2) == arr2:
		if c == 0:
			print(0)
		else:
			print(len(res))
			for i in range(len(res)):
				ans = res[i]
				print(ans[0], ans[1])
	else:
		print(-1)


import sys
input = sys.stdin.readline

def Issorted(arr):
	pre = arr[0]
	for v in arr[1:]:
		if pre > v:
			return False
		pre = v
	return True

def correct(answer):
	print(len(answer))
	for v in answer:
		print(*v)
	return
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	aa = a.copy()
	ab = b.copy()
	answerA = []
	for i in range(n):
		for j in range(i + 1, n):
			if aa[i] >= aa[j]:
				if aa[i] == aa[j] and ab[i] <= ab[j]:
					continue
				(aa[i], aa[j]) = (aa[j], aa[i])
				(ab[i], ab[j]) = (ab[j], ab[i])
				answerA.append((i + 1, j + 1))
	if Issorted(aa) and Issorted(ab):
		correct(answerA)
		continue
	aa = a.copy()
	ab = b.copy()
	answerB = []
	for i in range(n):
		for j in range(i + 1, n):
			if ab[i] >= ab[j]:
				if ab[i] == ab[j] and aa[i] <= aa[j]:
					continue
				(ab[i], ab[j]) = (ab[j], ab[i])
				(aa[i], aa[j]) = (aa[j], aa[i])
				answerB.append((i, j))
	if Issorted(aa) and Issorted(ab):
		correct(answerB)
	else:
		print(-1)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	r = []
	for i in range(n):
		for j in range(i):
			if a[j] > a[i]:
				r.append((j + 1, i + 1))
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
	for i in range(n):
		for j in range(i):
			if b[j] > b[i]:
				r.append((j + 1, i + 1))
				(a[i], a[j]) = (a[j], a[i])
				(b[i], b[j]) = (b[j], b[i])
	if a != sorted(a) or b != sorted(b):
		r = [(-1, '')]
	else:
		print(len(r))
	for (i, j) in r:
		print(i, j)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	brr = list(map(int, input().strip().split()))[:n]

	def issorted(L):
		flag = 1
		for i in range(n - 1):
			if L[i] > L[i + 1]:
				flag = 0
				break
		return flag
	a = []
	b = []
	cnt = 0
	for i in range(n - 1):
		for j in range(i + 1, n, +1):
			if arr[i] >= arr[j] and brr[i] >= brr[j]:
				a.append(i + 1)
				b.append(j + 1)
				(arr[i], arr[j]) = (arr[j], arr[i])
				(brr[i], brr[j]) = (brr[j], brr[i])
	if issorted(arr) == 1 and issorted(brr) == 1:
		print(len(a))
		for i in range(len(a)):
			print(a[i], b[i])
	else:
		print(-1)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = sorted(a)
	d = sorted(b)
	count = 0
	k = []
	temp = 0
	if a == c and b == d:
		print(0)
		continue
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[i] >= a[j] and b[i] >= b[j]:
				temp = a[i]
				a[i] = a[j]
				a[j] = temp
				temp = b[i]
				b[i] = b[j]
				b[j] = temp
				k.append([i + 1, j + 1])
				count += 1
	if a == c and b == d:
		print(count)
		for i in k:
			print(' '.join(list(map(str, i))))
	else:
		print(-1)