H. Пик продуктивности форсес
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Я на пике продуктивности, и это глубоко.

Вам даны две перестановки$$$^{\text{∗}}$$$ $$$a$$$ и $$$b$$$, обе длины $$$n$$$.

Вы можете выполнить следующую трехшаговую операцию над перестановкой $$$a$$$:

  1. Выбрать индекс $$$i$$$ ($$$1 \le i \le n$$$).
  2. Циклически сдвинуть $$$a_1, a_2, \ldots, a_{i-1}$$$ на $$$1$$$ вправо. Если вы выбрали $$$i = 1$$$, то этот диапазон не существует, и вам не надо его сдвигать.
  3. Циклически сдвинуть $$$a_{i + 1}, a_{i + 2}, \ldots, a_n$$$ на $$$1$$$ вправо. Если вы выбрали $$$i = n$$$, то этот диапазон не существует, и вам не надо его сдвигать.

После операции массив $$$a_1,a_2,\ldots, a_{i-2},a_{i-1},a_i,a_{i + 1}, a_{i + 2},\ldots,a_{n-1}, a_n$$$ преобразуется в $$$a_{i-1},a_1,\ldots,a_{i-3},a_{i-2},a_i,a_n, a_{i + 1},\ldots,a_{n-2}, a_{n-1}$$$.

Вот несколько примеров операций, выполняемых над тождественной перестановкой $$$[1,2,3,4,5,6,7]$$$ длины $$$7$$$:

  • Если мы выберем $$$i = 3$$$, то она станет $$$[2, 1, 3, 7, 4, 5, 6]$$$.
  • Если мы выберем $$$i = 1$$$, то это станет $$$[1, 7, 2, 3, 4, 5, 6]$$$.
  • Если мы выберем $$$i = 7$$$, то это станет $$$[6, 1, 2, 3, 4, 5, 7]$$$.
Заметим, что позиция $$$i$$$ не сдвигается.

Найдите конструкцию, использующую не более $$$2n$$$ операций, чтобы $$$a$$$ стала равна $$$b$$$, или выведите $$$-1$$$, если это невозможно. Количество операций не обязательно должно быть минимальным. Можно показать, что если возможно сделать $$$a$$$ равным $$$b$$$, то это можно сделать не более чем за $$$2n$$$ операций.

$$$^{\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 5 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки $$$a$$$.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — элементы перестановки $$$b$$$.

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

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

Для каждого набора входных данных:

Если существует последовательность операций для преобразования $$$a$$$ в $$$b$$$, выведите одно целое число $$$q$$$ ($$$0\le q\le 2n$$$) — количество операций, в первой строке, и $$$q$$$ целых чисел, где $$$i$$$-е число представляет индекс на $$$i$$$-й операции, во второй строке.

Если последовательность операций не существует, то в единственной строке выведите $$$-1$$$.

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

-1
2
1 3
7
3 4 5 1 2 1 1
Примечание

В первом наборе входных данных вы можете не совершать операции, так как $$$a=b$$$.

Во втором наборе входных данных можно доказать, что $$$a$$$ не может быть преобразовано в $$$b$$$.

В третьем наборе входных данных $$$a$$$ преобразуется в $$$[2,3,1]$$$ после первой операции и в $$$b$$$ после второй операции.