426. Minimum Swaps for Chessboard Transformation

0

Hard

M.S. Dhoni and Virat Kohli have a strong interest in chess. Virat presents Dhoni with a square matrix of size N × N, filled with only

**zeros**and**ones**. Dhoni's task is to transform the given matrix into a chessboard configuration. To achieve this, Dhoni can perform the following operations:- Swap any two
**rows**of the matrix. - Swap any two
**columns**of the matrix.

**NOTE:**In a**chessboard**, no adjacent elements (vertically or horizontally) are the same. Therefore, the chessboard may start with a 0 in the top-left corner.Input Format

The first line contains an integer N, representing the size of the matrix. The next N lines contain N space-separated 0's or 1's, representing the elements of the matrix.

Output Format

Print the minimum number of swaps required.

*If it is impossible to obtain a chessboard configuration from the given matrix, print -1.*Example

Input

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

Output

2

Constraints

2 <= N <= 30

A

A

_{ij}= 0 or 1Loading...

View Submissions

Console