E - Don't Isolate Elements /

問題文

• 1 \leq i \leq H を満たす整数 i を選び、1 \leq j \leq W を満たす全ての整数 j に対して A_{i,j} の値を 1-A_{i,j} で置き換える。

また、A_{i,j} は行列において上下左右に同じ値が存在しない、すなわち 4 つの整数組 (x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1) のいずれかであって、 1 \leq x \leq H, 1 \leq y \leq W かつ A_{i,j} = A_{x,y} を満たすものが存在しないとき、またそのときに限り孤立した要素であると定義されます。

制約

• 2 \leq H,W \leq 1000
• A_{i,j} = 0 または A_{i,j} = 1
• 入力はすべて整数

入力

H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}


入力例 1

3 3
1 1 0
1 0 1
1 0 0


出力例 1

1


i = 1 を選択し操作を行うと、A = ((0,0,1),(1,0,1),(1,0,0)) となり、孤立した要素は存在しなくなります。

入力例 2

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


出力例 2

2


入力例 3

2 3
0 1 0
0 1 1


出力例 3

-1


Score : 500 points

Problem Statement

You are given a matrix A with H rows and W columns. The value of each of its elements is 0 or 1. For an integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, we denote by A_{i,j} the element at the i-th row and j-th column.

You can perform the following operation on the matrix A any number of times (possibly zero):

• Choose an integer i such that 1 \leq i \leq H. For every integer j such that 1 \leq j \leq W, replace the value of A_{i,j} with 1-A_{i,j}.

A_{i,j} is said to be isolated if and only if there is no adjacent element with the same value; in other words, if and only if none of the four integer pairs (x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1) satisfies 1 \leq x \leq H, 1 \leq y \leq W, and A_{i,j} = A_{x,y}.

Determine if you can make the matrix A in such a state that no element is isolated by repeating the operation. If it is possible, find the minimum number of operations required to do so.

Constraints

• 2 \leq H,W \leq 1000
• A_{i,j} = 0 or A_{i,j} = 1
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}


Output

If you can make it in such a state that no element is isolated by repeating the operation, print the minimum number of operations required to do so; otherwise, print -1.

Sample Input 1

3 3
1 1 0
1 0 1
1 0 0


Sample Output 1

1


An operation with i = 1 makes A = ((0,0,1),(1,0,1),(1,0,0)), where there is no longer an isolated element.

Sample Input 2

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


Sample Output 2

2


Sample Input 3

2 3
0 1 0
0 1 1


Sample Output 3

-1