Coin Flipping on Chessboard

You are given an even-sized chessboard with n rows and n columns. Each cell contains a coin, which is either heads (denoted by 0) or tails (denoted by 1). In one operation, you may choose a cell \((x, y)\) and flip all coins in row \(x\) and all coins in column \(y\); note that the coin at \((x,y)\) is flipped twice and hence remains unchanged.

The goal is to make all coins show the same face (all 0’s or all 1’s) using the minimum number of operations. If it is impossible to achieve a uniform board, output -1.

Explanation: Let the initial state of the coin at cell \((i,j)\) be \(a_{i,j} \in \{0,1\}\). Performing a sequence of operations can be modeled in \(\mathbb{F}_2\) (mod 2 arithmetic). Each operation on cell \((x,y)\) contributes +1 (mod2) to every coin in row \(x\) (except that the cell \((x,y)\) is also flipped by the column flip, resulting in 2 flips, which is 0 mod2) and +1 mod2 to every coin in column \(y\). Hence the final state of coin \((i,j)\) is:

[ a_{i,j} + r_i + c_j \equiv T \quad (\text{mod }2), ]

where \(r_i, c_j \in \{0,1\}\) indicate whether row \(i\) and column \(j\) have been flipped an odd number of times, and \(T \in \{0,1\}\) is the desired final state. A necessary and sufficient condition for a solution is that for every row \(i\), the row is either identical to the first row or its bitwise complement. In that case, if we let \(k\) be the number of rows which are identical to row 1 and let ones be the number of 1’s in the first row, then a solution exists only if either

[ ones = k \quad \text{or} \quad ones = n - k. ]

In such a case, the minimum number of operations needed is min(k, n - k), because one valid strategy is to decide on the parity for row 1 (denoted by \(r_1\)) and the target state \(T\), from which the parity for all rows and columns is uniquely determined. Otherwise, output -1.

inputFormat

The first line of input contains an even integer n (\(2 \le n \le 1000\)). Each of the next n lines contains n integers (each either 0 or 1), separated by spaces, representing the initial state of the coins on the board.

outputFormat

Output a single integer: the minimum number of operations required to make all coins show the same face. If it is impossible to achieve, output -1.

sample

2
0 1
1 0

1