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
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *

from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    graph = [set() for _ in range(N)]
    for i in range(N):
        S = input().rstrip()
        for j in range(N):
            if S[j] == '1':
                graph[i].add(j)
    
    
    ans = -1
    for i in range(N):
        visited = {i}
        cur_points = {i}
        tmp = 1
        
        while len(visited) < N:
            next_points = set()
            
            for point in cur_points:
                next_points |= graph[point]
            next_points -= cur_points
            
            link_checker = False
            for point in next_points:
                if graph[point] & next_points:
                    link_checker = True
                    break
            
            if link_checker:
                break
            
            visited |= next_points
            cur_points = next_points
            tmp += 1
        else:
            ans = max(ans,tmp)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
S = [list(map(int,input())) for i in range(n)]
Graph = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j]==1:
            Graph[i]+=[j]
colors = [0 for i in range(n)]

def is_bipartite(es):
    stack = [(0,1)]
    while stack:
        v,color = stack.pop()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.append((to, -color))
    return True

if not is_bipartite(Graph):
    print(-1)
    exit()

S2 = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j]==1:
            S2[i][j]=1
        elif i==j:
            S2[i][j]=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

warshall_floyd(S2)

diam = 0
for i in range(n):
    for j in range(n):
        diam = max(diam,S2[i][j])
print(diam+1)

Solution (Python):
from collections import deque
N = int(input())
S = [list(map(int, input().strip())) for _ in range(N)]
G = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j] == 1:
            G[i].append(j)


def is_bibarate(G):
    vst = [False] * N
    que = deque([0])
    color = [0] * N
    color[0] = 1
    while len(que):
        p = que.popleft()
        for q in list(G[p]):
            if color[q] == 0:
                color[q] = - color[p]
                que.append(q)
            elif color[q] == color[p]:
                return False
            
    return True
                

        

d = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            d[i][j] = 0
        elif S[i][j] == 1:
            d[i][j] = 1
            
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])

wf_ans = max([max(r) for r in d]) + 1

if is_bibarate(G):
    print(wf_ans)
else:
    print(-1)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
S = []
for i in range(N):
    s = list(input().strip())
    s_list = [int(k) for k in s]
    S.append(s_list)

count_max = 0
for i in range(N):
    flag = [-1]*N
    q = deque([i])
    flag[i] = 0
    count = 0
    while(q):
        count += 1
        for k in range(len(q)):
            v = q.popleft()
            for j in range(len(S[v])):
                if S[v][j] == 1 and flag[j] == -1:
                    flag[j] = count
                    q.append(j)
                elif S[v][j] == 1:
                    if flag[j]%2 != count%2:
                        print(-1)
                        sys.exit()
    count_max = max(count, count_max)
print(count_max)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int( input())
    S = [ list( map( int, list( input())[:-1])) for _ in range(N)]
    E = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == 1:
                E[i].append(j)
    
    d = deque([0])
    V = [-1]*N
    V[0] = 1
    
    while d:
        v = d.pop()
        now = V[v]
        for w in E[v]:
            if V[w] == -1:
                V[w] = now+1
                d.append(w)
                continue

            if (now + V[w])%2 == 1:
                continue
            print(-1)
            return
    ans = 2

    for i in range(N):
        d = deque([i])
        V = [-1]*N
        V[i] = 1
        check = True
        while d:
            v = d.popleft()
            now = V[v]
            for w in E[v]:
                if V[w] == -1:
                    V[w] = now+1
                    d.append(w)
                    continue
                if now+1 == V[w] or now-1 == V[w]:
                    continue
                check = False
                break
            if not check:
                break
        if not check:
            continue
        if max(V) > ans:
            ans = max(V)
    print(ans)
    
            
                
if __name__ == '__main__':
    main()

Solution (Python):




class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.edges = []
    self.depth = -1

  def __str__(self):
    return '{}: -> {}'.format(self.idx, ','.join(str(e.idx) for e in self.edges))


