グリッド問題

$N \times M$ のグリッドがある。最初、すべてのマスは壊れていない。

ちょうど $X$ 個のマスを壊す。その後、壊れていない $NM-X$ 個のマスに $0,1,\cdots,NM-X-1$ をそれぞれちょうど 1 回ずつ書き込む。

整数 $L,R$ が $0 \le L<R<NM-X$ を満たすとする。$L \le i \le R$ を満たす整数 が書かれたマスだけを残したとき、それらのマスが 1 つの連結成分をなすなら、区間 を と呼ぶ。2 つのマスは辺を共有するときに限り隣接する。

すべての区間 $(L,R)$ が良い区間でないようにしたい。壊すマスの個数 $X$ の最小値を求め、その最小値を達成するグリッドの構成を 1 つ求めよ。

壊れていないマスが 1 個以下なら、$L<R$ を満たす区間が存在しないため、条件は自動的に満たされる。

入力は次の形式で与えられる。

$N\ M$

1 行目に、壊すマスの個数の最小値 $X$ を出力する。

続く $N$ 行に、それぞれ $M$ 個の整数 $B_{i,1},B_{i,2},\cdots,B_{i,M}$ を出力し、グリッドの構成を表す。

• $1 \le N,M \le 2000$.