CF2268F Deglado

给定一个 $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$）。

每组测试样例包含若干个测试用例。第一行包含测试用例数量 $t$（$1 \leq t \leq 500$）。之后是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 80$）。 接下来的 $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$ 行，每行输出两个整数 $i_w$ 和 $j_w$（$1 \leq i_w, j_w < 2n$），表示在第 $w$ 次操作中选择的位置。

在第一个测试用例中，你可以通过一次操作将各列排好序。 在第二个测试用例中，可以证明你无法将所有列排序。 下图为第三个测试用例的示意图：  由 ChatGPT 5 翻译