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