F. Дегладо
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана таблица размера $$$2n \times 2n$$$, обозначаемая через $$$a$$$, каждый столбец которой является перестановкой$$$^{\text{∗}}$$$ длины $$$2n$$$.

Необходимо отсортировать все столбцы по возрастанию сверху вниз с помощью следующей операции:

  • Выбрать подтаблицу размера $$$2 \times 2$$$ и поменять местами два верхних элемента с двумя нижними элементами.

    Формально, можно выбрать два целых числа $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \lt 2n$$$), а затем поменять местами $$$a_{i,j}$$$ с $$$a_{i+1,j}$$$ и $$$a_{i,j+1}$$$ с $$$a_{i+1,j+1}$$$.

Необходимо отсортировать все столбцы не более чем за $$$n \cdot \binom{2n}{2} + 9n$$$ операций или определить, что это невозможно.

Заметим, что не требуется минимизировать количество операций.

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 80$$$).

$$$i$$$-я из следующих $$$2n$$$ строк содержит $$$2n$$$ целых чисел $$$a_{i,1},a_{i,2},\ldots,a_{i,2n}$$$ ($$$1 \leq a_{i,j} \leq 2n$$$) — элементы $$$i$$$-й строки таблицы.

Гарантируется, что каждый столбец таблицы образует перестановку длины $$$2n$$$.

Гарантируется, что сумма значений $$$n^3$$$ по всем наборам входных данных не превосходит $$$80^3$$$.

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

Для каждого набора входных данных, если отсортировать все столбцы не более чем за $$$n \cdot \binom{2n}{2} + 9n$$$ операций невозможно, выведите $$$-1$$$ в отдельной строке.

В противном случае в первой строке выведите одно целое число $$$k$$$ ($$$0 \leq k \leq n \cdot \binom{2n}{2} + 9n$$$) — количество операций.

Затем выведите $$$k$$$ строк, в $$$w$$$-й из которых должны находиться два целых числа $$$i_w$$$ и $$$j_w$$$ ($$$1 \leq i_w, j_w \lt 2n$$$) — значения $$$i_w$$$ и $$$j_w$$$, выбранные в $$$w$$$-й операции.

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

В первом наборе входных данных можно отсортировать столбцы с помощью одной операции.

Можно доказать, что во втором наборе входных данных отсортировать столбцы невозможно.

Иллюстрация третьего набора входных данных: