题目描述

给定一张 $N$ 个顶点，$M$ 条边的无向连通图。
顶点以 $1\ldots N$ 编号，边以仅包含 $\texttt{0/1}$ 的邻接矩阵的形式给出。

请判断是否能够将顶点分为 $k$ 个非空集合 $V_1,\ldots,V_k$，使得其满足以下条件。若可以，则最大化 $k$：

• 对于每条边 $(i,j)$，存在 $1 \le t \le k-1$ 满足 $i \in V_t, j \in V_{t+1}$ 或 $i \in V_{t+1}, j \in V_t$。

输入格式

第一行，一个正整数 $N$。
以下 $N$ 行，每行一个长度为 $N$ 的 $\texttt{0/1}$ 串，表示邻接矩阵。

输出格式

如果无法找到一种划分方案满足上述条件，输出 $-1$。
否则输出所有方案中最大的 $k$。

样例 1

输入

2
01
10

输出

2

样例 2

输入

3
011
101
110

输出

-1

样例 3

输入

6
010110
101001
010100
101000
100000
010000

输出

4

说明/提示

数据限制

• $N \in [2,200] \bigcap \mathbb Z$。
• 邻接矩阵仅由 $\texttt0$ 与 $\texttt1$ 组成。
• 邻接矩阵关于主对角线对称。
• 邻接矩阵主对角线均为 $\texttt0$（无自环）。
• 图一定连通。

样例解释 #1

可以分别将顶点 $1,2$ 分入 $V_1,V_2$。