{"problem":{"name":"Graph Partition","description":{"content":"Given is a connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the edges are described by a grid of characters $S$. If $S_{i,j}$ is `1`, there is an e","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc039_b"},"statements":[{"statement_type":"Markdown","content":"Given is a connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the edges are described by a grid of characters $S$. If $S_{i,j}$ is `1`, there is an edge connecting Vertex $i$ and $j$; otherwise, there is no such edge.\nDetermine whether it is possible to divide the vertices into non-empty sets $V_1, \\dots, V_k$ such that the following condition is satisfied. If the answer is yes, find the maximum possible number of sets, $k$, in such a division.\n\n*   Every edge connects two vertices belonging to two \"adjacent\" sets. More formally, for every edge $(i,j)$, there exists $1\\leq t\\leq k-1$ such that $i\\in V_t,j\\in V_{t+1}$ or $i\\in V_{t+1},j\\in V_t$ holds.\n\n## Constraints\n\n*   $2 \\leq N \\leq 200$\n*   $S_{i,j}$ is `0` or `1`.\n*   $S_{i,i}$ is `0`.\n*   $S_{i,j}=S_{j,i}$\n*   The given graph is connected.\n*   $N$ is an integer.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S_{1,1}...S_{1,N}$\n$:$\n$S_{N,1}...S_{N,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc039_b","tags":[],"sample_group":[["2\n01\n10","2\n\nWe can put Vertex $1$ in $V_1$ and Vertex $2$ in $V_2$."],["3\n011\n101\n110","\\-1"],["6\n010110\n101001\n010100\n101000\n100000\n010000","4"]],"created_at":"2026-03-03 11:01:14"}}