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
def main():
    input = sys.stdin.readline
    N = int(input())
    S = [list(input().rstrip()) for _ in range(N)]

    color = [-1] * N
    color[0] = 0
    stack = [0]
    while stack:
        v = stack.pop()
        for to in range(N):
            if S[v][to] == '0': continue
            if color[to] >= 0:
                if color[to] == color[v]:
                    print(-1)
                    exit()
                continue
            stack.append(to)
            color[to] = color[v]^1

    D = [[10**9] * 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])
    print(max(max(d) for d in D) + 1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    S = [list(input().rstrip()) for _ in range(N)]

    uf = UnionFindTree(N*2)
    for i in range(N):
        for j in range(i+1,N):
            if S[i][j] == '1':
                uf.union(i, j+N)
                uf.union(i+N, j)
    
    for i in range(N):
        if uf.same(i, i+N):
            print(-1)
            exit()

    D = [[10**9] * 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])
    d_max = max(max(s) for s in D)
    print(d_max+1)

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
sys.setrecursionlimit(10**7)

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

n = int(input())
S = np.frombuffer(read(),'S1').reshape(n, n+1)[:, :n].astype(np.int64)
G = csgraph_from_dense(S)

F = floyd_warshall(G).astype(np.int64)

C = [-1]*n
def dfs(v, c):
  C[v] = c
  for nv, i in enumerate(S[v]):
    if not i:
      continue
    if C[nv] != -1:
      if not (C[v] ^ C[nv]):
        return False
    else:
      if not dfs(nv, c^1):
        return False
  return True

if dfs(0, 0):
  ans = F.max() + 1
  print(ans)
else:
  print(-1)

Solution (Python):
from collections import deque
def bfs(G, s):
    cost=[-1]*len(G)
    cost[s]=1
    deq=deque([s])
    while deq:
        u=deq.popleft()
        for v in G[u]:
            if cost[v]<0:
                cost[v]=cost[u]+1
                deq.append(v)
            elif abs(cost[u]-cost[v])!=1:
                return -1
    return max(cost)

def main():
    N=int(input())
    S=[[bool(int(i)) for i in input()] for _ in range(N)]
    G=[[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j]:
                G[i].append(j)
    print(max(bfs(G,i) for i in range(N)))

if __name__ == "__main__":
    main()

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

data=[[] for i in range(N)]
for y in range(N):
    for x in range(N):
        if S[y][x]=="1":
            data[y].append(x)

visited=[-1 for i in range(N)]
visited[0]=0
stack=[[0,0]]

while stack:
    a,m=stack.pop()
    for p in data[a]:
        if visited[p]==m:
            print(-1)
            exit()
        else:
            if visited[p]==-1:
                n=(m+1)%2
                visited[p]=n
                stack.append([p,n])


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

for x in range(len(d)):
    d[x][x]=0
for x in range(len(data)):
    for y in data[x]:
        d[x][y]=1
        d[y][x]=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])
print(max([max([i for i in l]) for l in d])+1)

Solution (Python):
from collections import defaultdict, deque
N = int(input())
dic = defaultdict(list)
for i in range(N):
  inf = [int(c) for c in input()]
  for j in range(N):
    if inf[j]:
      dic[i] += [j]
      dic[j] += [i]
ans = 0
for i in range(N):
  q = deque([i])
  dist = [float('inf')]*N
  dist[i] = 0
  m = 0
  while q:
    p = q.popleft()
    for e in dic[p]:
      if dist[e]==dist[p]:
        print(-1)
        import sys
        sys.exit()
      if dist[e]>dist[p]+1:
        dist[e] = dist[p]+1
        q += [e]
        m = max(m,dist[e])
  ans = max(ans,m)
print(ans+1)

Solution (Python):
from sys import stdout
from collections import deque
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

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

ddprint(dst)

mx = 0
for i in range(n):
    d = [-1]*n
    d[i] = 0
    q = deque([i])
    while len(q)>0:
        x = q.popleft()
        for y in dst[x]:
            if d[y]>=0 and (d[y]-d[x])%2 == 0:
                ddprint("x {} y {} dx {} dy {}".format(x,y,d[x],d[y]))
                print(-1)
                exit()
            if d[y]<0:
                d[y] = d[x]+1
                mx = max(mx,d[y])
                q.append(y)
print(mx+1)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
edge = np.array([list(input()) for _ in range(N)]).astype(int)

