C. Вы грациозно взмыли вдаль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны две перестановки $$$a$$$ и $$$b$$$ длины $$$n$$$$$$^{\text{∗}}$$$. Вы можете выполнить следующую операцию не более $$$n$$$ раз:

  • Выберите два индекса $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$), поменяйте $$$a_i$$$ с $$$a_j$$$, поменяйте $$$b_i$$$ с $$$b_j$$$.

Определите, могут ли $$$a$$$ и $$$b$$$ оказаться перевернутыми копиями друг друга в результате выполнения некоторого (возможно, нулевого) числа операций. Иными словами, для каждого $$$i = 1, 2, \ldots, n$$$ должно выполняться $$$a_i = b_{n + 1 - i}$$$.

Если это возможно, выведите любую допустимую последовательность операций. В противном случае выведите $$$-1$$$.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$).

Гарантируется, что $$$a$$$ и $$$b$$$ являются перестановками длины $$$n$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных, если это невозможно, выведите $$$-1$$$ в единственной строке. В противном случае выведите одно целое число $$$m$$$ ($$$0 \le m \le n$$$) — количество операций в первой строке. В следующих $$$m$$$ строках выведите по два целых числа — индексы $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$) в каждой операции по порядку. Если существует несколько решений, выведите любое из них.

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

Во втором наборе входных данных $$$b$$$ уже является обратной к $$$a$$$.

В третьем наборе входных данных, после выполнения следующей операции, $$$b$$$ станет обратной к $$$a$$$:

  • Обменяйте $$$a_1, a_2$$$ и обменяйте $$$b_1, b_2$$$. Теперь $$$a = [3, 1, 2, 4]$$$ и $$$b = [4, 2, 1, 3]$$$.

В четвертом наборе входных данных, после выполнения следующих операций $$$b$$$ станет обратной к $$$a$$$:

  • Обменяйте $$$a_1, a_2$$$ и обменяйте $$$b_1, b_2$$$. Теперь $$$a = [5, 2, 1, 3, 4]$$$ и $$$b = [5, 3, 4, 2, 1]$$$.
  • Обменяйте $$$a_1, a_3$$$ и обменяйте $$$b_1, b_3$$$. Теперь $$$a = [1, 2, 5, 3, 4]$$$ и $$$b = [4, 3, 5, 2, 1]$$$.