AT_agc039_b [AGC039B] Graph Partition

[problemUrl]: https://atcoder.jp/contests/agc039/tasks/agc039_b $ 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 $ の最大値を出力せよ。

### 制約 - $ 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 $ に含めればよいです。