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())
route = [[] for i in range(n)]
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == "1":
            route[i].append(j)
            route[j].append(i)
ans = -1
for p in range(n):
    visit = [-1 for i in range(n)]
    visit[p] = 1
    d = deque()
    d.append(p)
    while d:
        now = d.popleft()
        for i in route[now]:
            if visit[i] == -1:
                visit[i] = visit[now] + 1
                d.append(i)
            elif abs(visit[i] - visit[now]) != 1:
                print(-1)
                exit()
    ans = max(ans,max(visit))
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d
  


N = I()
data = SLs(N)
graph = [[] for i in range(N)]
U = UnionFind(N*2)
W = WarshallFloyd(N)
for i in range(N):
  for j in range(N):
    if data[i][j] == "1":
      graph[i].append(j)
      U.union(i,j+N)
      U.union(i+N,j)
      W.add(i,j,1)
for i in range(N):
  if U.same(i, i+N):
    print(-1)
    exit()
_,d = W.WarshallFloyd_search()
print(max(max(i) for i in d)+1)

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    sl = []
    for i in range(n):
        si = input()
        si = [1 if i == "1" else 100000 for i in si]
        sl.append(si)

    cm = csr_matrix(sl)
    d = dijkstra(cm,directed=False)
    ma = 0
    for i in range(n):
        for j in range(n):
            if d[i][j] > ma:
                ma = d[i][j]
            if sl[i][j] == 1 and (d[i][0]%2+d[j][0]%2)%2 == 0:
                print(-1)
                exit()
    print(int(ma)+1)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


N = int(input())
Map = [[] for _ in range(N)]
for i in range(N):
    S = list(input())[:-1]
    for j in range(N):
        s = S[j]
        if s == "1":
            Map[i].append(j)
error = 0
MAX = 0
for i in range(N):
    E = 0
    flag = 1
    vmax = 0
    depth = [-1]*N
    depth[i] = 1
    q = deque([i])
    while len(q) != 0:
        cur = q.popleft()
        for chi in Map[cur]:
            if depth[chi] == -1:
                depth[chi] = depth[cur]+1
                vmax = max(vmax,depth[cur]+1)
                q.append(chi)
            else:
                if depth[chi] != depth[cur]:
                    continue
                else:
                    E = 1
                    break
    if E == 0:
        MAX = max(vmax,MAX)
    else:
        error += 1
if error == N:
    print(-1)
else:
    print(MAX)

Solution (Python):



INF = 10 ** 8
N = int(input())
S = []
for _ in range(N):
    S.append(list(map(int, list(input()))))



color = [0] * N
def dfs(x, c):
    color[x] = c
    for i in range(N):
        
        if S[x][i] == 1 and color[i] == c:
            return False
        
        if S[x][i] == 1 and color[i] == 0 and not dfs(i, -c):
            return False
    
    return True

for i in range(N):
    if color[i] == 0 and not dfs(i, 1):
        print(-1)
        exit()


d = [[INF if S[i][j] == 0 else S[i][j] for i in range(N)] for j in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            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] != INF:
            ans = max(ans, d[i][j] + 1)
print(ans)

Solution (Python):
import sys






def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



from collections import deque

def main():
	n=II()
	G=[]
	for i in range(n):
		G.append(list(map(int,input())))
		

	ans=0
	for i in range(n):
		v=[-2]*n
		v[i]=0
		q=deque()
		q.append([i,0])

		while q:
			now,d=q.popleft()
			for j in range(n):
				if G[now][j]==1:
					if v[j]==-2:
						v[j]=d+1
						q.append([j,d+1])
					elif v[j]==d-1 or v[j]==d+1:
						continue
					else:
						print(-1)
						exit(0)
		ans=max(ans,max(v)+1)


	print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
import sys






def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



from collections import deque

def main():
	n=II()
	G=[]
	for i in range(n):
		G.append(list(map(int,input())))
		

	ans=0
	for i in range(n):
		v=[-2]*n
		v[i]=0
		q=deque()
		q.append([i,0])

		while q:
			now,d=q.popleft()
			for j in range(n):
				if G[now][j]==1:
					if v[j]==-2:
						v[j]=d+1
						q.append([j,d+1])
					elif v[j]==d-1 or v[j]==d+1:
						continue
					else:
						print(-1)
						exit(0)
		ans=max(ans,max(v)+1)


	print(ans)

if __name__ == "__main__":
	main()

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

def bfs():
    color = [0]*N
    color[0] = 1
    q = deque([0])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
            else:
                if color[nv]==color[v]:
                    return False
    
    return True
    
def warshall_floyd():
    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])
            
