CF2268F.Deglado

You are given a $2n \times 2n$ grid $a$ where each column is a permutation$^{\text{∗}}$ of length $2n$.

We want to sort all columns in ascending order from top to bottom by performing the following operation:

• Choose a $2 \times 2$ subgrid and swap the two top elements with the two bottom elements.

  More formally, you can choose two integers $i$ and $j$ ($1 \leq i, j \lt 2n$), then swap $a_{i,j}$ with $a_{i+1,j}$ and swap $a_{i,j+1}$ with $a_{i+1,j+1}$.

You have to sort all columns using at most $n \cdot \binom{2n}{2} + 9n$ operations, or determine that it is impossible.

Note that you do not need to minimize the number of operations.

$^{\text{∗}}$A permutation of length $m$ is an array consisting of $m$ distinct integers from $1$ to $m$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($m=3$ but there is $4$ in the array).

给你一个 $2n \times 2n$ 的网格 $a$，其中每一列都是长度为 $2n$ 的一个排列$^{\text{∗}}$。

我们希望通过执行如下操作，将所有列按从上到下的升序排序：

• 选择一个 $2 \times 2$ 的子网格，并将其中的两个上方元素与两个下方元素互换。

  更准确地说，你可以选择两个整数 $i$ 和 $j$（满足 $1 \leq i, j < 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$ 的排列是指由 $1$ 到 $m$ 中互不相同的 $m$ 个整数组成的任意顺序的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $m = 3$，但数组中出现了 $4$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test contains a single integer $n$ ($1 \leq n \leq 80$).

The $i$-th line of the next $2n$ lines contains $2n$ integers $a_{i,1},a_{i,2},\ldots,a_{i,2n}$ ($1 \leq a_{i,j} \leq 2n$) — the elements of the $i$-th row of the grid.

It is guaranteed that every column in the grid forms a permutation of length $2n$.

It is guaranteed that the sum of $n^3$ over all test cases does not exceed $80^3$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 80$）。

接下来 $2n$ 行中的第 $i$ 行包含 $2n$ 个整数 $a_{i,1},a_{i,2},\ldots,a_{i,2n}$（$1 \leq a_{i,j} \leq 2n$）——即网格第 $i$ 行的元素。

保证网格中每一列均为长度为 $2n$ 的一个排列。

保证所有测试用例的 $n^3$ 之和不超过 $80^3$。

For each test case, if it is impossible to sort all columns in at most $n \cdot \binom{2n}{2} + 9n$ operations, print $-1$ in a single line.

Otherwise, in the first line print a single integer $k$ ($0 \leq k \leq n \cdot \binom{2n}{2} + 9n$) — the number of operations.

Then $k$ lines follow, the $w$-th line containing two integers $i_w$ and $j_w$ ($1 \leq i_w, j_w \lt 2n$) — you choose $i_w$ and $j_w$ in the $w$-th operation.

对于每个测试用例，如果无法在至多 $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$），表示你在第 $w$ 次操作中选择的 $i_w$ 和 $j_w$。

In the first test case, you can sort columns using one operation.

In the second test case, it can be shown that you cannot sort columns.

The illustration of the third test case:

在第一个测试用例中，你可以通过一次操作对列进行排序。

在第二个测试用例中，可以证明你无法对列进行排序。

第三个测试用例的示意图：