Minimum Flips to Uniform Binary Matrix

You are given an (N \times M) binary matrix. Your task is to determine the minimum number of flips required to make all cells in the matrix equal (i.e. all 0s or all 1s). A flip changes a single cell from 0 to 1 or from 1 to 0. If the matrix is already uniform, then no flips are needed (answer is 0). Otherwise, under certain conditions described below, one flip might be enough to make the matrix uniform. If it is impossible to achieve uniformity with the allowed operation(s), output -1.

For an (N \times M) matrix with (T = N \times M) cells, let (k) be the number of 1s in the matrix. The answer is defined as follows:
[ \text{Answer} = \begin{cases} 0 & \text{if } k = 0 \text{ or } k = T, \ -1 & \text{if } T \text{ is odd and } k \neq \lfloor T/2 \rfloor \text{ and } k \neq \lfloor T/2 \rfloor + 1, \ 1 & \text{otherwise.} \end{cases} ] Note that for matrices with an even number of cells, if the matrix is not already uniform, it is always considered to be fixable with exactly one flip.

inputFormat

The first line of input contains two integers \(N\) and \(M\) representing the number of rows and columns of the matrix, respectively.

Each of the following \(N\) lines contains \(M\) space-separated integers (each either 0 or 1) representing the rows of the matrix.

outputFormat

Output a single integer: the minimum number of flips required to transform the matrix into a uniform matrix (all elements the same), or -1 if it is impossible.

3 3
0 1 0
1 0 1
0 1 0

1