def search(nodes):
  new_nodes = set()

  for node in nodes:
    for edge in node.edges:
      if edge.depth == -1:
        edge.depth = node.depth + 1
        new_nodes.add(edge)
      elif abs(edge.depth - node.depth) != 1:
        return False

  if len(new_nodes) == 0:
    return True

  return search(new_nodes)


def main():
  nodes = [Node(i) for i in range(int(input()))]
  value = 0

  for i in range(len(nodes)):
    for j, v in enumerate(map(int, input().strip())):
      if v == 1:
        nodes[i].edges.append(nodes[j])

  for i in range(len(nodes)):
    for node in nodes:
      node.depth = -1

    start = nodes[i]
    start.depth = 1

    if not search([start]):
      print(-1)
      return

    for node in nodes:
      value = max(node.depth, value)

  print(value)


if __name__ == '__main__':
  main()

Solution (Python):

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
n = int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
l=[]

for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            d[i][j] = 1
            l.append([i,j])
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
visited = [1]+[0 for i in range(n-1)]
for _ in range(1000):
    for i in l:
        if visited[i[0]]!=0:
            if visited[i[0]]==1:
                if visited[i[1]]==1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=-1
            else:
                if visited[i[1]]==-1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=1
ans=0
for i in wf:
    ans=max(ans,max(i)+1)
print(ans)

Solution (Python):
n = int(input())
s = []
for i in range(n):
    line = list(map(int, list(input())))
    s.append(line)

ans = -1


def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

for k in range(n):
    unsearched_nodes = list(range(n)) 
    distance = [300] * n 
    previous_nodes = [-1] * n 
    distance[k] = 0 

    while(len(unsearched_nodes) != 0): 
        
        posible_min_distance = 300 
        for node_index in unsearched_nodes: 
            if posible_min_distance > distance[node_index]: 
                posible_min_distance = distance[node_index] 
        target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) 
        unsearched_nodes.remove(target_min_index) 

        target_edge = s[target_min_index] 
        for index, route_dis in enumerate(target_edge):
            if route_dis != 0:
                if distance[index] > (distance[ target_min_index] + route_dis):
                    distance[index] = distance[ target_min_index] + route_dis 
                    previous_nodes[index] =  target_min_index 

    marubatu = 1
    for i in range(n-1):
        if marubatu == 0:
            break
        for j in range(i+1, n):
            if distance[i] == distance[j] and s[i][j] == 1:
                marubatu = 0
                break
    if marubatu == 1:
        ans = max(ans, len(list(set(distance))))

print(ans)

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

adj_dict={i:[] for i in range(N)}

for i in range(N):
  for j in range(i,N):
    if S[i][j]:
      adj_dict[i].append(j)
      adj_dict[j].append(i)

ans = 0
for i in range(N):
  
  l=0
  visited = set([i])
  prev_layer = set()
  cur_layer = set([i])
  next_layer = set()
  
  
  while len(visited)<N:
    l+=1
    for v in cur_layer:
      visited.add(v)
      for u in adj_dict[v]:
        if u in cur_layer:
          print(-1)
          exit()
        next_layer.add(u)
    prev_layer = cur_layer
    cur_layer = next_layer
    next_layer = set()
  ans = max(ans,l)
  
print(ans)

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

from collections import deque
from collections import defaultdict

g = defaultdict(set)

for i in range(N):
    for j in range(N):
        if s[i][j] == 1:
            g[i+1].add(j+1)
            g[j+1].add(i+1)

ans = -1
for i in range(N):
    q = []
    q.append(i+1)
    visit = [-1]*(N+1)
    visit[i+1] = 1
    temp = 0
    while q:
        nextq = []
        for now in q:
            for next in g[now]:
                if visit[next] == -1:
                    visit[next] = visit[now] + 1
                    nextq.append(next)
                else:
                    if abs(visit[next] - visit[now]) == 1:
                        continue
                    else:
                        temp = -1
        if temp == -1:
            break
        q = nextq[:]
    if temp != -1:
        ans = max(max(visit), ans)
