D - Cyclic Present Exchange Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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 つの条件は両方とも満たされています．