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):

from collections import deque

N = int(input())
S = [input() for _ in range(N)]
es = [[] for _ in range(N)]

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)

INF = float("inf")
def solve(s):
    dist = [INF] * N
    dist[s] = 0
    union = [[] for _ in range(N)]
    union[0].append(s)

    q = deque()
    q.append(s)
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[curr] + 1 >= dist[nxt]:
                continue

            dist[nxt] = dist[curr] + 1
            union[dist[nxt]].append(nxt)
            q.append(nxt)

    return dist, union



d, u = solve(0)

for i in range(N):
    if len(u[i]) > 1:
        for a in u[i]:
            for b in u[i]:
                if S[a][b] == "1":
                    print(-1)
                    exit()

ans = 0
for i in range(N):
    d, _ = solve(i)
    ans = max(ans, max(d) + 1)

print(ans)

Solution (Python):
n=int(input())
l=[[j for j,k in enumerate(input())if k=="1"]for i in range(n)]
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(2*n)
for i in range(n):
    for ne in l[i]:
        uf.unite(i,ne+n)
        uf.unite(i+n,ne)

if uf.same(0,n):
    print(-1)

else:
    class WarshallFloyd:
        
        def __init__(self,n,_first_index=0):
            self.v = n
            self._first_idx=_first_index
            self.d = [[float("INF")]*(n) for _ in range(n)]
            for i in range(n):
                self.d[i][i] = 0
    
        def path(self,x,y,c):
            if x == y:
                return False
            f=self._first_idx
            self.d[x-f][y-f] = c
            self.d[y-f][x-f] = c
            return True
    
        def build(self):
            for k in range(self.v):
                for i in range(self.v):
                    for j in range(self.v):
                        self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
            return self.d
    w=WarshallFloyd(n)
    for x in range(n):
        for j in l[x]:
            w.path(x,j,1)
    d=w.build()
    ans=0
    for i in range(n):
        ans=max(ans,max(d[i]))
    print(ans+1)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]

from collections import defaultdict, deque 


N = ii()

rel = [[] for _ in range(N)]

for i in range(N):
    S = input()
    l = []
    for j in range(N):
        if S[j] == '1':
            l.append(j)
    rel[i] = l

flag = [0]*N
ans = 0

for i in range(N):
    flag = [0]*N
    que = deque([i])
    add = 0
    flag[i] = 1
    while que != deque([]):
        node = que.popleft()
        for nn in rel[node]:
            if not flag[nn]:
                que.append(nn)
                flag[nn] = flag[node] + 1
    ans = max(ans, max(flag))

for i in range(N):
    for t in rel[i]:
        if abs(flag[t] - flag[i]) != 1:
            print(-1)
            exit()

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]

from collections import defaultdict, deque 


N = ii()

rel = [[] for _ in range(N)]

for i in range(N):
    S = input()
    l = []
    for j in range(N):
        if S[j] == '1':
            l.append(j)
    rel[i] = l

flag = [0]*N
ans = 0

for i in range(N):
    flag = [0]*N
    que = deque([i])
    add = 0
    flag[i] = 1
    while que != deque([]):
        node = que.popleft()
        for nn in rel[node]:
            if not flag[nn]:
                que.append(nn)
                flag[nn] = flag[node] + 1
    ans = max(ans, max(flag))

for i in range(N):
    for t in rel[i]:
        if abs(flag[t] - flag[i]) != 1:
            print(-1)
            exit()

print(ans)

Solution (Python):
def warshall_floyd(g):
    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])

