Problem:
 Score : 500 points    Problem Statement Given is a connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N , and the edges are described by a grid of characters S .
If S_{i,j} is 1 , there is an edge connecting Vertex i and j ; otherwise, there is no such edge.  Determine whether it is possible to divide the vertices into non-empty sets V_1, \dots, V_k such that the following condition is satisfied. If the answer is yes, find the maximum possible number of sets, k , in such a division.   Every edge connects two vertices belonging to two "adjacent" sets. More formally, for every edge (i,j) , there exists 1\leq t\leq k-1 such that i\in V_t,j\in V_{t+1} or i\in V_{t+1},j\in V_t holds.       Constraints  2 \leq N \leq 200  S_{i,j} is 0 or 1 .  S_{i,i} is 0 .  S_{i,j}=S_{j,i}  The given graph is connected.  N is an integer.         Input Input is given from Standard Input in the following format:  N  S_{1,1}...S_{1,N}  :  S_{N,1}...S_{N,N}       Output If it is impossible to divide the vertices into sets so that the condition is satisfied, print -1 .
Otherwise, print the maximum possible number of sets, k , in a division that satisfies the condition.        Sample Input 1 2
01
10      Sample Output 1 2  We can put Vertex 1 in V_1 and Vertex 2 in V_2 .       Sample Input 2 3
011
101
110      Sample Output 2 -1       Sample Input 3 6
010110
101001
010100
101000
100000
010000      Sample Output 3 4

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, c):
        for u in edge[v]:
            if color[u] is None:
                color[u] = c
                dfs(u, c ^ 1)
            else:
                if color[u] != c:
                    print(-1)
                    exit()

    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)
                edge[j].append(i)

    color = [None] * n
    dfs(0, 0)
    for i in range(n):
        for j in range(n):
            if i == j:
                S[i][j] = 0
            else:
                S[i][j] = f_inf if S[i][j] == "0" else 1

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

    res = 0
    for s in S:
        res = max(res, max(s))
    print(res + 1)


if __name__ == '__main__':
    resolve()

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


N = int(input())
A = [[int(a) for a in input()] for _ in range(N)]
graph = np.array(A)
dist_mat = floyd_warshall(graph).astype(np.int64)
max_d = dist_mat.max()

B = np.where(dist_mat[0]%2 == 0)
C = np.where(dist_mat[0]%2 == 1)

bl = (graph[B][:, B] == 0).all() and (graph[C][:, C] == 0).all()



if bl:
    print(max_d + 1)
else:
    print(-1)

Solution (Python):
n = int(input())
S = [list(input()) for i in range(n)]
e = [[] for i in range(n)]
count = [0]*n
for i in range(n):
    count[i] = S[i].count("1")
    for j in range(i+1,n):
        if S[i][j] == "1":
            e[i].append(j)
            e[j].append(i)

m = min(count)
ans = 0
for i in range(n):
    dis = [float("INF")]*n
    dis[i] = 0
    check = True
    l = [i]
    d = 0
    while check:
        nl = []
        for j in l:
            for nex in e[j]:
                if dis[nex] < d-1 or dis[nex] == d:
                    check = False
                    break
                if dis[nex] == float("INF"):
                    nl.append(nex)
                    dis[nex] = d+1
            if check == False:
                break
        if check == False:
            d = float("INF")
            break
        if nl:
            l = nl
            d += 1
        else:
            break
    if d != float("INF"):
        ans = max(ans,d+1)
print(ans if ans != 0 else -1)

Solution (Python):
from collections import deque

def bfs(i):
    q = deque()
    q.append(i)
    dist = [0] * n
    dist[i] = 1
    maxdist = 1
    while q:
        p = q.popleft()
        for j in G[p]:
            if dist[j] == 0:
                dist[j] = dist[p] + 1
                maxdist = max(maxdist, dist[j])
                q.append(j)
            elif dist[p] == dist[j]:
                return
    global ans
    ans = max(ans, maxdist)
    return

n = int(input())
s = [list(input()) 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)
ans = -1
for i in range(n):
    bfs(i)
print(ans)

Solution (Python):
import collections

n = int(input())
g = [[] for i in range(n)]
for i in range(n):
    S =input()
    for j in range(i+1,n):
        if S[j]=="1":
            g[i].append(j)
            g[j].append(i)
