def wd(a)
  n=a.size-1
  0.upto(n){|k|0.upto(n){|i|0.upto(n){|j|a[i][j]=[a[i][j],a[i][k]+a[k][j]].min}}}
end
class UnionFind
  def initialize(size)
    @rank = Array.new(size, 0)
    @parent = Array.new(size, &:itself)
  end

  def unite(id_x, id_y)
    x_parent = get_parent(id_x)
    y_parent = get_parent(id_y)
    return if x_parent == y_parent

    if @rank[x_parent] > @rank[y_parent]
      @parent[y_parent] = x_parent
    else
      @parent[x_parent] = y_parent
      @rank[y_parent] += 1 if @rank[x_parent] == @rank[y_parent]
    end
  end

  def get_parent(id_x)
    @parent[id_x] == id_x ? id_x : (@parent[id_x] = get_parent(@parent[id_x]))
  end

  def same_parent?(id_x, id_y)
    get_parent(id_x) == get_parent(id_y)
  end
end

n=gets.to_i
a=n.times.map{gets.chomp.split("").map(&:to_i)}
u=UnionFind.new(a.size*2)
a.each_with_index{|x,i|
  x.each_with_index{|y,j|
    next if i>=j
    if y==1
      u.unite(i,j+n)
      u.unite(i+n,j)
    end
    }}
0.upto(n-1){|i| puts -1 or exit if u.same_parent?(i,i+n) }
a.map!{|x| x.map!{|y| y==0 ? 100000 : y}}
wd(a)
0.upto(a.size-1){|i| a[i][i]=0}
d=a.map{|x| x.max}.max
puts d+1