Вам дана таблица \(a\) размера \(2 \times n\) (из двух строк и \(n\) столбцов), состоящая из целых чисел от \(1\) до \(n\).
За один ход вы можете выбрать какой-то столбец \(j\) (\(1 \le j \le n\)) и обменять местами значения \(a_{1, j}\) и \(a_{2, j}\). Каждый столбец может быть выбран не более одного раза.
Ваша задача — найти минимальное количество ходов, необходимое для того, чтобы получить перестановки размера \(n\) в первой и во второй строках, или же определить, что это сделать невозможно.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Напомним, что перестановкой размера \(n\) называется такой массив размера \(n\), который содержит каждое целое число от \(1\) до \(n\) ровно один раз (порядок элементов не важен).
Выходные данные
Выведите ответ на каждый набор тестовых данных: -1, если невозможно получить перестановки размера \(n\) в первой и второй строках таблицы, или же одно целое число \(k\) в первой строке, где \(k\) равно минимальному количеству ходов, необходимому для получения перестановок в обеих строках, а затем \(k\) различных целых чисел \(pos_1, pos_2, \dots, pos_k\) во второй строке (\(1 \le pos_i \le n\)) в любом порядке — индексы столбцов, в которых вам необходимо обменять значения местами для получения перестановок в обеих строках. Если существует несколько ответов, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
1 2 3 4
2 3 1 4
5
5 3 5 1 4
1 2 3 2 4
3
1 2 1
3 3 2
4
1 2 2 1
3 4 3 4
4
4 3 1 4
3 2 2 1
3
1 1 2
3 2 2
|
0
2
2 3
1
1
2
3 4
2
3 4
-1
|