def bfs(s):
    vis = [False]*n
    cnts=[0]*n
    que = collections.deque()
    cnt=1
    que.append((s,cnt))
    vis[s]=True
    cnts[s]=1
    while que:
        s,cnt = que.popleft()
        for node in g[s]:
            if not vis[node]:
                vis[node]=True
                cnts[node]=cnt+1
                que.append((node,cnt+1))
            else:
                if (cnts[node]+cnt)%2==0:
                    print(-1)
                    exit()
    return cnt
ans = 0
for node in range(n):
    ans = max(bfs(node),ans)
print(ans)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

n = ni()
g = [[] for i in range(n)]
for i in range(n):
    S =input()
    for j in range(i+1,n):
        if S[j]=="1":
            g[i].append(j)
            g[j].append(i)
visited=[False]*n
def bfs(s):
    que = collections.deque()
    que.append(s)
    visited[s]=True
    ls=[s]
    while que:
        s = que.popleft()
        for node in g[s]:
            if not visited[node]:
                visited[node]=True
                que.append(node)
                ls.append(node)
    return ls
def bfs2(s):
    vis = [False]*n
    cnts=[0]*n
    que = collections.deque()
    cnt=1
    que.append((s,cnt))
    vis[s]=True
    cnts[s]=1
    while que:
        s,cnt = que.popleft()
        for node in g[s]:
            if not vis[node]:
                vis[node]=True
                cnts[node]=cnt+1
                que.append((node,cnt+1))
            else:
                if (cnts[node]+cnt)%2==0:
                    print(-1)
                    exit()
    return cnt

ans = 0
for i in range(n):
    if not visited[i]:
        ls = bfs(i)
        
        tmp = 0
        for node in ls:
            tmp = max(bfs2(node),tmp)
        ans+=tmp
print(ans)

Solution (Python):
from collections import deque

N=int(input())
E=[[] for _ in range(N+1)]
P=[]

for a in range(1,N+1):
    S=input()
    for b in range(1,N+1):
        if S[b-1]=="1":
            E[a].append(b)

            if a<b:
                P.append((a,b))

M=-1
for a in range(1,N+1):
    Q=deque([a])
    T=[0 for i in range(N+1)]
    T[a]=1
    while Q:
        v=Q.popleft()
        for w in E[v]:
            if T[w]==0:
                T[w]=T[v]+1
                Q.append(w)

    F=True
    for (u,v) in P:
        F&=(abs(T[u]-T[v])==1)

    if F:
        M=max(M,max(T))

print(M)

Solution (Python):
from collections import deque

N=int(input())
E=[[] for _ in range(N+1)]
P=[]

for a in range(1,N+1):
    S=input()
    for b in range(1,N+1):
        if S[b-1]=="1":
            E[a].append(b)

            if a<b:
                P.append((a,b))

M=-1
for a in range(1,N+1):
    Q=deque([a])
    T=[0 for i in range(N+1)]
    T[a]=1
    while Q:
        v=Q.popleft()
        for w in E[v]:
            if T[w]==0:
                T[w]=T[v]+1
                Q.append(w)

    F=True
    for (u,v) in P:
        F&=(abs(T[u]-T[v])==1)

    if F:
        M=max(M,max(T))

print(M)

Solution (Python):
n=int(input())
G=[""]+["x"+input() for s in range(n)]
V=[0 for i in range(n+1)] 

V[1]=1
que=[1]
head=0
while len(que)>head:
    now=que[head]
    head+=1
    nexr=G[now]
    for i in range(1,n+1):
        if nexr[i]=="1" and V[i]==0:
            V[i]=V[now]+1
            que.append(i)

flg=True
for i in range(1,n):
    for q in range(i+1,n+1):
        if G[i][q]=="1" and abs(V[i]-V[q])!=1:
            flg=False

if flg:
    ans=0
    for sta in range(1,n+1):
        V=[0 for i in range(n+1)] 
        V[sta]=1
        que=[sta]
        head=0
        while len(que)>head:
            now=que[head]
            head+=1
            nexr=G[now]
            for i in range(1,n+1):
                if nexr[i]=="1" and V[i]==0:
                    V[i]=V[now]+1
                    que.append(i)
        ans=max(max(V),ans)
    print(ans)
        