n = int(input())
s = [[int(i) for i in list(input())] for _ in range(n)]
graph = [[float("inf")]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == 1:
            graph[i][j] = 1
        if i == j:
            graph[i][j] = 0

warshall_floyd(graph)
d = 0

for i in range(n-1):
    for j in range(i+1,n):
        if graph[i][j] != float("inf"):
            if d < graph[i][j]:
                start = i
                end = j
                d = graph[i][j]

v = [[] for _ in range(d+1)]
for i in range(n):
    l = graph[start]
    v[l[i]].append(i)



for l in v:
    m = len(l)
    for i in range(m-1):
        for j in range(i+1,m):
            if s[l[i]][l[j]] == 1:
                print(-1)
                quit()
print(d+1)

Solution (Python):
n=int(input())
l=[[j for j,k in enumerate(input())if k=="1"]for i in range(n)]
import sys
sys.setrecursionlimit(10**9)
color=[0]*n
def nibu(v,c):
    
    color[v]=c
    for i in l[v]:
        if color[i]==c:return False
        elif color[i]==0 and not nibu(i,-c):
            return False
    return True
if not nibu(0,1):
    print(-1)

else:
    class WarshallFloyd:
        
        def __init__(self,n,_first_index=0):
            self.v = n
            self._first_idx=_first_index
            self.d = [[float("INF")]*(n) for _ in range(n)]
            for i in range(n):
                self.d[i][i] = 0
    
        def path(self,x,y,c):
            if x == y:
                return False
            f=self._first_idx
            self.d[x-f][y-f] = c
            self.d[y-f][x-f] = c
            return True
    
        def build(self):
            for k in range(self.v):
                for i in range(self.v):
                    for j in range(self.v):
                        self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
            return self.d
    w=WarshallFloyd(n)
    for x in range(n):
        for j in l[x]:
            w.path(x,j,1)
    d=w.build()
    ans=0
    for i in range(n):
        ans=max(ans,max(d[i]))
    print(ans+1)

Solution (Python):
n=int(input())
l=[[j for j,k in enumerate(input())if k=="1"]for i in range(n)]
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(2*n)
for i in range(n):
    for ne in l[i]:
        uf.unite(i,ne+n)
        uf.unite(i+n,ne)
notnibu=0
for i in range(n):
    notnibu|=uf.same(i,i+n)
if notnibu:
    print(-1)

else:
    class WarshallFloyd:
        
        def __init__(self,n,_first_index=0):
            self.v = n
            self._first_idx=_first_index
            self.d = [[float("INF")]*(n) for _ in range(n)]
            for i in range(n):
                self.d[i][i] = 0
    
        def path(self,x,y,c):
            if x == y:
                return False
            f=self._first_idx
            self.d[x-f][y-f] = c
            self.d[y-f][x-f] = c
            return True
    
        def build(self):
            for k in range(self.v):
                for i in range(self.v):
                    for j in range(self.v):
                        self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
            return self.d
    w=WarshallFloyd(n)
    for x in range(n):
        for j in l[x]:
            w.path(x,j,1)
    d=w.build()
    ans=0
    for i in range(n):
        ans=max(ans,max(d[i]))
    print(ans+1)

Solution (Python):
n=int(input())
l=[[j for j,k in enumerate(input())if k=="1"]for i in range(n)]
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(2*n)
for i in range(n):
    for j in l[i]:
        uf.unite(i,j+n)
        uf.unite(i+n,j)
f=0
for i in range(n):
    f|=uf.same(i,i+n)

if f:
    print(-1)

else:
    class WarshallFloyd:
        
        def __init__(self,n,_first_index=0):
            self.v = n
            self._first_idx=_first_index
            self.d = [[float("INF")]*(n) for _ in range(n)]
            for i in range(n):
                self.d[i][i] = 0
    
        def path(self,x,y,c):
            if x == y:
                return False
            f=self._first_idx
            self.d[x-f][y-f] = c
            self.d[y-f][x-f] = c
            return True
    
        def build(self):
            for k in range(self.v):
                for i in range(self.v):
                    for j in range(self.v):
                        self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
            return self.d
    w=WarshallFloyd(n)
    for x in range(n):
        for j in l[x]:
            w.path(x,j,1)
    d=w.build()
    ans=0
    for i in range(n):
        ans=max(ans,max(d[i]))
    print(ans+1)

Solution (Python):
n=int(input())
s=[list(map(int,list(input()))) for _ in range(n)]
g=[[]for _ in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    if s[i][j]==1:
      g[i].append(j)
      g[j].append(i)
from collections import deque
def bfs(i):
  seen=[0]*n
  seen[i]=1
  todo=deque([[i,-1]])
  while todo:
    t,p=todo.popleft()
    l=g[t]
    for li in l:
      if li==p:
        continue
      if seen[li]==0:
        seen[li]=seen[t]+1
        todo.append([li,t])
      elif abs(seen[li]-seen[t])==1:
        pass
      else:
        return -1
  return max(seen)
ans=-1
for i in range(n):
  ans=max(bfs(i),ans)
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
S = [list(input()) for _ in range(N)]
INF = 10**12
dist = [[INF]*N for _ in range(N)]
edge = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i==j:
            dist[i][j] = 0
        if S[i][j]=='1':
            edge[i].append(j)
            dist[i][j] = 1

def WarshallFloyd(d, N):
    
    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 = WarshallFloyd(dist, N)
def dfs(v, c):
    colors[v] = c
    for nv in edge[v]:
        if colors[nv] == c:
            return False
        if colors[nv] == -1:
            if not dfs(nv, c^1):
                return False
    return True

colors = [-1]*N
if not dfs(0,0):
    print(-1)
    exit()

ans = 0
for e in d:
    ans = max(ans, max(e))
print(ans+1)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

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

ans = 0
import queue
for i in range(N):
    q = queue.Queue()
    q.put(i)
    nums = [-1]*N
    nums[i] = 1
    while not q.empty():
        v = q.get()
        flag = True
        for nv in edge[v]:
            if nums[nv] == -1:
                nums[nv] = nums[v] + 1
                q.put(nv)
            elif nums[nv]%2 != (nums[v]+1)%2:
                flag = False
                break
        if not flag:
            break
    if flag:
        ans = max(ans, max(nums))
print(ans) if ans != 0 else print(-1)

Solution (Python):
n = int(input())

g = [[] * n for i in range(n)]

for i in range(n):
  s = input()
  for j,si in enumerate(s):
    if si == '1':
      g[i].append(j)
      
from collections import deque

def bfs(s):
  que = deque()
  que.append((s,1))
  a[0].append(s)
  chk = [False]*n
  chk[s] =True
  cnt = 1
  while que:
      now,p = que.popleft()
      if cnt == n:
        break
      for i in g[now]:
          if not chk[i]:
            a[p].append(i)
            chk[i] = True
            cnt += 1
            que.append((i,p+1))
          
ans = -1
for i in range(n):
  a = [[] for i in range(n+1)]
  bfs(i)
  cc = 0
  b = False
  
  for j in a:
    if j == []:
      ans = max(ans,cc)
      break
    cc += 1
    for k in j:
      
      if set(g[k]) & set(j) != set():
        b = True
        break
    if b:
      break
  
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

g=[[]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j]=="1":
            g[i].append(j)


ans=-float('inf')
for i in range(n):
    itta=[0]*n
    d=deque([i])
    cnt=0
    while d:
        
        cnt+=1
        for i in range(len(d)):
            tmp=d.popleft()
            if itta[tmp]==0:
                itta[tmp]=cnt
                for j in range(len(g[tmp])):
                    if itta[g[tmp][j]]==0:
                        d.append(g[tmp][j])
            elif itta[tmp]==cnt:
                continue
            else:
                cnt=-float('inf')
    ans=max(ans,cnt)
if ans==-float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
N = int(input())
S = [list(map(int, list(input()))) for i in range(N)]


color = [-1] * N
def dfs(node, par):
  global color
  res = True
  for i, s in enumerate(S[node]):
    if s and i != par:
      if color[i] == -1:
        color[i] = (color[node] + 1) % 2
        res *= dfs(i, node)
      else:
        res *= (color[i] == (color[node] + 1) % 2)
  return res

color[0] = 0
if dfs(0, -1):
  from scipy.sparse.csgraph import floyd_warshall
  import numpy as np
  dist = floyd_warshall(S).astype(int)
  print(dist.max() + 1)
else:
  print(-1)

Solution (Python):
N = int(input())
S = [list(map(int, list(input()))) for i in range(N)]


node_to_idx = {}
visited = [False] * N
def dfs(node, par, n):
  global node_to_idx
  res = True
  for i, s in enumerate(S[node]):
    if s and i != par:
      if i in node_to_idx:
        idx = node_to_idx[i]
        if (n - idx) % 2:
          res *= False
        else:
          res *= True
      else:
        if visited[i]:
          continue
        visited[i] = True
        node_to_idx[i] = n
        res *= dfs(i, node, n+1)
  return res

node_to_idx[0] = 0
visited[0] = True
res = dfs(0, -1, 1)
if res:
  from scipy.sparse.csgraph import floyd_warshall
  import numpy as np
  dist = floyd_warshall(S).astype(int)
  print(dist.max() + 1)
else:
  print(-1)

Solution (Python):
from collections import deque
from heapq import heappop, heappush

INF = float("inf")


def bfs():
  stack = deque()
  stack.append((0, 1)) 
  colors[0] = 1
  while stack:
    v, c = stack.popleft()
    for i in edges[v]:
      if colors[i] == c:
        return False
      if colors[i] == 0:
        stack.append((i, -c))
        colors[i] = -c
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] 
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

n = int(input())
S = [input() for _ in range(n)]

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
  

colors = [0] * n

if bfs() == True:
  import numpy as np
  from scipy.sparse.csgraph import shortest_path
  from scipy.sparse.csgraph import floyd_warshall
  from scipy.sparse.csgraph import csgraph_from_dense

  li = [list(map(int, s)) for s in S]
  nli = np.array(li)
  nnli = np.where(nli == 0, 10**12, nli)

  G = csgraph_from_dense(nnli, null_value=10**12)
  d = floyd_warshall(G)
  
  ans = 0
  for i in range(n):
    for j in range(n):
      if ans < d[i][j]:
        ans = d[i][j]
      
  print(int(ans) + 1)
else:
  print(-1)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    S = [[int(x) for x in sys.stdin.readline().rstrip()] for _ in range(N)]

    max_k = 0

    for i in range(N):
        node = [-1] * N
        q = collections.deque()
        q.append((i,1))
        node[i] = 1
        f = True
        while q:
            v,d = q.popleft()
            for j in range(N):
                if S[v][j] == 0: continue
                if node[j] == d+1 or node[j] == d-1: continue
                if node[j] < 0:
                    node[j] = d+1
                    q.append((j,d+1))
                else:
                    f = False
                    break
            else:
                continue
            break
        if f: max_k = max(max_k,max(node))
    if max_k == 0:
        print(-1)
    else:
        print(max_k)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque

n = int(input())
links = [[] for _ in range(n+1)]
for i in range(1,n+1):
    ss = input()
    for j,s in enumerate(ss,1):
        if(s=='1'):
            links[i].append(j)

ans = -1
for i in range(1,n+1):
    ng_flag = False

    depth = [-1] * (n+1)
    depth[i] = 1
    max_depth = 1
    d = deque()
    d.append(i)
    while(d):
        now = d.popleft()
        for j in links[now]:
            if(depth[j] == -1):
                depth[j] = depth[now] + 1
                d.append(j)
                max_depth = max(max_depth, depth[j])
            else:
                if(abs(depth[j] - depth[now]) != 1):
                    ng_flag = True
                    break
        if(ng_flag):
            break
    if(not ng_flag):
        ans = max(ans, max_depth)

print(ans)

Solution (Python):
from collections import deque
n = int(input())
mat=[[10**18 for i in range(n+1)] for j in range(n+1)]
ab = [[] for i in range(n)]

for i in range(n):
    si = input()
    for j in range(n):
        if int(si[j]) == 1:
            
            mat[i+1][j+1] = 1
            ab[i].append(j)

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


def dfs(v,color):
    
    colors[v] = color
    
    for to in ab[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 not is_bipartite():
    print(-1)
    exit()



for i in range(n+1):
	mat[i][i]=0

for i in range(1,n+1):
	for x in range(1,n+1):
		for y in range(1,n+1):
			mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])

