問題文

ちわわは算数の天才だが、最近衰えを感じている。
このままではいけないと思ったちわわは、あるパズルを毎朝することにした。

• 盤面は縦M×横Nマスである。
• マスは表が白、裏が黒で、初期状態では何枚かがひっくり返っている。
• あるマスをひっくり返すと、それに同期して8近傍の周囲のマスがひっくり返る。
  （端の場合は周囲のひっくり返せるマスのみ）
• このゲームの目的は、最短手順で全てのマスを表向きにすることである。

入力

M N
\(\begin{array}{cccc}
    a_{ 1,1 } & a_{ 1,2 } & \ldots & a_{ 1,N } \\
    a_{ 2,1 } & a_{ 2,2 } & \ldots & a_{ 2,N } \\
    \vdots & \vdots & \ddots & \vdots \\
    a_{ M,1 } & a_{ M,2 } & \ldots & a_{ M,N }
\end{array}\)

\(a_{ i,j }\)は、盤面の\(i\)行目\(j\)列目を指し、表ならば0, 裏ならば1である。

\( 1 \leq M,N \leq 8 \)

出力

全てのマスをひっくり返す手順数が存在するならばその最短手順数を、存在しないならば"Impossible"を出力せよ。

サンプル

5 5
0 0 1 1 1
0 0 1 1 1
1 1 0 1 1
1 1 1 0 0
1 1 1 0 0

2

4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

16

8 5
0 0 1 1 1
0 0 1 1 1
0 1 0 0 1
1 0 0 1 0
1 1 1 0 0
1 0 1 0 1
0 1 0 0 1
0 0 1 1 1

5