問題文

音楽班では現在、アルバムの楽曲の並び順を考えています。

音楽班で自作した楽曲は全部で $N$ 曲あり、順に楽曲 $1$、楽曲 $2$、$\dotsc$、楽曲 $N$ と名付けられています。

音楽班には $M$ 人の学生が在籍しており、各学生が$1$通りずつ並び順の例を提案しています。

学生 $i$ が提案した並び順の $j$ 番目の楽曲は曲 $A_{i,j}$ であり、学生 $i$ はアルバムにおいて、 楽曲 $A_{i,j}$ の次の楽曲が $A_{i,j+1}$ $(1 \leq j \leq N - 1)$ であるとき満足度$1$を得るとします。

各学生の満足度の和の最大値と、それを満たす楽曲の並び順をひとつ求めてください。

制約

• $2 \leq N \leq 8$
• $1 \leq M \leq 100$
• 各 $i$ $(1 \leq i \leq N)$ に対し、$(A_{i,1},A_{i,2},\dotsc,A_{i,M})$ は $(1,2,\dotsc,M)$ の並び替え
• 入力は全て整数

入力

出力

満足度の和の最大値を $X$ 、それを満たす並び順を $Y_1,Y_2,\dotsc,Y_N$ とするとき、以下の形式で出力してください。

サンプル

3 3
1 2 3
1 3 2
2 3 1

3
1 2 3

2 2
1 2
2 1

1
2 1

条件を満たす並び順が複数存在する場合、そのうちどの並び順を出力しても構いません。