Description

小C给了你一个简单无向连通图，有N个顶点和M条边。点从1到N编号。 通过一个二维矩阵S来给出边：如果S(i,j)是1 ,则表示存在一条连接点i和点 j的边，否则则表示不存在这样的边。

现在小C想让你判断：能否将所有的点划分到不同的非空点集中，满足条件：

•每条边连接的两个点属于两个相邻的集合。即对于每条边（i，j),存在

1=< t =< k — 1 满足 i ∈ Vt, j ∈V(t+1) 或 i ∈ V(t+1),j ∈ Vt

如果可以的话，小C想知道最多能够将原来的点集划分为多少个集合。

Input Format

输入 第一行输入一个整数 N

接下来一共N行，每行输入N个整数，表示题目中的S矩阵

Output Format

如果找不到合法的划分方式，输出-1。

否则输出最多能被划分成的集合的数量

Sample

样例数据 1 输入

2
01
10

输出

2

样例解释 我们可以把1号点放入集合1 ,然后把2号点放入集合2。 样例数据 2 输入

3
011
101
110

输出

-1

样例数据 3 输入

6
010110
101001
010100
101000
100000
010000

输出

4

Hint

2 < N < 200

• S(i,j)是0或1

• S(i,i) = 0

•给定图是连通的