配点 : $500$ 点

問題文

$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$ の最大値を出力せよ。

2
01
10

2

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

3
011
101
110

-1

6
010110
101001
010100
101000
100000
010000

4