#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int n;
int d[300][300];
int a[300];

int calc(int v){
	queue<int>que;
	memset(a,-1,sizeof(a));
	a[v]=0;
	que.push(v);
	int Max=0;
	while(!que.empty()){
		int p=que.front();que.pop();
		rep(i,n){
			if(d[p][i]==1){
				if(a[i]!=-1){
					if(abs(a[i]-a[p])!=1){
						return -2;
					}
				}
				else{
					a[i]=a[p]+1;
					Max=max(Max,a[i]);
					que.push(i);
				}
			}
		}
	}
	return Max;
}
int main(){
	cin>>n;
	rep(i,n)rep(j,n)scanf("%1d",&d[i][j]);
	//~ rep(i,n)for(int j=i+1;j<n;j++){
		//~ if(d[i][j]==1){
			//~ cout<<i<<' '<<j<<endl;
		//~ }
	//~ }
	//~ return 0;
	int Max=-2;
	rep(i,n)Max=max(Max,calc(i));
	cout<<Max+1<<endl;
}
### Prompt

Develop a solution in cpp to the problem described below:

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.

Determine 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.

* 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.

Constraints

* 2 \leq N \leq 200
* S_{i,j} is `0` or `1`.
* S_{i,i} is `0`.
* S_{i,j}=S_{j,i}
* The given graph is connected.
* N is an integer.

Input

Input is given from Standard Input in the following format:


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


Output

If it is impossible to divide the vertices into sets so that the condition is satisfied, print -1. Otherwise, print the maximum possible number of sets, k, in a division that satisfies the condition.

Examples

Input

2
01
10


Output

2


Input

3
011
101
110


Output

-1


Input

6
010110
101001
010100
101000
100000
010000


Output

4

### Response

```cpp
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int n;
int d[300][300];
int a[300];

int calc(int v){
	queue<int>que;
	memset(a,-1,sizeof(a));
	a[v]=0;
	que.push(v);
	int Max=0;
	while(!que.empty()){
		int p=que.front();que.pop();
		rep(i,n){
			if(d[p][i]==1){
				if(a[i]!=-1){
					if(abs(a[i]-a[p])!=1){
						return -2;
					}
				}
				else{
					a[i]=a[p]+1;
					Max=max(Max,a[i]);
					que.push(i);
				}
			}
		}
	}
	return Max;
}
int main(){
	cin>>n;
	rep(i,n)rep(j,n)scanf("%1d",&d[i][j]);
	//~ rep(i,n)for(int j=i+1;j<n;j++){
		//~ if(d[i][j]==1){
			//~ cout<<i<<' '<<j<<endl;
		//~ }
	//~ }
	//~ return 0;
	int Max=-2;
	rep(i,n)Max=max(Max,calc(i));
	cout<<Max+1<<endl;
}
```