N = int(input())
S = [input()[:-1] for _ in range(N)]
G = [[] for _ in range(N)]

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

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

d = [[10**18]*N for _ in range(N)]

for i in range(N):
    d[i][i] = 0
    
for i in range(N):
    for j in range(i+1, N):
        if S[i][j]=='1':
            d[i][j] = 1
            d[j][i] = 1

warshall_floyd()
ans = 0

for i in range(N):
    for j in range(N):
        ans = max(ans, d[i][j])

print(ans+1)

Solution (Python):
from collections import deque
n = int(input())
edges = [[] for _ in range(n)]

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


flg = True
l, r = set(), set()
l.add(0)
que = deque()
que.append((0, True))
is_left = True
while que and flg:
    cur, is_left = que.popleft()
    for to in edges[cur]:
        if is_left:
            if to in l:
                flg = False
            elif to not in r:
                r.add(to)
                que.append((to, False))
        else:
            if to in r:
                flg = False
            elif to not in l:
                l.add(to)
                que.append((to, True))

    if is_left:
        is_left = False
    else:
        is_left = True


if not flg:
    print(-1)

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

    inf = 1000
    d = [[inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if j in edges[i]:
                d[i][j] = 1

    warshall_floyd(d, n)
    
    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            ans = max(ans, d[i][j]+1)

    print(ans)

Solution (Python):

"""
二部グラフで無いなら分割はできない。
二部グラフの場合、頂点間の最も長い距離＋１
が答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
g = [[float("inf")]*n for i in range(n)]
g2 = [[] for i in range(n)] 
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    for j in range(n):
        if s[j] == "1":
            g[i][j] = 1
            g2[i].append(j)
            g2[j].append(i)
for i in range(n):
    g[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

FW = warshall_floyd(g)

color = [0] * n 

def f(v,c,g):
    
    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,g2):
            
            return False
    return True

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

if k != 1:
    print(-1)
else:
    ans = 0
    for i in FW:
        for j in i:
            if j != float("inf"):
                ans = max(ans,j)
    print(ans+1)

Solution (Python):
import sys

INF = 10 ** 8
N = int(input())
S = []
for _ in range(N):
    S.append(list(map(int,list(input()))))

color = [0] * N

def dfs(x, c):
    color[x] = c
    for i in range(N):
        if S[x][i] and color[i] == c:
            return False
        if S[x][i] and color[i] == 0 and not dfs(i, -c):
            return False
    return True

for i in range(N):
    if color[i] == 0 and not dfs(i, 1):
        print(-1)
        sys.exit()

d = [[INF if S[i][j] == 0 else S[i][j] for i in range(N)] for j in range(N)]

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] != INF:
            ans = max(ans, d[i][j]+1)
print(ans)

Solution (Python):
from collections import deque
N = int(input())

G = {k: [] for k in range(N)}
for i in range(N):
    S = input()
    for j in range(N):
        if S[j] == '1':
            G[i].append(j)
            G[j].append(i)


def bfs(i):
    visited = [-1 for _ in range(N)]
    visited[i] = 1
    M = 1
    que = deque([(i, -1)])

    while que:
        ci, p = que.popleft()

        for ni in G[ci]:
            if ni != p:
                if visited[ni] != -1:
                    if (visited[ci]+1-visited[ni]) % 2 == 1:
                        print(-1)
                        exit()
                else:
                    que.append((ni, ci))
                    visited[ni] = visited[ci]+1
                    M = max(M, visited[ni])

    return M


ans = 0
for i in range(N):   
    ans = max(ans, bfs(i))
print(ans)

Solution (Python):
N=int(input())
S=[list(map(int,list(input()))) for i in range(N)]
VE=[[] for i in range(N)]
for i in range(N):
  for j in range(N):
    if S[i][j]:
      VE[i].append(j)
C=[0]*(N*N+1)
def ni(v,c):
  global S,C,N
  C[v]=c
  for i in range(len(VE[v])):
    if C[VE[v][i]]==c:
      return False
    if C[VE[v][i]]==0 and not(ni(VE[v][i],-c)):
      return False
  return True

if not(ni(0,1)):
  print(-1)
  exit()
INF=10**12
D=[[INF]*N for i in range(N)]
for i in range(N):
  D[i][i]=0
  for j in range(len(VE[i])):
    D[i][VE[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])
P=0
for i in range(N):
  P=max(P,max(D[i]))
print(P+1)

Solution (Python):
from collections import  deque
def is_bin_graph(edges,st):
    """
    :param edges: 辺のdictionary,0-indexedを想定
    :param st: start
    :return:is_bin:二部グラフかどうか
    """
    que = deque()
    v = [0 for i in range(len(edges))]
    que.append([st,0])
    v[st] = 1
    is_bin = True
    while True:
        if len(que) > 0:
            top = que.popleft()
            col = v[top[0]]
            cos = top[1]
            for nex in edges[top[0]]:
                if v[nex] == 0:
                    v[nex] = -col
                    que.append([nex,cos+1])
                else:
                    if v[nex] == col:
                        is_bin = False
                    else:
                        continue
        else:
            break
        if not is_bin:
            break

    return  is_bin

def dfs(edges,st):
    que = deque()
    v = [0 for i in range(len(edges))]
    que.append([st,0])
    v[st] = 1
    max_cos = 0
    while True:
        if len(que) > 0:
            top = que.popleft()
            cos = top[1]
            for nex in edges[top[0]]:
                if v[nex] == 0:
                    v[nex] = 1
                    que.append([nex,cos+1])
                    if cos +1 > max_cos:
                        max_cos = cos+1
        else:
            break

    return max_cos

n = int(input())
edges = {}
for i in range(n):
    edges[i] = []
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == "1":
            edges[i].append(j)
            edges[j].append(i)

if is_bin_graph(edges,0):
    tp = 0
    for i in range(n):
        cos = dfs(edges,i)
        if tp < cos:
            tp = cos
    print(tp+1)
else:
    print(-1)

Solution (Python):
n = int(input())
link = [[] for _ in range(n)]
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            link[i].append(j)

from collections import deque
Q = deque()
Q.append([0,0])
visited=[-1]*n
visited[0]=0 
while Q:
    now,color = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            if visited[nxt] == (color+1)%2:
                continue
            else:
                print(-1)
                exit()
        visited[nxt]=(color+1)%2
        Q.append([nxt,(color+1)%2])

ans=0
for i in range(n):
    Q = deque()
    Q.append([i,0])
    visited=[-1]*n
    visited[i]=1
    while Q:
        now,cnt = Q.popleft()
        for nxt in link[now]:
            if visited[nxt]!=-1:
                continue
            visited[nxt]=cnt+1
            Q.append([nxt,cnt+1])
    mx = max(visited)
    ans=max(ans,mx)

print(ans+1)

Solution (Python):
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def warshall_floyd(n, 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


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

    def bfs(start, S):
        visited = [False] * N
        visited[start] = True
        group = [-1] * N
        group[start] = 0
        q = deque([(start, 0)])
        while q:
            n, g = q.popleft()

            for i in range(N):
                if S[n][i] == "1":
                    if visited[i]:
                        if abs(group[i] - g) != 1:
                            return -1
                        else:
                            continue
                    else:
                        group[i] = g + 1
                        visited[i] = True
                        q.append((i, g + 1))
                else:
                    continue
        n_group = 1
        for i in range(N):
            if group[i] == -1:
                return -1
            if n_group < group[i] + 1:
                n_group = group[i] + 1
        return n_group

    answer = -1
    for i in range(N):
        n_group = bfs(i, S)
        if n_group > answer:
            answer = n_group
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    def bfs(start):
        q = deque([start])
        visited = [-1 for _ in range(N)]
        visited[start] = 0
        prev = [set() for _ in range(N)]
        prev[start].add(-1)

        while q:
            cur = q.popleft()

            for nex in range(N):
                if cur == nex:
                    continue

                if S[cur][nex] == "0":
                    continue

                if nex in prev[cur]:
                    continue

                if visited[nex] == visited[cur] + 1:
                    prev[nex].add(cur)
                    continue

                if visited[nex] > 0:
                    return -1

                visited[nex] = visited[cur] + 1
                prev[nex].add(cur)
                q.append(nex)

        return max(visited) + 1

    
    ans = -1
    for i in range(N):
        tmp = bfs(i)
        if ans < tmp:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

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

def main():
    n = int(input())
    s = [list(input()) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if (i==j):
                s[i][j] = 0
                continue
            if (s[i][j]=="1"):
                s[i][j] = 1
            else:
                s[i][j] = float("inf")
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                s[i][j] = min(s[i][j], s[i][k]+s[k][j])
    
    w = [[] for _ in range(n)]
    m = [s[0][0],0,0]
    for i in range(n):
        for j in range(n):
            if (s[i][j] > m[0]):
                m = [s[i][j],i,j]
    
    for i in range(n):
        w[s[m[1]][i]].append(i)
    
    for i in range(n):
        if (len(w[i])>=2):
            for j in range(len(w[i])-1):
                for k in range(j+1,len(w[i])):
                    if (s[w[i][j]][w[i][k]]==1):
                        print(-1)
                        exit()
    print(m[0]+1)
    

if __name__=="__main__":
    main()

Solution (Python):


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    
    adj=[[]for _ in range(N)]
    
    
    for i in range(N):
        S=list(input())
        for j in range(N):
            if S[j]=="1":
                adj[i].append(j)
            
    import queue
    
    ans=0
    
    
    def bfs(x):
        q=queue.Queue()
        q.put((x,1))
        V=[-1]*N
        V[x]=1
        flag=0
        while not q.empty():
            v,d=q.get()
            for nv in adj[v]:
                if V[nv]==-1:
                    V[nv]=d+1
                    q.put((nv,d+1))
                if abs(V[nv]-V[v])!=1:
                    flag=1
                    break
                
        if flag:
            return -1
        return max(V)
    
    ans=0
    for i in range(N):
        temp=bfs(i)
        if temp==-1:
            ans=-1
            break
        ans=max(ans,temp)
    print(ans)
    
                    

        
        

main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for i in range(n):
    s = list(map(int, list(input().rstrip())))
    for j in range(n):
        if s[j]:
            edges[i].append(j)


def dfs(v, c=0):
    color[v] = c
    for v2 in edges[v]:
        if color[v2] != -1:
            if color[v] == color[v2]:
                global is_ok
                is_ok = 0
            continue
        dfs(v2, color[v] ^ 1)


color = [-1]*n
is_ok = 1
dfs(0)


def bfs(init_v):
    next_v = deque([init_v])
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)
    return dist

if is_ok:
    ans = 0
    for i in range(n):
        dist = bfs(i)
        x = max(dist)
        if ans < x:
            ans = x
    print(ans+1)
else:
    print(-1)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for i in range(n):
    s = list(map(int, list(input().rstrip())))
    for j in range(n):
        if s[j]:
            edges[i].append(j)

            
def dfs(v):
    for v2 in edges[v]:
        if color[v2] != -1:
            if color[v] == color[v2]:
                global is_ok
                is_ok = 0
            continue
        color[v2] = color[v] ^ 1
        dfs(v2)


color = [-1]*n
color[0] = 0
is_ok = 1
dfs(0)


def bfs(init_v):
    next_v = deque([init_v])
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)
    return dist


if is_ok:
    ans = 0
    for i in range(n):
        dist = bfs(i)
        x = max(dist)
        if ans < x:
            ans = x
    print(ans+1)
else:
    print(-1)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for i in range(n):
    s = list(map(int, list(input().rstrip())))
    for j in range(n):
        if s[j]:
            edges[i].append(j)


def dfs(v, parent, d):
    visited[v] = 1
    depth[v] = d
    for v2 in edges[v]:
        if v2 == parent:
            continue
        if visited[v2]:
            d2 = depth[v2]
            n_cycle = d-d2+1
            if 0 < n_cycle:
                cycle.append(n_cycle)
            continue
        dfs(v2, v, d+1)


cycle = []
depth = [0]*n
visited = [0]*n
dfs(0, -1, 0)


def bfs(init_v):
    next_v = deque([init_v])
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)
    return dist


if all(c % 2 == 0 for c in cycle):
    ans = 0
    for i in range(n):
        dist = bfs(i)
        x = max(dist)
        if ans < x:
            ans = x
    print(ans+1)
else:
    print(-1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    adj = []
    for i in range(N):
        adj.append(S())

    def bfs(v):
        group = [-1] * N
        q = deque([(v, 0)])
        group[v] = 0
        while q:
            cur_v, gid = q.popleft()
            for next_v in range(N):
                if adj[cur_v][next_v] == '0':
                    continue
                if group[next_v] != -1:
                    if abs(group[cur_v] - group[next_v]) > 1:
                        return -1
                    if group[cur_v] == group[next_v]:
                        return -1
                    else:
                        continue
                group[next_v] = gid + 1
                q.append((next_v, gid+1))
        return max(group) + 1

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

    print(ans)

main()

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

def main():
    n = int(input())
    s = np.array([list(input()) for _ in range(n)], dtype=np.int64)
    wf = csgraph_from_dense(s)
    wf = shortest_path(wf, method="FW")
    idx = -1
    tmp = 0
    for i in range(n):
        for j in range(n):
            if wf[i][j] > tmp:
                idx = i
                tmp = wf[i][j]
    st = [set() for _ in range(int(tmp)+1)]
    f = True
    for j in range(n):
        x = int(wf[idx][j])
        for v in st[x]:
            if s[j][v] != 0:
                f = False
        st[x].add(j)
    if f:
        print(int(tmp)+1)
    else:
        print(-1)

if __name__ == "__main__":
    main()