Problem Description

There is an $n \times n$ chessboard, and each cell has a coin on it. $n$ is even. Each coin is either heads up or tails up. In one operation, you may choose a cell $(x,y)$, and then flip all coins in row $x$ and all coins in column $y$. Find the minimum number of operations needed to make all coins show the same side.

Input Format

The first line contains a positive integer $n$. The next $n$ lines each contain a $01$ string of length $n$, representing the states of the coins on the board.

Output Format

Only one line, the minimum number of operations needed.

4
0101
1000
0010
0101

2

Hint

Sample Explanation.

Perform operations on $(2,3)$ and $(3,1)$, and finally all coins become $1$.

Constraints.

For all data, $1\leq n \leq 1000$.

Translated by ChatGPT 5