Problem:
 Score : 500 points    Problem Statement 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.        Sample Input 1 2
01
10      Sample Output 1 2  We can put Vertex 1 in V_1 and Vertex 2 in V_2 .       Sample Input 2 3
011
101
110      Sample Output 2 -1       Sample Input 3 6
010110
101001
010100
101000
100000
010000      Sample Output 3 4

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)

colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=[]
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.append(connection[next[i]][j])
    next=next2
    next2=[]
    
  return distance

ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Solution (Python):
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int8([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print((s[i][:,i].any()|s[j][:,j].any()or~int(m.max()))*-1)

Solution (Python):
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int32([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print((s[i][:,i].any()|s[j][:,j].any()or~int(m.max()))*-1)

Solution (Python):
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int32([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print(s[i][:,i].any()|s[j][:,j].any()and-1or-~int(m.max()))

Solution (Python):
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int32([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print(s[i][:,i].any()|s[j][:,j].any()and-1or int(m.max()+1))

Solution (Python):
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.array([list(map(int,t[:-1]))for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print((s[i][:,i].any()|s[j][:,j].any())*-1or int(m.max()+1))

Solution (Python):
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.array([list(map(int,t[:-1]))for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print((s[i][:,i]<1).all()*(s[j][:,j]<1).all()*int(m.max()+1)or-1)

Solution (Python):
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
m=csgraph.floyd_warshall(csr_matrix(s))
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]<1)*all(s[j][:,j]<1)*int(m.max()+1)or-1)

Solution (Python):
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
m=csgraph.floyd_warshall(csr_matrix(s))
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(m.max()+1)or-1)

Solution (Python):
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
g=csr_matrix(s)
m=csgraph.floyd_warshall(g)
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(m.max()+1)or-1)

Solution (Python):
from subprocess import*
call(('python3','-c',"""
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
g=csr_matrix(s)
m=csgraph.floyd_warshall(g)
d=m.max()
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(d+1)or-1)
"""))

Solution (Python):
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
g=csr_matrix(s)
m=csgraph.floyd_warshall(g)
d=m.max()
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(d+1)or-1)

Solution (Python):
from collections import deque

n = int(input())
edge = [[] for i in range(n)]

for i in range(n):
    S = input()
    for j in range(n):
        if S[j] == '1':
            edge[i].append(j)


def is_bipartite(num_of_node, edge):
    colors = [-1]*num_of_node
    start = 0
    todo = deque([[start, 0]])

    while todo:
        node, color = todo.popleft()
        new_color = 1 - color

        for new_node in edge[node]:
            if colors[new_node] == -1:
                colors[new_node] = new_color
                todo.append([new_node, new_color])

            elif colors[new_node] == color:
                return False

            else:
                continue
    return True


def get_max_distance(start, num_of_node, edge):
    distances = [-1] * num_of_node
    distances[start] = 1
    todo = deque([[start, 1]])

    while todo:
        node, dis = todo.popleft()

        for new_node in edge[node]:
            if distances[new_node] == -1:
                distances[new_node] = dis + 1
                todo.append([new_node, dis+1])
            else:
                continue

    return max(distances)


if is_bipartite(n, edge):
    print(max([get_max_distance(x, n, edge) for x in range(n)]))
else:
    print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

n = int(input())
l=[list(input()) for _ in range(n)]
es = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if l[i][j]=="1":
            es[i].append(j)
colors = [0 for _ in range(n)]

def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def is_nibu():
    return dfs(0,1)

if not is_nibu():
    print(-1)
    exit()



d = [[float("inf") for i in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        if l[i][j]=="1":
            d[i][j]=1

for i in range(n):
    d[i][i] = 0

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

ans=0
dd=warshall_floyd(d)
for i in range(n):
    ans=max(ans,max(dd[i]))

print(ans+1)

Solution (Python):
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
s = [[_ for _ in S()] for _ in range(N)]

root = [[] for _ in range(N+1)]
for i in range(N):
  for j in range(N):
    if s[i][j] == "1":
      root[i + 1].append(j + 1)


ans = -1
for i in range(1, N+1):
  Vnum = [-1 for _ in range(N+1)]
  Vnum[i] = 1

  queue = deque([i])
  while queue:
    
    x = queue.popleft()
    for j in root[x]:
      if Vnum[j] == -1:
        Vnum[j] = Vnum[x] +1
        queue.append(j)
      else:
        if Vnum[j] == Vnum[x] or abs(Vnum[j] - Vnum[x]) > 1:
          break
    else:
      continue
    break
  else:
    ans = max(ans, max(Vnum))

print(ans)

Solution (Python):
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
s = [[_ for _ in S()] for _ in range(N)]

root = [[] for _ in range(N+1)]
for i in range(N):
  for j in range(N):
    if s[i][j] == "1":
      root[i + 1].append(j + 1)
      root[j + 1].append(i + 1)
      s[j][i] = "0"


ans = -1
for i in range(1, N+1):
  Vnum = [-1 for _ in range(N+1)]
  Vnum[i] = 1

  queue = deque([i])
  while queue:
    
    x = queue.popleft()
    for j in root[x]:
      if Vnum[j] == -1:
        Vnum[j] = Vnum[x] +1
        queue.append(j)
      else:
        if Vnum[j] == Vnum[x] or abs(Vnum[j] - Vnum[x]) > 1:
          break
    else:
      continue
    break
  else:
    ans = max(ans, max(Vnum))

print(ans)

Solution (Python):
import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)

def main():
    def judge(u=0,b=False):
        bt[u]=b
        res=False
        for ku in range(n):
            if not to[u][ku]:continue
            if bt[ku]==b:
                return True
            if bt[ku]==None:
                res|=judge(ku,not b)
        return res

    def bfs(u):
        hp=[]
        heappush(hp,(0,u))
        while hp:
            d,u=heappop(hp)
            for v in range(n):
                if not to[u][v]:continue
                if dis[v]!=-1:continue
                dis[v]=d+1
                heappush(hp,(d+1,v))

    n = int(input())
    to = [[c == "1" for c in input()] for _ in range(n)]
    bt=[None]*n
    if judge():
        print(-1)
        exit()
    ans=0
    for u in range(n):
        dis=[-1]*n
        dis[u]=0
        bfs(u)
        ans=max(ans,max(dis)+1)
    print(ans)
main()

Solution (Python):
import sys
sys.setrecursionlimit(1000)
inf = float('inf')

N = int(input())
ad = [[int(e) for e in list(input())] for _ in range(N)]




visited = [-1] * N
flag = True


def dfs(v=0, color=0):
    visited[v] = color
    for nv, bit in enumerate(ad[v]):
        if not bit:
            continue
        ncolor = (color + 1) % 2
        if visited[nv] == -1:
            dfs(nv, ncolor)
        elif visited[nv] != ncolor:
            global flag
            flag = False

dfs()
if not flag:
    print(-1)
    exit()
    
def warshall_floyd(ad):
    N = len(ad)
    dist = [[inf] * N for _ in range(N)]
    for i, line in enumerate(ad):
        for j, p in enumerate(line):
            if p:
                dist[i][j] = 1
            if i == j:
                dist[i][j] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

dist = warshall_floyd(ad)

ans = 0
for i, line in enumerate(dist):
    for j, d in enumerate(line):
        if d != inf and d > ans:
            ans = d
ans += 1
print(ans)

Solution (Python):
def dfs(v, c):
    color[v] = c
    for i in range(n):
        if g[v][i] == 1:
            if color[i] == c:
                return False
            if color[i] == 0 and not dfs(i, -c):
                return False
    return True


n = int(input())
g = []
for i in range(n):
    s = list(map(int, list(input())))
    for j in range(n):
        if s[j] == 0:
            s[j] = 1000000
        if i == j:
            s[j] = 0
    g.append(s)


color = [0] * n
nibu = True
for i in range(n):
    if color[i] == 0:
        if not dfs(i, 1):
            nibu = False

if nibu:
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    ans = 0
    for i in range(n):
        ans = max(ans, max(g[i]))
    print(ans + 1)
else:
    print(-1)

Solution (Python):
'''
二部グラフ判定
'''
INFTY = 10**13
def floyd():
    for k in range(N):
        for i in range(N):
            if d[i][k] == INFTY:
                continue
            for j in range(N):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

def dfs(v, c):
    color[v] = c
    for i in G[v]:
        if color[i] == c:
            return False
        if color[i] == 0 and not dfs(i, -c):
            return False
    
    return True
def solve():
    for i in range(N):
        if color[i] == 0:
            if not dfs(i, 1):
                return False
    return True
N = int(input())
G = [[]for i in range(N)]
color = [0 for i in range(N)]

d = [[0 if i == j else INFTY for j in range(N)]for i in range(N)]
for i in range(N):
    S = input()
    for j, s in enumerate(S):
        if s == '1':
            G[i].append(j)
            d[i][j] = 1

ans = solve()
if ans:
    floyd()
    print(max([max(di)for di in d])+1)
    
else:
    print(-1)

Solution (Python):
def where(cond, A):
    return [ i for i in range(len(A)) if cond(A[i])]

N = int(input())
S = [ input() for _ in range(N) ]
uv = [ where(int, s) for s in S ]

ans = -1
for i in range(N):
    used = [False]*N
    used[i] = True
    cur = {i}
    nxt = set(uv[i])
    k = 1
    while nxt:
        k += 1
        prev = cur
        cur = nxt
        for c in cur:
            used[c] = True
        nxt = set()
        for u in cur:
            for v in uv[u]:
                if v in prev:
                    continue
                elif used[v]:
                    k = -1
                    break
                else:
                    nxt.add(v)
            else:
                continue
            break
        else:
            continue
        break
    else:
        if k > ans:
            ans = k

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**3)

n = int(input())
s = [list(map(int, list(input()))) for _ in range(n)]

c = [-1 for _ in range(n)]
e = [[] for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        if s[i][j] == 1:
            e[i].append(j)
            e[j].append(i)

def dfs(x, p, b):
    c[x] = b
    for f in e[x]:
        if f != p:
            if c[f] >= 0:
                if c[f] == c[x]:
                    print(-1)
                    exit()
            else:
                dfs(f, x, (b+1)%2)


dfs(0, 0, 0)

inf = float('inf')

for i in range(n-1):
    for j in range(i+1, n):
        if s[i][j] == 0:
            s[i][j] = inf
            s[j][i] = inf

def warshall_floyd(d):
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]
    return d

s = warshall_floyd(s)

ans = 0
for x in s:
    ans = max(max(x), ans)

print(ans+1)

Solution (Python):
from scipy.sparse.csgraph import dijkstra
from collections import deque
import sys
input = sys.stdin.readline
def isbipart(n,graph):  
  colors = [0 for i in range(n)]
  stack = deque([(0,1)])
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in graph[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to,-color))
  return True

def solve():
  n = int(input())
  graph = []
  for i in range(n):
    tmp = []
    s = input()
    for j in range(n):
      tmp.append(int(s[j]))
    graph.append(tmp)
  d = dijkstra(graph)
  
  newgraph = [[] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if graph[i][j] == 1:
        newgraph[i].append(j)
  ans = -1 * float("Inf")
  for i in range(n):
    for j in range(n):
      ans = max(ans,d[i][j])
  if isbipart(n,newgraph):
    print(int(ans)+1)
  else:
    print(-1)
solve()

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
from collections import deque
import sys
input = sys.stdin.readline
def isbipart(n,graph):  
  colors = [0 for i in range(n)]
  stack = deque([(0,1)])
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in graph[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to,-color))
  return True

def solve():
  n = int(input())
  graph = []
  for i in range(n):
    tmp = []
    s = input()
    for j in range(n):
      tmp.append(int(s[j]))
    graph.append(tmp)
  d = floyd_warshall(graph)
  
  newgraph = [[] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if graph[i][j] == 1:
        newgraph[i].append(j)
  ans = -1 * float("Inf")
  for i in range(n):
    for j in range(n):
      ans = max(ans,d[i][j])
  if isbipart(n,newgraph):
    print(int(ans)+1)
  else:
    print(-1)
solve()

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall


def main():
    n = int(input())
    s = [list(map(int, input())) for _ in range(n)]

    s = np.array(s)

    g = csgraph_from_dense(s)

    dist_mat = floyd_warshall(g).astype(np.int32)

    dist_max = dist_mat.max()

    a = np.where(dist_mat[0] % 2 == 0)
    b = np.where(dist_mat[0] % 2 == 1)
    bl = (s[a][:,a] == 0).all() and (s[b][:,b] == 0).all()

    ans = dist_max + 1 if bl else -1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
s = [input() for _ in range(n)]
parity = [-1 for _ in range(n)]

def dfs(x):
	for i in range(n):
		if s[x][i] == "1":
			if parity[i] == parity[x]:
				print(-1)
				sys.exit()
			elif parity[i] == -1:
				parity[i] = parity[x]^1
				dfs(i)
	return

parity[0] = 0
dfs(0)

dist = [[10**30 if s[i][j] == "0" else 1 for j in range(n)] for i in range(n)]
for i in range(n):
	dist[i][i] = 0

for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


diam = 0
for i in range(n):
	for j in range(n):
		if dist[i][j] < 10**30:
			diam = max(diam, dist[i][j])

print(diam+1)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getsize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

def isBipertite(es):
    n = len(es)
    uf = UnionFind(2 * n)
    for v, e in enumerate(es):
        for u in e:
            uf.unite(v, n+u)
            uf.unite(u, n+v)
    for v in range(n):
        if uf.same(v, n+v):
            return False
    return True

N = int(input())
es = [input() for i in range(N)]
for i in range(N):
    es[i] = [j for j in range(N) if es[i][j] == '1']
if isBipertite(es):
    d = [[INF] * N for i in range(N)]
    for i in range(N):
        d[i][i] = 0
    for v in range(N):
        for u in es[v]:
            d[v][u] = 1
    for w in range(N):
        for v in range(N):
            for u in range(N):
                d[v][u] = min(d[v][u], d[v][w]+d[w][u])
    print(max([max(d[v]) for v in range(N)])+1)
else:
    print(-1)

Solution (Python):
N = int(input())
S = [None] * N

for i in range(0, N):
    S[i] = [int(s) for s in list(input())]


def local_max_level(S, N, n): 
    levels = [None] * N
    levels[n] = 0

    for l in range(0, N): 
        for i in range(0, N): 
            if levels[i] == l: 
                
                for j in range(0, N): 
                    if S[i][j] == 1: 
                        if levels[j] == None:
                            levels[j] = l + 1

                        elif levels[j] == l - 1: continue
                        elif levels[j] == l + 1: continue
                        else:
                            return -1
    return max(levels)

def n_partite(S, N):

    M = 0
    for n in range(0, N):  
        m = local_max_level(S, N, n)
        if m == -1: 
            return -1
        else:
            M = max(M, m)
    return M + 1

print(n_partite(S, N))

Solution (Python):
import queue
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        

        edges = defaultdict(set)
        for i in range(N):
            for j, flag in enumerate(list(input().rstrip())):
                if int(flag):
                    edges[i + 1].add(j + 1)

        ans = -1
        for i in range(N):
            q = queue.Queue()
            colors = defaultdict(int)
            q.put((i + 1, 0))
            colors[i+1] = -1
            is_bipartite_graph = True
            distance = 0
            while not q.empty():
                node = q.get()

                edge = edges[node[0]]

                
                for to in edge:
                    if colors[to] == 0:
                        colors[to] = -1 * colors[node[0]]
                        q.put((to, node[1] + 1))
                        distance = max(distance, node[1] + 1)
                    elif colors[to] == colors[node[0]]:
                        is_bipartite_graph = False
                        break
                if not is_bipartite_graph:
                    break

            if is_bipartite_graph:
                ans = max(ans, distance + 1)

        print(ans)



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):
N = int(input())
G = [[int(x) for x in input()] for k in range(N)]
es = [[] for k in range(N)]

for k in range(N):
    for l in range(N):
        if G[k][l] == 1:
            es[k].append(l)






colors = [0 for i in range(N)]


def dfs(v,color):
    
    colors[v] = color
    
    for to in es[v]:
        
        if colors[to] == color:
            return False
        
        if colors[to] == 0 and not dfs(to, -color):
            return False
    
    return True


def is_bipartite():
    return dfs(0,1) 

if is_bipartite() == False:
    print(-1)
    exit(0)


D = [[float("inf") for k in range(N)] for l in range(N)]
for k in range(N):
    for l in range(N):
        if k == l:
            D[k][l] = 0
        elif G[k][l] == 1:
            D[k][l] = 1

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r],D[q][p]+D[p][r])
ans = 0
for k in range(N):
    for l in range(N):
        ans = max(ans, D[k][l]+1)

print(ans)

Solution (Python):
N = int(input())
S = []
for i in range(N):
    S.append(input())
    


L = [0 for i in range(N)]
L[0] = 1
q = [0]
res = 0

while len(q) > 0:
    idx = q.pop(-1)
    c = L[idx]*(-1)
    for i in range(N):
        if S[idx][i] == "1":
            if L[i] == 0:
                L[i] = c
                q.append(i)
            elif L[i] == c*(-1):
                res = 1
                q = []
                break
            

if res == 1:
    print(-1)
else:
    
    d = [[10**4 for j in range(N)] for i in range(N)]
    
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                d[i][j] = 1
    
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i != j:
                    d[i][j] = min(d[i][j], d[i][k]+d[k][j])

                
    ans = 0
    for i in range(N):
        for j in range(N):
            if d[i][j] < 10**4:
                ans = max(ans, d[i][j])
                
    print(ans+1)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7



show_flg=False


inf=float('inf')
n=I()
s=[[inf]*n for _ in range(n)]
g=[[] for i in range(n)]
for r in range(n):
    ri=list(input())
    for c in range(n):
        if ri[c]=='1':
            s[r][c]=1
            g[r].append((c,1))

def wf(d):
    n=len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

d=wf(s)
diam=-1
bg=0
ed=n-1
for r in range(n):
    for i,dist in enumerate(d[r]):
        if i==r:
            continue
        if diam<dist:
            diam=dist
            bg=r
            ed=i

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i,d in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+d
    return

bfs(bg)

for i in range(n):
    for nb,d in g[i]:
        if abs(v[nb]-v[i])!=1:
            print(-1)
            exit()

print(diam+1)
exit()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return [int(i) for i in input().rstrip()]
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    s = S()
    k = II()
    ans = 0
    lis = []
    i = 0
    tmp = 1
    while len(s) > i + 1:
        if s[i] == s[i + 1]:
            tmp += 1
        else:
            lis.append((s[i], tmp))
            tmp = 1
        i += 1
    lis.append((s[i], tmp))
    if lis[0][0] == lis[-1][0]:
        if len(lis) == 1:
            ans += k * lis[0][1] // 2
            print(ans)
            return
        ans -= (lis[0][1] // 2 + lis[-1][1] // 2) * (k - 1)
        ans += (lis[0][1] + lis[-1][1]) // 2 * (k - 1)
    for _, b in lis:
        ans += b // 2 * k
    print(ans)
    return


def B():
    n = II()
    s = SR(n)
    edg = [[] for i in range(n)]
    check = [0] * n
    for i in range(n):
        for k in range(n):
            if i == k:
                continue
            if s[i][k]:
                edg[i].append(k)
                edg[k].append(i)
            else:
                s[i][k] = inf
    for i in range(n):
        q = deque([i])
        if check[i] == 0:
            check[i] += 1
        while q:
            p = q.pop()
            for k in edg[p]:
                if check[k]:
                    if (check[k] ^ check[p]) & 1:
                        continue
                    print(-1)
                    return
                else:
                    check[k] = check[p] + 1
                    q.appendleft(k)

    for x in range(n):
        for i in range(n):
            for k in range(n):
                s[i][k] = min(s[i][k], s[i][x] + s[x][k])
    ans = 0
    for i in range(n):
        for k in range(n):
            if s[i][k] == inf:
                continue
            ans = max(s[i][k], ans)
    print(ans+1)

def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    B()

Solution (Python):
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        while que:
            v, c = que.popleft()
            if col[v] == -1:
                col[v] = c
            elif col[v] == c:
                continue
            else:
                return 0
            for ne in E[v]:
                if col[ne] == c:
                    return 0
                if col[ne] < 0:
                    que.append([ne, 1-c])
    return 1

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(max([max(BFS(N, X, i)) for i in range(N)])+1)
else:
    print(-1)

Solution (Python):
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    f = 0
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        while que:
            v, c = que.popleft()
            if col[v] == -1:
                col[v] = c
            elif col[v] == c:
                continue
            else:
                f = 1
                break
            for ne in E[v]:
                if col[ne] == c:
                    f = 1
                    break
                if col[ne] < 0:
                    que.append([ne, 1-c])

            if f:
                break
        if f:
            break
    return 1-f

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(max([max(BFS(N, X, i)) for i in range(N)])+1)
else:
    print(-1)