print(ans)

Solution (Python):
from collections import deque
n = int(input())
s = [input() for i in range(n)]
ans = -2
for k in range(n):
    q = deque([k])
    d = [float('inf')] * n
    d[k] = 0
    while q:
        flg = 0
        p = q.popleft()
        for i, c in enumerate(s[p]):
            if c == '1':
                if d[i] == float('inf'):
                    d[i] = d[p] + 1
                    q.append(i)
                elif d[i] != d[p] + 1 and d[i] != d[p] - 1:
                    flg = 1
                    break
        if flg:
            break
    if flg:
        continue
    for i in range(n):
        ans = max(ans, d[i])
print(ans + 1)

Solution (Python):



def f(N, S, st):
    R = [0]*(N)

    Q = set([st])
    R[st] = 1
    idx = 1
    cnt = 0

    while(len(Q) > 0):
        Q2 = set()
        cnt += 1
        idx += 1
        
        for i in Q:
            for j, s in enumerate(S[i]):
                if s == '1':
                    if R[j] == idx - 1:
                        return -1
                    elif R[j] == 0:
                        R[j] = idx
                        Q2.add(j)
                    
        Q = Q2
        
    return cnt
        


def g(N, S):
    m = 0

    for i in range(N):
        k = f(N, S, i)
        if k == -1:
            return -1

        m = max(m, k)

    return m



def main():
    N = int(input())
    S = list(input() for _ in range(N))

    print(g(N, S))





if __name__ == '__main__':
    main()

Solution (Python):

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

M = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j] == "1":
            M[i].append(j)
ans = -1
owa = 0
for i in range(n):
    a0 = -1
    Q = [[i, 0]]
    st = 0
    D = [-1] * n
    while st < len(Q):
        a = Q[st][0]
        d = Q[st][1]
        D[a] = d
        for x in M[a]:
            if D[x] == -1:
                Q.append([x, d+1])
                D[x] = d+1
            elif D[x] != d-1 and D[x] != d+1:
                owa = 1
                break
        if owa == 1:
            break
        st += 1
    if owa == 0:
        a0 = max(D)+1
    ans = max(ans, a0)

print(ans)

Solution (Python):
n = int(input())
G = []
for i in range(n):
    a = []
    for j, c in enumerate(map(int, input())):
        if c == 1:
            a.append(j)
    G.append(a)

from collections import deque

def bfs(i):
    used = [-1]*n
    used[i] = 0
    que = deque()
    que.append(i)
    depth = 0
    while que:
        nxt = deque()
        while que:
            a = que.pop()
            for to in G[a]:
                if used[to] >= 0 and (used[to] != depth-1 and used[to] != depth+1):
                    return 0
                if used[to] < 0 :
                    nxt.append(to)
                    used[to] = depth+1
        que = nxt
        depth += 1
    for i in used:
        if i < 0:
            return 0
    return depth

ans = max(bfs(i) for i in range(n))
if ans == 0:
    ans = -1
print(ans)

Solution (Python):
n=int(input())
inf=float("inf")
table=[[inf]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][k]!=inf and d[k][j]!=inf:
          d[i][j]=min(d[i][j],d[i][k]+d[k][j])
          if d[i][j]<float("inf") and d[i][j]%2!=(d[i][k]+d[k][j])%2:
            return False
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)

Solution (Python):
from collections import deque

N = int(input())

S = []



for i in range(N):

    s = input()
    S.append(s)


"""
lis = [float("inf")] * N
lis[0] = 0
q = deque([])

q.append(0)



while len(q) > 0:

    now = q.pop()

    for i in range(N):

        
        if S[now][i] == "1" and lis[i] > lis[now] + 1:
            lis[i] = lis[now] + 1
            q.append(i)

mind = 0


for i in lis:
    if lis[mind] < lis[i]:
        mind = i

"""
ans = 0