else:
    print(-1)

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def judge(g):
    n = len(g)
    bi = [-1] * n
    bi[0] = 0
    for cn in range(n):
        for i, row in enumerate(g):
            for j, column in enumerate(row):
                if column == "1":
                    if bi[i] == -1 and bi[j] == -1:
                        pass
                    elif bi[i] == -1:
                        bi[i] = bi[j] ^ 1
                    elif bi[j] == -1:
                        bi[j] = bi[i] ^ 1
                    else:
                        if bi[i] == bi[j]:
                            print(-1)
                            sys.exit()




def solve():
    n = getN()
    g = []
    for i in range(n):
        g.append([c for c in getS()])

    judge(g)

    costs = [[INF for i in range(n)] for j in range(n)]
    for i in range(n):
        costs[i][i] = 0

    for i, row in enumerate(g):
        for j, column in enumerate(row):
            if column == "1":
                costs[i][j] = 1

    V = n
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if costs[i][k] != INF and costs[k][j] != INF:
                    costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

    ans = max([max(x) for x in costs])
    print(ans + 1)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
from itertools import count
def max_dist(adj,v):

    q = [v]
    visited = [False]*len(adj)
    visited[v] = True
    last = None
    for d in count():
        if not q:
            return d,last
        nq = []
        last = q[0]
        for v in q:
            for u in adj[v]:
                if not visited[u]:
                    visited[u] = True
                    nq.append(u)
        q = nq


def solve(S):

    N = len(S)

    adj = [[] for _ in range(N)]
    for i,l in enumerate(S):
        for j,f in enumerate(l):
            if f:
                adj[i].append(j)

    stack = [0]
    color = [None]*N
    color[0] = True

    while stack:
        v = stack.pop()
        nc = not color[v]
        for u in adj[v]:
            if color[u] is None:
                color[u] = nc
                stack.append(u)
            elif color[u] != nc:
                return -1

    return max(max_dist(adj,v)[0] for v in range(N))

if __name__ == '__main__':
    N = int(input())
    S = [[c=='1' for c in input()] for _ in range(N)]
    print(solve(S))

Solution (Python):
from collections import*
n=int(input())
s=[input() for _ in range(n)]
e=[[]for _ in range(n)]
INF=10**18
for i,x in enumerate(s):
  for j,y in enumerate(x):
    if y=='1':e[i]+=[j]
ans=0
for i in range(n):
  d=[INF]*n
  q=deque([i])
  d[i]=1
  while q:
    now=q.popleft()
    for to in e[now]:
      if d[to]==INF:
        q+=[to]
        d[to]=d[now]+1
      elif d[to]!=d[now]+1 and d[to]!=d[now]-1:
        print(-1)
        exit()
  ans=max(max(d),ans)
print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)



import numpy as np





INF = 1 << 50
EPS = 1e-8

def check_merge(merged,S):
    merged = np.array(merged)
    check = S[merged][:, merged]
    if check.sum():
        return False
    return True

def run():
    N = int(sysread())
    S = []
    for i in range(N):
        S.append(list(map(int, list(input()))))
    S = np.array(S, dtype=np.int8)

    ans = 0

    
    
    for k in range(N):
        
        seen = set()
        seen.add(k)
        merged = [k]
        count = 0
        while merged:
            
            count += 1
            nexts = []
            for i in merged:
                for j, e in enumerate(S[i]):
                    if int(e) and not j in seen:
                        nexts.append(j)
                        seen.add(j)
            if not check_merge(merged, S):
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)
import math








INF = 1 << 50
EPS = 1e-8

def check_merge(merged,S):
    merged = set(merged)
    for i in merged:
        for j, e in enumerate(S[i]):
            if int(e) and j in merged:
                return False
    return True

def run():
    N = int(sysread())
    S = []
    for i in range(N):
        S.append(input())

    ans = 0

    
    
    for k in range(N):
        
        seen = set()
        seen.add(k)
        merged = [k]
        count = 0
        while merged:
            
            count += 1
            nexts = []
            for i in merged:
                for j, e in enumerate(S[i]):
                    if int(e) and not j in seen:
                        nexts.append(j)
                        seen.add(j)
            if not check_merge(merged, S):
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    run()

Solution (Python):



n = int(input())

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

for i in range(n):
    s = input()
    for j, sj in enumerate(s):
        d[i][i] = 1
        if sj == '1':
            graph[i].append(j)
            d[i][j] = 1
            d[j][i] = 1

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


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





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

    return d 