ans = 0

for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans = max(ans,mat[i][j])
        
print(ans+1)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
S = [list(map(int, readline().strip())) for _ in range(N)]

ans = -1
for st in range(N):
    level = [None]*N
    level[st] = 0
    used = set([st])
    stack = [st]
    flag = True
    while len(used) < N:
        stack2 = []
        for vn in stack:
            used.add(vn)
            for vf in range(N):
                if S[vn][vf]:
                    if level[vf] is None:
                        level[vf] = level[vn]+1
                        stack2.append(vf)
                    elif level[vf] == level[vn]-1 or level[vf] == level[vn]+1:
                        continue
                    else:
                        flag = False
        stack = stack2[:]
    if flag:
        ans = max(ans, max(level)+1)
print(ans)

Solution (Python):

from collections import deque


N = int(input())
S = [input() for _ in range(N)]
es = [[] for _ in range(N)]

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")

def bfs(node):
    dist = [INF] * N
    dist[node] = 0
    union = [[] for _ in range(N+1)]
    union[0].append(node)
    q = deque()
    q.append(node)
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[curr] + 1 < dist[nxt]:
                dist[nxt] = dist[curr] + 1
                union[dist[nxt]].append(nxt)
                q.append(nxt)

    d = max(dist)
    max_idx = dist.index(d)
    return max_idx, dist, union

