#include <bits/stdc++.h>
using namespace std;
int G[1001][1001];

bool checkOddCycle(int src, int V){
    int colorArr[V];
    for(int i=0;i<V;i++){
        colorArr[i]=-1;
    }
    colorArr[src]=1;
    queue<int> q;
    q.push(src);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(G[u][u]==1){
            return true;
        }
        for(int v=0;v<V;v++){
            if(G[u][v]==1 && colorArr[v]==-1){
                colorArr[v]=1-colorArr[u];
                q.push(v);
            }
            else if(G[u][v]==1 && colorArr[v]==colorArr[u]){
                return true;
            }
        }
    }
    return false;
}

int findX(int n){
    if(checkOddCycle(0,n)==true){
        return -1;
    }
    int res=0;
    for(int i=0;i<n;i++){
        vector<int> group(n,0);
        vector<bool> vis(n,false);
        queue<int> q;
        q.push(i);
        group[i]=1;
        vis[i]=true;
    
        while(!q.empty()){
            int size=q.size();
            while(size--){
                int node=q.front();
                q.pop();
                for(int nei=0;nei<n;nei++){
                    if(G[node][nei]==1 && vis[nei]==false){
                        q.push(nei);
                        vis[nei]=true;
                        group[nei]=group[node]+1;
                    }
                }
            }
        }
        res=max(res,*max_element(group.begin(),group.end()));
    }
    return res;
}

int main() {
    memset(G,0,sizeof(G));
    G[0][8]=1;
    G[0][1]=1;
    G[0][6]=1;
    G[0][3]=1;
    
    G[1][2]=1;
    G[1][0]=1;
    
    G[2][6]=1;
    G[2][1]=1;
    
    G[3][4]=1;
    G[3][7]=1;
    G[3][0]=1;
    
    G[4][8]=1;
    G[4][5]=1;
    G[4][3]=1;
    
    G[5][4]=1;
    G[5][7]=1;
    
    G[6][0]=1;
    G[6][2]=1;
    G[6][7]=1;
    
    G[7][3]=1;
    G[7][6]=1;
    G[7][5]=1;
    
    G[8][4]=1;
    G[8][0]=1;
    cout<<findX(9)<<endl;   // ANSWER=4 (OUTPUT) 
 /*----------------------------------------------------------*/   
    
    memset(G,0,sizeof(G));
    G[0][1]=1;
    G[1][0]=1;
    cout<<findX(2)<<endl;   // ANSWER=2 (OUTPUT)
/*----------------------------------------------------------*/   
    
    memset(G,0,sizeof(G));
    G[0][1]=1;
    G[0][2]=1;
    
    G[1][0]=1;
    
    G[2][0]=1;
    cout<<findX(3)<<endl; 
 /*----------------------------------------------------------*/  
    
    memset(G,0,sizeof(G));
    G[0][1]=1;
    G[0][2]=1;
    G[0][3]=1;
    
    G[1][0]=1;
    G[1][2]=1;
    G[1][3]=1;
    
    G[2][0]=1;
    G[2][1]=1;
    G[2][3]=1;
    
    G[3][0]=1;
    G[3][1]=1;
    G[3][2]=1;
    cout<<findX(4); // ANSWER=-1 (OUTPUT) 
    return 0;
}

We are given N cities and M bridges, each bridge connects two cities where it is possible to travel from any one city to any other city using a sequence of bridges.

We want to divide these N cities into X disjoint groups G1, G2....Gx such that any one of the following conditions meet for any bridge that connects two cities A and B:

if A belongs to Gi then B belongs to Gi+1 (1 <= i <= x-1) if A belongs to Gi then B belongs to Gi-1 (2 <= i <= x) Find the maximum value of X, or print -1 if such division is impossible

Constraints 2 <= N <= 250

Input Format

First line contains N, an integer N line follows, one for each city, ith line contains N characters , where the jth character is 1 if there is a bridge between city i and j, else the character is 0

Sample Input 1

4 0111 1011 1101 1110

Sample Output 1

-1

Explanation It is not possible to divide the cities into different groups by following the given constraints

Sample Input 2

2 01 10

Sample Output 2

2

Explanation City 1 can be in 1st group and city 2 can be in 2nd group, hence, max value of x is 2

Sample Input 3

3 011 100 100

Sample output 3

3

Explanation City 2 can be in 1st group, city 1 can be in 2nd group and city 3 can be in 3nd group, hence, max value of x is 3

[execution time limit] 3 seconds (java)

[input] integer n

[input] array.array.char mat

N line follows, one for each city, ith line contains N characters , where the jth character is 1 if there is a bridge between city i and j, else the character is 0

[output] integer