for mind in range(N):


    lis = [float("inf")] * N
    lis[mind] = 0
    q = deque([])
    q.append(mind)

    

    while len(q) > 0:

        now = q.pop()
        
    

        for i in range(N):

            if S[now][i] == "1" and lis[i] > lis[now] + 1:

                lis[i] = lis[now] + 1
                q.append(i)

    ans = max(ans,max(lis))


mind = 0
nlis = [None] * N
nlis[mind] = 0
q = deque([])
q.append(mind)
flag = True

while len(q) > 0:

    now = q.pop()  

    for i in range(N):

        if S[now][i] == "1" and nlis[i] == None:
   
            nlis[i] = nlis[now] ^ 1
            q.append(i)

        elif S[now][i] == "1" and nlis[now] == nlis[i]:
            flag = False
            break

    if not flag:
        break

if flag:
    print (ans + 1)

else:
    print (-1)

Solution (Python):
from collections import deque
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall


def bfs(links):
    color = [-1] * n
    last_v = None
    q = deque([(0, 0)])
    while q:
        v, c = q.popleft()
        if color[v] != -1:
            if color[v] != c:
                return -1
            continue
        else:
            color[v] = c
        last_v = v
        new_c = c ^ 1
        for u in links[v]:
            if color[u] != -1:
                if color[u] != new_c:
                    return -1
                continue
            q.append((u, new_c))
    return last_v


def bfs2(s, links):
    visited = set()
    q = deque([(s, 1)])
    last_d = -1
    while q:
        v, d = q.popleft()
        if v in visited:
            continue
        visited.add(v)
        last_d = d
        for u in links[v]:
            if u in visited:
                continue
            q.append((u, d + 1))
    return last_d


def solve(n, links, matrix):
    res = bfs(links)
    if res == -1:
        return -1
    
    g = csgraph_from_dense(matrix)
    f = floyd_warshall(g)
    return int(f.max()) + 1


n = int(input())
links = [set() for _ in range(n)]
matrix = []
for i in range(n):
    s = input().strip()
    for j, c in enumerate(s):
        if c == '0':
            continue
        links[i].add(j)
    matrix.append(list(map(int, s)))

print(solve(n, links, matrix))

Solution (Python):
from collections import deque


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


graph = [[] for i in range(n)]

for i in range(n):
    for j in range(i+1, n):
        if s[i][j] == "1":
            graph[i].append(j)
            graph[j].append(i)

q = ([0])
visited = [-1]*n
visited[0] = 0
is_2graph = True
while q:
    pos = q.pop()
    for next_pos in graph[pos]:
        if visited[next_pos] == -1:
            visited[next_pos] = visited[pos] ^ 1
            q.append(next_pos)
        else:
            if visited[pos]^1 != visited[next_pos]:
                is_2graph = False
if not is_2graph:
    print(-1)
    exit()


INF = 10**9
dp = [[INF]*n for i in range(n)]
for i in range(n):
    dp[i][i] = 0

for i in range(n):
    for j in range(n):
        if s[i][j] == "1":
            dp[i][j] = 1
            dp[j][i] = 1

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

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

Solution (Python):
n = int(input())
raw = []
for i in range(n):
  tmp = input()
  now = []
  for j in range(n):
    if tmp[j] == '1':
      now.append(j)
  raw.append(now)

ans = []
for st in range(n):
  gr = [-1 for _ in range(n)]
  gr[st] = 1
  time = 1
  now = {st}
  while now:
    time += 1
    last = now
    now = set()
    
    for x in last:
      for y in raw[x]:
        if gr[y] == time-2:
          pass
        elif gr[y] == time:
          pass
        elif gr[y] == -1:
          gr[y] = time
          now.add(y)
        else:
          print(-1)
          
          break
      else:
        continue
      break
    else:
      continue
    break
  else:
    
    ans.append(time-1)
    continue
  break
else:
  print(max(ans))

Solution (Python):

import sys
sys.setrecursionlimit(10**6)


