AT_waipc_qual_d Cyclic Present Exchange

$ 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 $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ 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 $ に座る子供の番号を表す．

### Sample Explanation 1 例えば， $ 1 $ つめのテストケースではフェーズ数を $ 1 $ とし，子供 $ 3,2,1 $ を椅子 $ 1,2,3 $ に座らせればよいです．このとき，以下のようにプレゼント交換が進む可能性があります． - 子どもたちがプレゼントを $ 0 $ 回時計回りに回す．子供 $ 1,2 $ の持ってきたプレゼントは，それぞれ子供 $ 1,2 $ の手にある状態で終わる． - 子どもたちがプレゼントを $ 1 $ 回時計回りに回す．子供 $ 1,2 $ の持ってきたプレゼントは，それぞれ子供 $ 3,1 $ の手にある状態で終わる． - 子どもたちがプレゼントを $ 2 $ 回時計回りに回す．子供 $ 1,2 $ の持ってきたプレゼントは，それぞれ子供 $ 2,3 $ の手にある状態で終わる． よって， $ 2 $ つの条件は両方とも満たされています． ### Constraints - $ 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 $ 以下 - 入力はすべて整数