Migrated from Lutece 3168 点分类

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一个 $n$ 个点的连通图，ljy 希望把这 $n$ 个点分入不同的集合中去，每个点只能被分入一个集合 $i$ 。为了提高分类过程中的乐趣，ljy 提出了一个要求，对于原图中相连的两个点，应该被分入两个序号相邻的集合中。请问是否存在这样的分类方案，如果存在，输出可以分出的最大的集合数。

Input

第一行一个整数 $n$，代表点的数量。 接下来是 $n×n$ 的邻接矩阵 $G$，表示各点的连通性。

Output

输出一行一个整数，表示可以分出的最大集合数。若没有方案输出 -1。

Samples

2
01
10

2

3
011
101
110

-1

6
010110
101001
010100
101000
100000
010000

4

Constraints

$2 \le n \le 200$ 邻接矩阵 $G$中的元素只可能为 $0$ 或 $1$，保证$G_{ij} = G_{ji}, G_{ii} = 0$。

Resources

2024 UESTC ICPC Training for Graph