def is_bipartite(N, edge):
    color = [-1]*N
    graph = [np.nonzero(i)[0].tolist() for i in edge]

    node = [0]
    color[0] = 0
    while node:
        s = node.pop()
        col_s = color[s]
        for t in graph[s]:
            col_t = color[t]
            if col_t == -1:
                color[t] = 1-col_s
                node.append(t)
            elif col_t == col_s:
                return False
            else:
                continue
    return True


if is_bipartite(N, edge):
    wf = floyd_warshall(edge).astype(int)
    ans = wf.max()+1
else:
    ans = -1

print(ans)

Solution (Python):
from collections import deque
n = int(input())
ls = [list(input()) for i in range(n)]
graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
parity = [-1 for i in range(n+1)]
dist = [0 for i in range(n+1)]
for i in range(n):
  for j in range(i,n):
    if ls[i][j] == "1":
      graph[i+1].append(j+1)
      graph[j+1].append(i+1)
que = deque([(1,0)])
parity[1] = 0
visited[1] = 1
while que:
  x,cnt = que.popleft()
  dist[x] = cnt
  for y in graph[x]:
    if visited[y] == 0:
      que.append((y,cnt+1))
      visited[y] = 1
      parity[y] = 1-parity[x]
ans = []
for v in range(1,n+1):
  que.append((v,0))
  visited = [0 for i in range(n+1)]
  visited[v] = 1
  dist = [0 for i in range(n+1)]
  while que:
    x,cnt = que.popleft()
    dist[x] = cnt
    for y in graph[x]:
      if visited[y] == 0:
        que.append((y,cnt+1))
        visited[y] = 1
      if parity[y] == parity[x]:
        print(-1)
        exit()
  ans.append(max(dist))
print(max(ans)+1)

Solution (Python):
from collections import deque
n = int(input())
ls = [list(input()) for i in range(n)]
graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
parity = [-1 for i in range(n+1)]
dist = [0 for i in range(n+1)]
for i in range(n):
  for j in range(i,n):
    if ls[i][j] == "1":
      graph[i+1].append(j+1)
      graph[j+1].append(i+1)
que = deque([(1,0)])
parity[1] = 0
visited[1] = 1
while que:
  x,cnt = que.popleft()
  dist[x] = cnt
  for y in graph[x]:
    if visited[y] == 0:
      que.append((y,cnt+1))
      visited[y] = 1
      parity[y] = 1-parity[x]





ans = []
for far in range(1,n+1):
  que.append((far,0))
  visited = [0 for i in range(n+1)]
  visited[far] = 1
  dist = [0 for i in range(n+1)]
  while que:
    x,cnt = que.popleft()
    dist[x] = cnt
    for y in graph[x]:
      if visited[y] == 0:
        que.append((y,cnt+1))
        visited[y] = 1
      if parity[y] == parity[x]:
        print(-1)
        exit()
  ans.append(max(dist))
print(max(ans)+1)

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    sa = [S() for _ in range(n)]
    e = collections.defaultdict(set)
    for i in range(n):
        s = sa[i]
        for j in range(i+1,n):
            if s[j] == '1':
                e[i].add(j)
                e[j].add(i)

    r = -1
    for i in range(n):
        k = 1
        a = [set(), set([i])]
        u = set([i])
        while len(u) < n:
            k += 1
            v = set()
            for c in a[k-1]:
                v |= e[c]
            v -= a[k-2]
            if len(v & u) > 0:
                k = -1
                break
            vv = set()
            for c in v:
                vv |= e[c]
            if len(vv & v) > 0:
                k = -1
                break
            a.append(v)
            u |= v
        if r < k:
            r = k

    return r


print(main())

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


INF = 10 ** 15

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


for i in range(N):
  for j in range(N):
    if S[i][j] == 0  and i != j:
      S[i][j] = 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])


answer = -2
for i in range(N):
  flag = 1
  for A, B in AB:
    if abs(S[i][A] - S[i][B]) != 1:
      flag = 0
      break
  if flag:
    answer = max(answer, max(S[i]))

print(answer + 1)

Solution (Python):
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq


def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()

