Даны две перестановки \(a\) и \(b\), обе размера \(n\). Перестановка размера \(n\) — это массив из \(n\) элементов, в который каждое целое число от \(1\) до \(n\) входит ровно один раз. Элементы в каждой перестановке пронумерованы от \(1\) до \(n\).
Вы можете выполнять следующую операцию любое количество раз:
- выбрать целое число \(i\) от \(1\) до \(n\);
- обозначим за \(x\) такое целое число, что \(a_x = i\). Поменять местами \(a_i\) и \(a_x\);
- обозначим за \(y\) такое целое число, что \(b_y = i\). Поменять местами \(b_i\) и \(b_y\).
Вы должны отсортировать обе перестановки в порядке возрастания (то есть должны выполняться условия \(a_1 < a_2 < \dots < a_n\) и \(b_1 < b_2 < \dots < b_n\)) за минимальное количество операций. Обратите внимание, что обе перестановки должны быть отсортированы после того, как вы выполните выбранную вами последовательность операций.
Выходные данные
Сначала выведите одно целое число \(k\) (\(0 \le k \le 2n\)) — минимальное количество операций, за которое можно отсортировать обе перестановки. Обратите внимание: можно показать, что \(2n\) операций всегда достаточно.
Затем выведите \(k\) целых чисел \(op_1, op_2, \dots, op_k\) (\(1 \le op_j \le n\)), где \(op_j\) — значение \(i\), выбранное для \(j\)-й операции.
Если ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3 2 4 5
2 1 3 4 5
|
1
2
|
|
2
|
2
1 2
1 2
|
0
|
|
3
|
4
1 3 4 2
4 3 2 1
|
2
3 4
|