← 返回题目列表

AtCoder · waipc_qual_d

D. 循环当前交换

中文机器翻译题面 查看原题

配点 : 1200 点

問題文

1 减去 N 编号最多为 N 个孩子,每个人带来了 1 份礼物聚在一起。从现在开始,他们准备进行礼物交换。具体来说,进行以下操作。准备

  • 第一 砍倒 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} 该值应乘以 1 请找到一个。

1 对于每个输入,T 请解答案例。

制約

  • 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 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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

4
3 2
2 3
3 1
3 1
1 3
4 4
1 2
2 3
3 4
4 1
14 1
1 2

出力例 1

1
3 2 1
-1
1
4 1 2 3
0

例如, 当分解为1 第几个测试案例的阶段数为 1 ,让孩子 3,2,1 坐在椅子 1,2,3 上即可。这时,礼物交换可能会按如下进行。

  • 孩子们将礼物 0 顺时针转动次。孩子 1,2 带来的礼物将分别给每个孩子 1,2 以…手中状态结束。
  • 孩子们将礼物 1 顺时针转动次。孩子 1,2 带来的礼物将分别给每个孩子 3,1 以…手中状态结束。
  • 孩子们将礼物 2 顺时针转动次。孩子 1,2 带来的礼物将分别给每个孩子 2,3 以…手中状态结束。

因此, 正确答案是输出2 两个条件都满足。