题目描述

电路板排列问题是大规模电子系统设计中提出的问题。该问题的提法是，将$\red {n}$块电路板以最佳排列方案插入方案。

设$\red {B＝\{1，2，…，n\}}$是$\red {n}$块电路板的集合。集合$\red {L＝\{N _1~ ，N _2~ ，…，N _m~ \}}$是$\red {n}$块电路板的$\red {m}$个连接块。其中，每个连接$\red {N_i~}$是$\red {B}$的一个子集，且$\red {N_i~}$中的电路板用同一根导线连接在一起。例如，设$\red {n＝8，m＝5}$。给不定期$\red {n}$块电路板用其$\red {m}$个连接块如下：

$\red {B＝\{1，2，3，4，5，6，7，8\}}$

$\red {L\{N _1~ ，N _2~ ，N _3~ ，N _4~ ，N _5~ \}}$

$\red {N _1~ ＝\{4，5，6\}; N _2~ ＝\{2，3\}; N _3~ ＝\{1，3\}}$ $\red {N _4~ ＝\{3，6\}; N _5~ ＝\{7，8\}}$

这$\red {8}$块电路板的一个可能的排列如图所示。在最小长度电路板排列问题中，连接块的长度是指该连接块中第$\red {1}$块电路板到最后$\red {1}$块电路板之间的距离。例如，在图$\red {9}$所示的电路板排列中，连接块$\red {N_4}$的第一块电路板在插槽$\red 3$中，它的最后$\red {1}$块电路板在插槽$\red {6}$中，因此$\red {N_4~}$的长度为$\red {3}$。同理$\red {N_2~}$的长度为$\red {2}$。图$\red {9}$中连接块最大长度为$\red {3}$。试设计一个回溯法找出所给$\red {n}$个电路板的最佳排列，使得$\red {m}$个连接块中最大长度达到最小。 对于给定的电路板连接块，设计一个算法，找出所给$\red {n}$个电路板的最佳排列，使得$\red {m}$个连接块中最大长度达到最小。

输入格式

第$\red {1}$行$\red {2}$个整数$\red {n}$和$\red {m(1≤n,m≤20)}$。接下来的$\red {n}$行中，每行$\red {m}$个整数。第$\red {k}$行的第$\red {j}$个数为$\red {0}$表示电路板$\red {k}$不在第$\red {j}$个连接块中，为$\red {1}$表示电路板$\red {k}$在第$\red {j}$个连接块中。

输出格式

第一行为最大连接长度的最小值；接下来的一行是最佳排列。

样例

输入样例

8 5

1 1 1 1 1

0 1 0 1 0

0 1 1 1 0

1 0 1 1 0

1 0 1 0 0

1 1 0 1 0

0 0 0 0 1

0 1 0 0 1

输出样例

4

5 4 3 1 6 2 8 7