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