s, dist, union = bfs(0)

for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                
                if S[i][j] == "1":
 
                    print(-1)
                    exit()
ans = 0
for i in range(N):
    _, dist, _ = bfs(i)
    ans = max(ans, max(dist)+1)

print(ans)

Solution (Python):
"""
問題の理解が困難
ノードi,jを結ぶ辺があるとき、ノードiは集合aに、ノードjは集合k+1（あるいは逆）に含まれるようにノードを集合に分ける。
その条件を満たす最大の集合の数を求める

1->2
2->3
2->4
みたいなのがあるときに、
・1と2は別の集合（1を集合１、２を集合とする）
・２と３は別の集合（２が集合２なので、３は集合１か３。できるだけ集合の数を多くとりたいので、３とする）
・２と４は別の集合（２が集合２なので、４は集合１か３。上に同じく３とする）
みたいな感じか。
なので、
あるノードから等距離にあるノードを同じ集合にする
という戦略をとれば、集合の数を最大化できる。
で、同じ集合に属するやつらの間に辺がある場合、辺を挟んだノードは別の集合にならなければならないので矛盾するからNG

↑から、木の直径＋１が最大の集合数になるので、double sweepだったか？何かでもとめればよいか？
"""



import heapq
from collections import deque



N = int(input())
S = [input() for _ in range(N)]
es = [[] for _ in range(N)]

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                
                if S[i][j] == "1":

                    print(-1)
                    exit()

