AT_waipc_qual_d.Cyclic Present Exchange

有 $N$ 个小孩，编号为 $1$ 到 $N$，每个人都带着一个礼物聚集在一起。他们现在要进行礼物交换。具体来说，将进行以下操作：

• 首先，准备一个有 $N$ 条腿的椅子，将其环状摆放。椅子的编号沿顺时针为 $1,2,\ldots,N$。
• 接下来，进行 $0$ 次或更多的阶段。你需要在第一个阶段开始前决定阶段数 $k$ 以及每个阶段的座次安排 $p_{i,j}$（含义见下）。然后将这些信息传达给孩子们。之后，孩子们会进行 $k$ 次阶段。第 $i$ 次阶段包含如下步骤：
  • 首先，对于每个 $j$（$1 \leq j \leq N$），令小孩 $p_{i,j}$ 坐在第 $j$ 号椅子上。
  • 然后，孩子们可以进行 $0$ 至 $N-1$ 次如下操作：
    • 所有 $N$ 个孩子同时将自己当前持有的礼物传递给顺时针下一个椅子上的小孩。

你需要通过合适的阶段数和每个阶段的座次安排，使得下列 $M$ 个条件全部满足。

• 第 $i$ 个条件（$1 \leq i \leq M$）：如果每个阶段里礼物传递的次数合理指定，则最后可以让小孩 $1,2$ 各自带去的礼物分别落到小孩 $A_i,B_i$ 手中。

请你判断是否能够满足这些条件。如果可以，请求出所需的最小阶段数 $k$，以及一种实际可行的座位安排 $p_{i,j}$。

每组输入需要解答 $T$ 个测试用例。

输入以如下格式从标准输入读入：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每组测试用例格式为：

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

对于每个测试用例，若目标无法达成，则输出 -1。若可达成，则输出如下格式的答案：

$k$ $p_{1,1}$ $p_{1,2}$ $\ldots$ $p_{1,N}$ $p_{2,1}$ $p_{2,2}$ $\ldots$ $p_{2,N}$ $\vdots$ $p_{k,1}$ $p_{k,2}$ $\ldots$ $p_{k,N}$

其中 $k$ 为所需最小阶段数，$p_{i,j}$ 表示第 $i$ 阶段第 $j$ 号椅子的入座小孩编号。

样例解释 1

例如，在第一个测试用例中，只需 $1$ 个阶段，将小孩 $3,2,1$ 分别安排在第 $1,2,3$ 号椅子上。此时可能的礼物交换过程如下：

• 不进行任何传递时，小孩 $1,2$ 的礼物仍在自己手中。
• 传递 $1$ 次后，$1,2$ 的礼物分别变为在 $3,1$ 手中。
• 传递 $2$ 次后，$1,2$ 的礼物分别变为在 $2,3$ 手中。

因此，这两个条件都得以满足。

数据范围

• $1 \leq T \leq 64$
• $2 \leq N \leq 16$
• $1 \leq M \leq N(N-1)$
• $1 \leq A_i,B_i \leq N$
• $A_i \neq B_i$
• $(A_i,B_i) \neq (A_j,B_j)$（$i \neq j$）
• $T$ 个测试用例所有 $N^2$ 之和不超过 $16^2$
• 所有输入均为整数。

由 ChatGPT 5 翻译