Заданы два массива \(a\) и \(b\), оба состоящие из \(n\) целых чисел.
За один ход можно выбрать две позиции \(i\) и \(j\) (\(1 \le i, j \le n\); \(i \neq j\)) и поменять местами \(a_i\) с \(a_j\) и \(b_i\) с \(b_j\). Перестановки обязательно делать в обоих массивах.
Разрешается сделать не более \(10^4\) ходов (возможно, ноль). Можете ли вы сделать оба массива отсортированными по неубыванию в конце? Если можете, то выведите любую последовательность ходов, которая делает оба массива отсортированными.
Выходные данные
На каждый набор входных данных выведите ответ. Если невозможно сделать оба массива отсортированными по неубыванию за не более чем \(10^4\) ходов, то выведите -1. Иначе сначала выведите количество ходов \(k\) \((0 \le k \le 10^4)\). Затем выведите \(i\) и \(j\) для каждого хода \((1 \le i, j \le n\); \(i \neq j)\).
Если существует несколько ответов, то выведите любой из них. Не требуется минимизировать количество ходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 2
1 2
2
2 1
1 2
4
2 3 1 2
2 3 2 3
|
0
-1
3
3 1
3 2
4 3
|