#898. 矩阵变换

矩阵变换

样例下载

题目描述

有一个 n×nn \times n 的 01 矩阵。

现在有一种操作:任意选择两个整数 i,j∈[1,n]i, j \in [1, n],将 (i,1),(i,2),…,(i,n)(i, 1), (i, 2), \ldots, (i, n) 的值依次赋给 (1,j),(2,j),…,(n,j)(1, j), (2, j), \ldots, (n, j)。

你可以操作任意次。

你的任务是将矩阵所有元素全部变成 1。如果能够办到,输出最少操作次数,否则输出 -1 。

输入格式

第一行一个整数 n。

接下来是一个 n×nn \times n 的 01 矩阵。

输出格式

输出只有一行,一个整数表示答案。

样例 1

输入

2
10
01

输出

3

样例 2

输入

2
00
00

输出

-1

数据范围

对于 30% 的数据,n ≤ 4;

对于另外 20% 的数据,满足每一列都至少有一个 1;

对于 100% 的数据,1 ≤ n ≤ 1000。