if is_bipartite():
    ret = 0
    for a in warshall_floyd(d,n):
        ret = max(ret, max(a))
    print(ret+1)
else:
    print(-1)

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

es = [[] for _ 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()

dist = [[N]*N for _ in range(N)]
for i,row in enumerate(S):
    for j,c in enumerate(row):
        if i==j:
            dist[i][j] = 0
        elif c=='1':
            dist[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    n = int(readline())
    s = [input() for _ in range(n)]
    ans = 0
    que = deque()

    for i in range(n):
        dist = [-1] * n
        dist[i] = 0
        que.append((i, 0))
        while que:
            cur, d = que.popleft()
            adj = s[cur]
            for nx, is_connected in enumerate(adj):
                if is_connected == "1":
                    if dist[nx] == -1:
                        dist[nx] = d + 1
                        que.append((nx, d + 1))
                    else:
                        if dist[nx] % 2 != (d + 1) % 2:
                            return print(-1)
            ans = max(ans, max(dist) + 1)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N = int(input())
S = []
for _ in range(N):
  S.append(input())
  
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)


visited = [False] * N
willSearch = [False] * N
Color = [-1] * N
Q = deque()
Q.append((0,0))
while Q:
  now, c = Q.pop()
  visited[now] = True
  Color[now] = c
  for nxt in G[now]:
    if Color[nxt] >= 0 and c == Color[nxt]:
      
      print(-1)
      exit(0)
    if visited[nxt] or willSearch[nxt]:
      continue
    Q.append((nxt,1-c)) 
    willSearch[nxt] = True
    
INF = 1000
D = [[INF for _ in range(N) ]  for _ in range(N)]
for i in range(N):
  for nxt in G[i]:
    D[i][nxt] = 1
    D[nxt][i] = 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])
      


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

Solution (Python):
import numpy as np
import scipy.sparse
n = int(input())
s = np.array([list(map(int, list(input()))) for i in range(n)])
d = scipy.sparse.csgraph.floyd_warshall(scipy.sparse.csr_matrix(s))
l = d[:, np.argmax(d) % n]
for i in range(n):
    for j in range(i + 1, n):
        if s[i, j] == 1 and abs(l[i] - l[j]) != 1:
            exit(print(-1))
print(int(np.amax(d) + 1))

Solution (Python):
n=int(input())
s=[[0]*n for _ in range(n)]
for i in range(n):
	r=input()
	for j in range(n):
		if r[j]=="1":
			s[i][j]=1
ans=0
from collections import deque
for i in range(n):
	queue=deque([i])
	num=[-1]*n
	num[i]=0
	while queue:
		r=queue.popleft()
		for j in range(n):
			if s[r][j]==1 and num[j]==-1:
				num[j]=num[r]+1
				queue.append(j)
	MAX=max(num)
	p=[[]for _ in range(MAX+1)]
	for i in range(n):
		p[num[i]].append(i)
	ok=1
	for i in range(MAX+1):
		for x in p[i]:
			for y in p[i]:
				if s[x][y]==1:
					ok=0
					break
			if ok==0:
				break
		if ok==0:
			break
	if ok:
		ans=max(ans,MAX+1)
print(ans if ans else -1)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge):

    search = [-1] * N
    search[v0] = 1
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        now_color = search[v]
        for nv in edge[v]:
            if search[nv] == -1:
                q.append(nv)
                search[nv] = now_color + 1
            elif search[nv] == now_color:
                return None

    return max(search)


def main():

    N = in_n()

    edge = [[] for _ in range(N)]
    for i in range(N):
        edge[i] = [j for j, n in enumerate(readline()) if n == ord('1')]

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

    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7



'''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())'''

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=I()