def dfs(s):
    for t in g[s]:
        if dist[t] > -1:
            if (dist[s] + 1 - dist[t]) % 2 == 1:
                print(-1)
                exit()
            continue
        dist[t] = dist[s] + 1
        dfs(t)


n = int(input())
s = [list(input()) for _ in range(n)]
g = [[] for _ in range(n)]
mat = [[10**9] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
    for j in range(i + 1, n):
        if s[i][j] == '1':
            g[i].append(j)
            g[j].append(i)
            mat[i][j] = mat[j][i] = 1
dist = [-1] * n
dist[0] = 0
dfs(0)

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

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
G=[[] for i in range(n)]
for i in range(n):
    s=input().rstrip()
    for j in range(i,n):
        if s[j]=='1':
            G[i].append(j)
            G[j].append(i)
Ans=-1
for i in range(n):
    ans=1
    que=[i]
    cs=set(que)
    check=[False]*n
    check[i]=True
    nex=[]
    M=False
    while True:
        while len(que)>0:
            now=que.pop()
            for j in G[now]:
                if j in cs:
                    M=True
                elif check[j]:
                    pass
                else:
                    check[j]=True
                    nex.append(j)
        que=nex
        if que==[]:
            break
        cs=set(que)
        nex=[]
        ans+=1
    if M:
        ans=-1
    Ans=max(ans,Ans)
print(Ans)

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

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

es = [[] for i in range(N)]
for i,row in enumerate(S):
    for j,c in enumerate(row):
        if c=='1':
            es[i].append(j)
            es[j].append(i)


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 not is_bipartite():
    print(-1)
    exit()

INF = float('inf')
dists = [[1 if c=='1' else INF for c in row] for row in S]
for i in range(N):
    dists[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

print(max(max(row) for row in dists) + 1)

Solution (Python):
from collections import deque
N = int(input())
S = list(input() for i in range(N))
ans = -1
for i in range(N):
    queue = deque([i])
    V = [0]*N
    V[i] = 1
    while queue:
        q = queue.popleft()
        m = V[q]
        for i in range(N):
            if S[q][i] == "1":
                if V[i] == 0:
                    V[i] = m+1
                    queue.append(i)
                elif abs(V[i]-m) != 1:
                    print(-1)
                    exit()
    ans = max(max(V),ans)
print(ans)

Solution (Python):
from collections import deque


def search(N, adj, start):
    dist = [-1] * N
    q = deque()
    q.append((start, 0, -1))
    while len(q):
        p, d, prev = q.popleft()
        if dist[p] != -1:
            if dist[p] != d:
                return None
            continue
        dist[p] = d
        for nxt in adj[p]:
            if nxt == prev:
                continue
            if dist[nxt] == -1:
                q.append((nxt, d+1, prev))
    return dist


def main():
    N = int(input())
    S = [input() for _ in range(N)]
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                adj[i].add(j)
    start = 0
    dist = search(N, adj, 0)
    if dist == None:
        print(-1)
        return
    ans = 0
    for i in range(N):
        tmp = max(search(N, adj, i)) + 1
        ans = max(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
import queue

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.judge = "Yes"
		self.g = graph.graph
		self.Q = queue.Queue()
		self.dist = [INF] * N
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.dist[s] = 0
		self.Q.put(s)
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"
				else:
					if (self.dist[i] - self.dist[v]) % 2 == 0:
						self.judge = "No"

	def ans(self):
		return max(self.dist)


def main():
	
	N = int(input())
	L = []
	for i in range(N):
		S = list(input())
		L.append(S)
	G = Graph()
	for i in range(N):
		for j in range(i + 1, N):
			if L[i][j] == "1":
				G.add_edge(i, j)
				G.add_edge(j, i)
	
	jud = "Yes"
	A = - INF
	for i in range(N):
		bfs = BFS(G, i, N)
		A = max(bfs.ans(), A)
		if bfs.judge == "No":
			jud = "No"
	if jud == "No":
		print(-1)
	else:
		print(A + 1)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

N=int(input())
S=[input().strip() for i in range(N)]

E=[[] for i in range(N)]

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

USE=[-1]*N

Q=deque()
Q.append(0)
USE[0]=0


while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[x]==USE[to]:
            print(-1)
            sys.exit()
            
        elif USE[to]==-1:
            USE[to]=1-USE[x]
            Q.append(to)

for i in range(N):
    for j in range(N):
        if S[i][j]=="1" and USE[i]==USE[j]:
            print(-1)
            sys.exit()

ANS=0
for i in range(N):
    Q=deque()
    Q.append(i)
    USE=[0]*N
    USE[i]=1
    H=[0]*N

    while Q:
        NQ=deque()
        while Q:
            
            x=Q.pop()

            for to in E[x]:
                if USE[to]==0:
                    H[to]=H[x]+1
                    USE[to]=1
                    NQ.append(to)

        Q=NQ

    ANS=max(ANS,max(H)+1)

print(ANS)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    E = []
    G = defaultdict(list)
    for i, s in enumerate(S):
        for j, c in enumerate(s[:]):
            if i < j and c == '1':
                E.append((i, j))
                G[i].append(j)
                G[j].append(i)
    
    def f(s):
        e = set(E)
        vs = [set([s])]
        while e:
            vs1 = set()
            for i in vs[-1]:
                for j in G[i]:
                    vs1.add(j)
                    if i > j:
                        u, v = j, i
                    else:
                        u, v = i, j
                    if (u, v) in e:
                        e.remove((u, v))
            vs.append(vs1)
            for i in vs[-1]:
                for j in G[i]:
                    if j in vs[-1]:
                        return -1

        return len(vs)

    ans = -1
    for i in range(N):
        ans = max(ans, f(i))
    return ans


def main():
    N = read_int()
    S = [read_str() for _ in range(N)]
    print(slv(N, S))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque

def main():
    def solve(i):
        C=[0]*n
        C[i]=1
        q=deque()
        q.append(i)
        while q:
            v=q.popleft()
            for to in Edges[v]:
                if C[to]==0:
                    q.append(to)
                    C[to]=C[v]+1
                else:
                    if C[to]!=C[v]+1 and C[to]!=C[v]-1:
                        return -1
        return max(C)
    n=int(input())
    S=[input().strip() for _ in range(n)]
    Edges=[[] for _ in range(n)]
    for i,s in enumerate(S):
        for j in range(n):
            if s[j]=='1':
                Edges[i].append(j)
    ans=-1
    for i in range(n):
        
        ans=max(ans,solve(i))
    return ans

if __name__=='__main__':
    print(main())

Solution (Python):
from collections import deque
import sys
readline = sys.stdin.readline

N = int(readline())
Edge = [[] for _ in range(N)]
for i in range(N):
    S = readline().strip()
    for j in range(N):
        if S[j] == '1':
            Edge[i].append(j)

def check(Edge):
    s = 0
    Q = deque([s])
    N = len(Edge)
    col = [None]*N
    col[s] = 0
    while Q:
        vn = Q.pop()
        for vf in Edge[vn]:
            if col[vn] == col[vf]:
                return False
            if col[vf] is None:
                col[vf] = 1 - col[vn]
                Q.appendleft(vf)
    
    return True

def bfs(s, Edge):
    N = len(Edge)
    Q = deque([s])
    inf = 10**9+7
    dist = [inf]*N
    dist[s] = 0
    used = set([s])
    while Q:
        vn = Q.pop()
        for vf in Edge[vn]:
            if vf in used:
                continue
            used.add(vf)
            dist[vf] = min(dist[vn]+1, dist[vf])
            Q.appendleft(vf)
    
    return dist

if not check(Edge):
    print(-1)
else:
    ans = 0
    for i in range(N):
        ans = max(ans, max(bfs(i, Edge)))
    print(ans+1)