def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    ma = 0
    e = [[] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if(S[i][j] == '1'): e[i].append(j) 
    for i in range(N):
        dep = [-1] * N
        q = collections.deque()
        dep[i] = 0
        q.append(i)
        while(len(q) > 0):
            now = q.popleft()
            for nxt in e[now]:
                if dep[nxt] == -1:
                    dep[nxt] = dep[now] + 1
                    q.append(nxt)
        for j in range(N):
            ma = max(ma, dep[j])
    
    print(ma + 1)
        

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
import sys

import collections
from functools import cmp_to_key
import heapq


def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()

def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    inf = int(1e9)
    wf = [[inf] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            wf[i][j] = 1 if S[i][j] == '1' else inf
            if i == j: wf[i][j] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    
    ma = 0
    for i in range(N):
        for j in range(N):
            ma = max(ma, wf[i][j])

    print(ma + 1)

if __name__ == "__main__":
    main()

Solution (Python):



from collections import deque

n = int(input())
s = []

for i in range(n):
    sij = input()
    s.append(sij)
    
d = [-1]*n

Q = deque()

d[0] = 0

Q.append(0)

while Q:
    v = Q.popleft()
    for i in range(n):
        if int(s[v][i]):
            if d[i]<0:
                d[i] = d[v] + 1
                Q.append(i)
            elif (d[i]-d[v])%2==0:
                print(-1)
                exit()

mxd = max(d)
mxd_id = d.index(mxd)

"""   
d2 = [-1]*n

d2[mxd_id] = 0

Q.append(mxd_id)

while Q:
    v = Q.popleft()
    for i in range(n):
        if int(s[v][i]):
            if d2[i]<0:
                d2[i] = d2[v] + 1
                Q.append(i)
"""


dd = [[10**5 for i in range(n)] for j in range(n)]
for i in range(n):
    dd[i][i] = 0
    for j in range(n):
        if int(s[i][j]):
            dd[i][j] = 1
for k in range(n):
    for i in range(n):
        for j in range(n):
            dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j])
            

ans = 0

for i in range(n):
    for j in range(n):
        ans = max(ans, dd[i][j])

print(ans+1)

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

n=int(input())
l=[]
ll=[]
E=[[] for i in range(n)]

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

for i in range(n):
    s=input()
    ll.append(s)
    for j in range(n):
        if s[j]=="1":
            l.append([i,j,1])
            E[i].append(j)
            E[j].append(i)

edge=np.array(l,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2])),(n,n))

dist_mat = floyd_warshall(graph).astype(np.int32)
 
max_d = dist_mat.max()
 
def dfs(cur, pre, col):
    stack = deque([[cur, pre, col]])
    while stack:
        cur, pre, col = stack.pop()
        if V[cur] and V[cur] != col:
            return False
        else:
            V[cur] = col
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, -1 * col])
        
        E[cur] = []
    return True
 

if not dfs(0, -1, 1):
    print(-1)
    exit()

answer = max_d + 1
print(answer)

Solution (Python):
import sys
from collections import deque

n = int(input())


dp = [[2*n for i in range(n)] for j in range(n)]
E = [[] for i in range(n)]


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


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

def dfs(cur, pre, col):
    stack = deque([[cur, pre, col]])
    while stack:
        cur, pre, col = stack.pop()
        if V[cur] and V[cur] != col:
            return False
        else:
            V[cur] = col
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, -1 * col])
        
        E[cur] = []
    return True


if not dfs(0, -1, 1):
    print(-1)
    sys.exit()

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


warshall_floyd()


diam = 0
for i in range(n):
    for j in range(n):
        diam = max(dp[i][j], diam)

print(diam+1)

Solution (Python):
def main():
    import numpy as np
    import scipy.sparse.csgraph as sp
    n = int(input())
    gg = [input() for _ in [0]*n]
    graph = [[] for _ in [0]*n]

    inf = float('inf')

    dist = np.full((n, n), inf)

    for i in range(n):
        dist[i, i] = 0
        for j in range(n):
            if gg[i][j] == "1":
                graph[i].append(j)
                dist[i, j] = 1
                dist[j, i] = 1
    q = [0]
    dp = [0]*n
    dp[0] = 1

    flag = True
    while q:
        i = q.pop()
        for j in graph[i]:
            if dp[j] == 0:
                dp[j] = dp[i]*(-1)
                q.append(j)
            elif dp[j] == dp[i]:
                flag = False
                break
        if flag is False:
            break

    dist = np.array(dist)

    if flag is False:
        print(-1)
    else:
        dist = sp.shortest_path(dist)
        print(int(max([max([i for i in j]) for j in dist])+1))


main()

Solution (Python):
from heapq import heappush, heappop

