题目描述

给定一个具有$N$个顶点和$M$条边的连通无向图。顶点编号为$1$到$N$，边由字符网格$S$描述。如果$S_{i,j}$是1，则存在连接顶点$i$和$j$的边；否则，不存在这样的边。

确定是否可以将顶点划分为非空集合$V_1, \\dots, V_k$，使满足以下条件。如果答案是肯定的，则找出满足条件的划分中最大可能的集合数$k$。

• 每条边连接两个属于两个"相邻"集合的顶点。更正式地说，对于每条边$(i,j)$，存在$1\\leq t\\leq k-1$使得$i\\in V_t,j\\in V_{t+1}$或$i\\in V_{t+1},j\\in V_t$成立。

约束条件

• $2 \leq N \leq 200$
• $S_{i,j}$是0或1。
• $S_{i,i}$是0。
• $S_{i,j}=S_{j,i}$
• 给定的图是连通的。
• $N$是一个整数。

输入

输入通过标准输入给出，格式如下：

$N$ $S_{1,1}...S_{1,N}$ $:$ $S_{N,1}...S_{N,N}$

输出

如果无法将顶点划分成满足条件的集合，则打印$\-1$。否则，打印满足条件的划分中最大可能的集合数$k$。

示例输入 1

2
01
10

示例输出 1

2

我们可以将顶点$1$放在$V_1$中，将顶点$2$放在$V_2$中。

示例输入 2

3
011
101
110

示例输出 2

-1

示例输入 3

6
010110
101001
010100
101000
100000
010000

示例输出 3

4