w=0
d = [[float("inf")]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
mat=[[] for i in range(n)]
for i in range(n):
    s=list(SI())
    for j in range(n):
        if int(s[j])==1:
            w+=1
            d[i][j]=1
            d[j][i]=1
            mat[i].append(j)
            
col=[0 for i in range(n)]


col[0]=1
def dfs(x):
    for y in mat[x]:
        if col[y]==0:
            col[y]=(-1)*col[x]
            dfs(y)
        elif col[y]!=col[x]*(-1):
            print(-1)
            exit()
dfs(0)


        
'''nodes=[0 for i in range(2*n)]
uf=UnionFind(2*n)
for i in range(n):
    for j in range(i,n):
        if d[i][j]==1:
            uf.union(i,n+j)
            uf.union(j,n+i)
for i in range(n):
    if uf.same(i,i+n):
        print(-1)
        sys.exit()'''
warshall_floyd(d)

ans=0
for i in range(n):
    for j in range(n):
        if d[i][j]<inf and d[i][j]>ans:
            ans=d[i][j]
print(ans+1)

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7



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

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=I()

w=0
d = [[float("inf")]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for i in range(n):
    s=list(SI())
    for j in range(n):
        if int(s[j])==1:
            w+=1
            d[i][j]=1
            d[j][i]=1
    
nodes=[0 for i in range(2*n)]
uf=UnionFind(2*n)
for i in range(n):
    for j in range(i,n):
        if d[i][j]==1:
            uf.union(i,n+j)
            uf.union(j,n+i)
for i in range(n):
    if uf.same(i,i+n):
        print(-1)
        sys.exit()
warshall_floyd(d)

ans=0
for i in range(n):
    for j in range(n):
        if d[i][j]<inf and d[i][j]>ans:
            ans=d[i][j]
print(ans+1)

Solution (Python):
from collections import deque
INFTY = 1000
N = int(input())
S = [list(map(int,list(input()))) for _ in range(N)]
G = {i:[] for i in range(1,N+1)}
for i in range(N-1):
    for j in range(i+1,N):
        if S[i][j]==1:
            G[i+1].append(j+1)
            G[j+1].append(i+1)
heap = deque([(1,0)])
hist = [0 for _ in range(N+1)]
col = [-1 for _ in range(N+1)]
hist[1] = 1
col[1] = 0
flag = 0
while heap:
    x,c = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            col[y] = 1-c
            heap.append((y,1-c))
            hist[y]=1
        else:
            if col[y]!=1-c:
                flag = 1
                break
    if flag==1:break
if flag==1:
    print(-1)
else:
    dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            if i==j:
                dist[i+1][j+1]=0
            if S[i][j]==1:
                dist[i+1][j+1]=1
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
    dmax = 0
    for i in range(1,N+1):
        for j in range(1,N+1):
            dmax = max(dmax,dist[i][j])
    print(dmax+1)

Solution (Python):
from collections import deque

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

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


ans = -1

for i in range(N):
    queue = deque([i])
    visit = [-1] * N
    visit[i] = 1

    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
    
    dist = [[] for _ in range(max(visit))]
    for j in range(N):
        dist[visit[j]-1].append(j)

    flag = True
    for d in dist:
        if len(d) < 2: continue
        for k in d:
            for l in d:
                if k == l: continue
                if S[k][l] == '1':
                    flag = False
                    break

    if flag:
        ans = max(ans,max(visit))

print(ans)

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(S, i):
    D = [-1] * len(S)
    P = [set() for _ in range(len(S))]
    
    Q = deque()
    Q.append(i)
    D[i] = 1

    while Q:
        v = Q.popleft()

        for w in S[v]:
            if w in P[v]:
                continue
            
            if D[w] > 0 and D[w] < D[v] + 1:
                return -1

            if D[w] < 0:
                Q.append(w)
            P[w].add(v)
            D[w] = D[v] + 1

    return D[v]


def main():
    N = int(input())
    S = [input().strip() for _ in range(N)]
    L = [set(j for j in range(N) if S[i][j] == "1") for i in range(N)]

    res = -1
    for i in range(N):
        r = f(L, i)
        res = max(res, r) 
    
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import networkx as nx

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

G = nx.Graph()
for i in range(N):
    G.add_node(i)

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

if nx.is_bipartite(G):
    ans = nx.diameter(G)+1
    print(ans)
else:
    print(-1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, graph, cur=0):
        color[v] = cur
        for u in graph[v]:
            if color[u] != -1:
                if color[u] == cur:
                    return False
                continue
            if not dfs(u, graph, 1 - cur):
                return False
        return True

    n = int(input())
    S = [list(input()) for _ in range(n)]
    edge = [[] for _ in range(n)]
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                cost[i][j] = 0
            if S[i][j] == "1":
                edge[i].append(j)
                cost[i][j] = 1

    color = [-1] * n
    if not dfs(0, edge):
        print(-1)
        exit()

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

    res = 0
    for i in range(n):
        res = max(res, max(cost[i]))
    print(res + 1)


if __name__ == '__main__':
    resolve()