ans = 0
for i in range(N):
    q = deque()
    q.append(i)
    dist = [0] * N
    
    dist[i] = 1
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[nxt] == 0:
                dist[nxt] = dist[curr] + 1
                q.append(nxt)
 
    ans = max(ans, max(dist))

print(ans)

Solution (Python):
N=int(input())
g=[[] for i in range(N)] 
cnt=0
for i in range(N):
  s=input()
  for j in range(N):
    if s[j]=='1':
      g[i].append(j)
      cnt+=1
w=cnt//2

color=[0]*N 

def f(v,c):
    
    color[v] = c
    for i in range(len(g[v])):
        if color[g[v][i]]==c:
            return False
        elif color[g[v][i]]==0 and not f(g[v][i],-c):
            
            return False
    return True

def warshall(d,n):
  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

k=1
for i in range(N):
  if color[i]==0:
    if not f(i,1):
      k=-1

if k==-1:
  print(-1)
else:
  d=[[float('inf')]*N for i in range(N)]
  for i in range(N):
    for j in g[i]:
      d[i][j]=1
  for i in range(N):
    d[i][i]=0
  A=warshall(d,N)
  ans=0
  for i in range(N):
    for j in range(N):
      ans=max(ans,d[i][j])
  print(ans+1)

Solution (Python):
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))


    from collections import defaultdict
    from queue import deque

    n = int(input())
    ns = defaultdict(set)
    for u in range(n):
        for v,b in enumerate(map(int, input())):
            if b:
                ns[u].add(v)
                ns[v].add(u)

    best = -1
    for start in range(n):
        q = deque([])
        seen = [False] * n
        vals = [-1] * n
        seen[start] = True
        vals[start] = 0
        v = 0
        q.appendleft((start, v))
        while q:
            u, val = q.pop()
            for v in ns[u]:
                if not seen[v]:
                    q.appendleft((v, val+1))
                    seen[v] = True
                    vals[v] = val + 1
                elif vals[v]==val:
                    print(-1)
                    return
        best = max(best, val+1)
    print(best)
main()

Solution (Python):



N = int(input())
E = [[] for i in range(N)]
G = [None] * N
INF = 10 ** 9
for i in range(N):
  edges = input()
  G[i] = list(map(int,list(edges)))
  G[i] = list(map(lambda x:INF if x == 0 else x,G[i]))
  for j in range(len(edges)):
    if edges[j] == "1":
      E[i].append(j)

color = [-1 for i in range(N)]
from collections import deque
q = deque([])

q.append([0,0])

while q:
  v,bit = q.popleft()
  if color[v] != -1:
    
    if color[v] == bit: 
      continue
    else: 
      print(-1)
      exit(0)
  
  color[v] = bit
  children = E[v]
  for child in children:
    q.append([child,bit^1])




import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense

G = csgraph_from_dense(G, null_value=10**9)
d = floyd_warshall(G)

ans = 0
for i in range(N):
  for j in range(N):
    if ans < d[i][j]:
      ans = d[i][j]
      
print(int(ans) + 1)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    dist = []
    for i in range(N):
        route = [int(i) for i in input()]
        for j in range(N):
            if route[j]:
                G[i].append(j)
            elif i != j:
                route[j] = INF
        dist.append(route)
    
    color = [-1]*N
    color[0] = 0
    stack = [0]
    possible = True
    while stack:
        p = stack.pop()
        for e in G[p]:
            if color[e] >= 0:
                if color[e] == color[p]:
                    possible = False
            else:
                color[e] = color[p]^1
                stack.append(e)
        if not possible:
            break
    
    if possible:
        csr = csr_matrix(dist)
        minimum_route = floyd_warshall(csr).astype(int)
        ans = minimum_route.max()
        print(ans + 1)
    else:
        print(-1)

if __name__ == '__main__':
    main()