题目描述

$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$ のいずれかを満たす。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を満たす分割が不可能な場合、$-1$ を出力せよ。 そうでない場合、集合の個数 $k$ の最大値を出力せよ。

题目大意

题目描述

给定一张 $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$。

说明/提示

数据限制

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

样例解释 #1

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

2
01
10

2

3
011
101
110

-1

6
010110
101001
010100
101000
100000
010000

4

提示

制約

• $2\ \leq\ N\ \leq\ 200$
• $S_{i,j}$ は 0 または 1 である
• $S_{i,i}$ は 0 である
• $S_{i,j}=S_{j,i}$
• 与えられるグラフは連結
• $N$ は整数である

Sample Explanation 1

頂点 $1,2$ をそれぞれ $V_1,V_2$ に含めればよいです。