N = int(input())
vec = [[] for _ in range(N)]
for i in range(N) :
    for j, v in enumerate(input()) :
        if v == '1' :
            vec[i].append(j)

def bfs(s) :
    dist = [float('inf')] * N
    queue = [(1, s)]
    dist[s] = 1
    
    while queue :
        co, cur = heappop(queue)
        if dist[cur] < co :
            continue
            
        for nex in vec[cur] :
            if co + 1 < dist[nex] :
                dist[nex] = co + 1
                heappush(queue, (co + 1, nex))
                
    for i in range(N) :
        for j in vec[i] :
            if abs(dist[i] - dist[j]) != 1 :
                return -1
    
    return max(dist)

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

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

E = [set() for _ in range(N)]
for i in range(N):
  for j in range(N):
    if S[i][j] == '1':
      E[i].add(j)

C = [0 for _ in range(N)]
def dfs(v,c):
  C[v] = c
  for u in E[v]:
    if C[u] == c:
      return False
    if C[u] == 0 and not dfs(u,-c):
      return False
  return True

if not dfs(0,1):
  print(-1)
  exit()

G = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(N):
  G[i][i] = 0
for i in range(N):
  for j in range(N):
    if S[i][j] == '1':
      G[i][j] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      G[i][j] = min(G[i][k]+G[k][j],G[i][j])
ans = 0
for g in G:
  mx = max(g)
  ans = max(ans,mx)
print(ans+1)

Solution (Python):
q = list()
n = int(input())
a = [input() for _ in range(n)]
col = [-1]*n
col[0] = 0
q.append(0)
while q:
  v = q.pop()
  for i in range(n):
    if a[v][i] == '0':
      continue
    if col[i] < 0:
      col[i] = col[v]^1
      q.append(i)
    elif col[i] == col[v]:
      print(-1)
      exit(0)

dist = [[10**3]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    if a[i][j] == '1':
      dist[i][j] = 1
    elif i == j:
      dist[i][j] = 0

for k in range(n):
  for i in range(n-1):
    for j in range(i+1,n):
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j]
        dist[j][i] = dist[i][j]
print(max(max(x) for x in dist)+1)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



def warshall_floyd(G):
    dist = deepcopy(G)
    n = len(G)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


def bipartite_or_not(G, s=0):
    n = len(G)
    global color
    color = [0] * n
    color[s] = 1
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v, bit in enumerate(G[u]):
            if u == v or bit == '0':
                continue
            elif color[v] == 0:
                color[v] = -color[u]
                dq += [v]
            else:
                if color[u] == color[v]:
                    return False
    return True



n = I()
G = SRL(n)
if not bipartite_or_not(G):
    print(-1)
    exit()


for u in range(n):
    for v in range(n):
        if u == v:
            G[u][v] = 0
        elif G[u][v] == '1':
            G[u][v] = 1
        else:
            G[u][v] = INF


dist = warshall_floyd(G)
print(max([dist[u][v] for u in range(n) for v in range(u + 1, n)]) + 1)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
 
N = int(input())
S = [[0 if i==j else float("inf") for i in range(N)] for j in range(N)]
for i in range(N):
    S_list = list(input())
    for j in range(N):
        if S_list[j] == "0": continue
        S[i][j] = S[j][i] = int(S_list[j])
 

def is_bipartite_graph(adjacency_matrix):
    colors = [0] * len(adjacency_matrix)
    return dfs(0,1,colors,adjacency_matrix)

def dfs(v,color,colors,adjacency_matrix):
    
    colors[v] = color
    
    for to in range(len(adjacency_matrix[v])):
        
        if adjacency_matrix[v][to] != 1:
            continue
        
        if colors[to] == color:
            return False
        
        if colors[to] == 0 and not dfs(to,-color,colors,adjacency_matrix):
            return False
    
    return True
 
if is_bipartite_graph(S):
    d = floyd_warshall(S)
    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(int(answer)+1)
else:
    print(-1)

Solution (Python):
n=int(input())
l=[[] for i in range(n+1)]
for i in range(1,1+n):
  l1=list(input())
  for j in range(1,1+n):
    if l1[j-1]=="1":
      l[i].append(j)
color=[0 for i in range(n+1)]
b=True
def f(v,c):
    
    color[v] = c
    for i in range(len(l[v])):
        if color[ l[v][i] ] == c:
            return False
        elif color[ l[v][i] ] == 0 and not f(l[v][i],-c):
            
            return False
    return True
b=f(1,1)
if not b:
  print(-1)
