G. Фабрика перестановок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны две перестановки $$$p_1,p_2,\ldots,p_n$$$ и $$$q_1,q_2,\ldots,q_n$$$ длины $$$n$$$. За одну операцию вы можете выбрать два целых числа $$$1\leq i,j\leq n,i\neq j$$$ и поменять местами $$$p_i$$$ и $$$p_j$$$. Стоимость операции равна $$$\min (|i-j|,|p_i-p_j|)$$$.

Найдите минимальную стоимость последовательности операций, в результате которых для всех $$$1\leq i\leq n$$$ выполняется равенство $$$p_i = q_i$$$, и выведите последовательность с минимальной стоимостью.

Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — длина перестановок $$$p$$$ и $$$q$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1,p_2,\ldots,p_n$$$ ($$$1\leq p_i\leq n$$$) — перестановка $$$p$$$. Гарантируется, что $$$p_1,p_2,\ldots,p_n$$$ является перестановкой чисел $$$1,2,\ldots,n$$$.

Третья строка содержит $$$n$$$ целых чисел $$$q_1,q_2,\ldots,q_n$$$ ($$$1\leq q_i\leq n$$$) — перестановка $$$q$$$. Гарантируется, что $$$q_1,q_2,\ldots,q_n$$$ является перестановкой чисел $$$1,2,\ldots,n$$$.

Гарантируется, что сумма $$$n^3$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите общее количество операций $$$k$$$ ($$$0\le k\le n^2$$$) в первой строке. Затем выведите $$$k$$$ строк, каждая из которых содержит два целых числа $$$i,j$$$ ($$$1\le i,j\le n$$$, $$$i\neq j$$$) — операцию обмена $$$p_i$$$ и $$$p_j$$$. Операции выводите в порядке выполнения.

Можно показать, что ни одна оптимальная последовательность операций не имеет длину больше $$$n^2$$$.

Пример
Входные данные
4
2
2 1
2 1
3
1 2 3
3 2 1
4
2 1 4 3
4 2 3 1
5
1 4 3 2 5
5 2 3 4 1
Выходные данные
0
1
1 3
3
1 4
2 4
1 3
4
1 2
4 5
2 5
1 4
Примечание

Во втором наборе входных данных вы можете поменять местами $$$p_1,p_3$$$, что будет стоить $$$\min(|1-3|,|1-3|)=2$$$. Тогда $$$p$$$ станет равно $$$q$$$, а общая стоимость равна $$$2$$$.

В третьем наборе входных данных вы можете выполнить следующие операции:

Изначально, $$$p=[2,1,4,3]$$$.

  1. Поменять местами $$$p_1,p_4$$$, что будет стоить $$$\min(|1-4|,|2-3|)=1$$$, в результате чего $$$p=[3,1,4,2]$$$.
  2. Поменять местами $$$p_2,p_4$$$, что будет стоить $$$\min(|2-4|,|1-2|)=1$$$, в результате чего $$$p=[3,2,4,1]$$$.
  3. Поменять местами $$$p_1,p_3$$$, что будет стоить $$$\min(|1-3|,|3-4|)=1$$$. Тогда $$$p$$$ станет равно $$$q$$$. Общая стоимость равна $$$3$$$.