配点 : 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 两个条件都满足。