else:
  inf=10**10
  d=[[inf for i in range(n+1)] for j in range(n+1)]
  for i in range(n+1):
    for j in l[i]:
      d[i][j]=1
  for k in range(n+1):
    for j in range(1,n+1):
      for i in range(1,n+1):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  max=0
  for i in range(1,n+1):
    for j in range(1,n+1):
      if i==j:
        pass
      elif d[i][j]>max:
        max=d[i][j]
  print(max+1)

Solution (Python):

n=int(input())
uselist=[[] for i in range(n+1)]
distancelist=[[10**5 for j in range(n)] for i in range(n)]
for i in range(n):
    s=input()
    for j in range(n):
        if int(s[j])!=0:
            distancelist[i][j]=1
            distancelist[j][i]=1
            uselist[i+1].append(j+1)

for i in range(n):
    distancelist[i][i]=0
visitedlist=[-1 for i in range(n)]
pointlist=[0 for j in range(n)]
flag=True
def search(i,string):
    visitedlist[i-1]=1
    if string==0:
        pointlist[i-1]="B"
    else:
        pointlist[i-1]=string
    flags=False 
    for node in uselist[i]:
        if visitedlist[node-1]==-1:
            
            flags=True
            visitedlist[node-1]=1
            if string=="B"or string==0:
                pointlist[node-1]="R"
            elif string=="R":
                pointlist[node-1]="B"
        else:
            pass
    if flags:
        
        for j in uselist[i]:
            search(j,pointlist[j-1])
    if not flags:
        
        pass    
search(1,0)
for j in range(1,n+1):
    for some in uselist[j]:
        if pointlist[j-1]==pointlist[some-1]:
            flag=False
if flag:
    
    for k in range(n):
        for j in range(n):
            for i in range(n):
                distancelist[i][j]=min(distancelist[i][j],distancelist[i][k]+distancelist[k][j])
    maxi=0
    for i in range(n):
        for j in range(n):
            maxi=max(maxi,distancelist[i][j])
    print(maxi+1)
else:
    print(-1)

Solution (Python):
import sys
n=int(input())
data=[[] for i in range(n+1)]
for i in range(1,n+1):
    s=[None]+list(input())
    for j in range(1,n+1):
        if s[j]=="1":
            data[i].append(j)


flag=[-1]*(n+1)
for i in range(1,n+1):
    if flag[i]==-1:
        que=[[i]]
        flag[i]=0
        k=1
        while que[0]:
            h=que[0]
            H=[]
            for u in h:
                for v in data[u]:
                    if flag[v]==-1:
                        flag[v]=k
                        H.append(v)
                    else:
                        if flag[v]==k:
                            continue
                        else:
                            print(-1)
                            sys.exit()
            k=(k+1)%2
            que=[H]


inf=float("inf")
d=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    d[i][i]=0
for i in range(1,n+1):
    for u in data[i]:
        d[i][u]=1
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        ans=max(ans,d[i][j])

print(ans+1)

Solution (Python):

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

N = int(input())
mat_original = [[int(c) for c in input()[:-1]] for _ in range(N)]
mat = [[1 if v == 1 else float('inf') for v in m] for m in mat_original]
for i in range(N):
    mat[i][i] = 0


def is_nibugurahu():
    visited = [0]*N
    visited[0] = 1
    Q = [0]
    while Q:
        q = Q.pop()
        for next in range(N):
            if mat_original[q][next] == 1:
                if visited[next] == 0:
                    visited[next] = visited[q]*(-1)
                    Q.append(next)
                elif visited[next] == visited[q]:
                    return False
                else:
                    pass
    return True


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


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

print(max([max(m) for m in mat])+1)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    A=[list(map(int,list(input()))) for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==0): A[i][j]=INF
    B=[a[:] for a in A] 
    E=[[] for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==1): E[i].append(j)

    
    d=[-1]*n 
    def dfs(v)->bool:
        
        res=True
        for nv in E[v]:
            if(d[nv]==-1):
                d[nv]=d[v]^1
                res=min(res,dfs(nv))
            else:
                res=min(res,d[nv]^d[v])
        return res

    for v in range(n):
        if(d[v]==-1):
            d[v]=0
            if(not dfs(v)):
                print(-1)
                return

    
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])

    
    diam=0
    for i,j in product(range(n),repeat=2):
        if(B[i][j]==INF): continue 
        diam=max(diam,B[i][j])
    print(diam+1)
resolve()