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

    
    from collections import deque
    d=[-1]*n 
    def bfs(v)->bool:
        
        if(d[v]!=-1): return True
        d[v]=0
        Q=deque([v])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(d[nv]==-1):
                    d[nv]=d[v]^1
                    Q.append(nv)
                else:
                    if(d[nv]^d[v]==0):
                        return False
        return True

    for v in range(n):
        if(not bfs(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()

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,p=-1)->bool:
        
        if(p==-1):
            if(d[v]!=-1): return True
            else: d[v]=0
        
        res=True
        for nv in E[v]:
            if(nv==p): continue
            if(d[nv]==-1):
                d[nv]=d[v]^1
                res=min(res,dfs(nv,v))
            else:
                res=min(res,d[nv]^d[v])
        return res

    for v in range(n):
        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()

Solution (Python):
from collections import deque

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

adjL = [[] for _ in range(N)]
for i, Ss in enumerate(Sss):
    for j, S in enumerate(Ss):
        if S == '1':
            adjL[i].append(j)

def IsBipartiteGraph(adjList):
    def bfs(vSt):
        colors[vSt] = 1
        Q = deque([vSt])
        while Q:
            vNow = Q.popleft()
            color = colors[vNow]
            for v2 in adjList[vNow]:
                if colors[v2] == color:
                    return False
                elif colors[v2] == 0:
                    colors[v2] = -color
                    Q.append(v2)
        return True
    numV = len(adjList)
    colors = [0] * numV
    for vSt in range(numV):
        if colors[vSt] != 0: continue
        if not bfs(vSt):
            return False
    return True

def getDiameterOfUnweightedGraph(adjList):
    numV = len(adjList)
    def bfs(vSt):
        costs = [-1] * numV
        costs[vSt] = cost = 0
        vs = [vSt]
        while vs:
            cost += 1
            v2s = []
            for v in vs:
                for v2 in adjList[v]:
                    if costs[v2] == -1:
                        costs[v2] = cost
                        v2s.append(v2)
            vs = v2s
        return cost - 1
    return max([bfs(vSt) for vSt in range(numV)])


if not IsBipartiteGraph(adjL):
    print(-1)
else:
    maxDist = getDiameterOfUnweightedGraph(adjL)
    print(maxDist+1)

Solution (Python):
from collections import deque

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

adjL = [[] for _ in range(N)]
for i, Ss in enumerate(Sss):
    for j, S in enumerate(Ss):
        if S == '1':
            adjL[i].append(j)

def IsBipartiteGraph(adjList):
    def bfs(vSt):
        colors[vSt] = 1
        Q = deque([vSt])
        while Q:
            vNow = Q.popleft()
            color = colors[vNow]
            for v2 in adjList[vNow]:
                if colors[v2] == color:
                    return False
                elif colors[v2] == 0:
                    colors[v2] = -color
                    Q.append(v2)
        return True
    numV = len(adjList)
    colors = [0] * numV
    for vSt in range(numV):
        if colors[vSt] != 0: continue
        if not bfs(vSt):
            return False
    return True

def WarshallFloyd(adjList):
    numV = len(adjList)
    D = [[float('inf')]*numV for _ in range(numV)]
    for u, adj in enumerate(adjList):
        for v in adj:
            D[u][v] = 1
        D[u][u] = 0
    for k in range(numV):
        Dk = D[k]
        for i in range(numV):
            Di = D[i]
            Dik = Di[k]
            for j in range(numV):
                D2 = Dik + Dk[j]
                if D2 < Di[j]:
                    D[i][j] = D2
    return D


if not IsBipartiteGraph(adjL):
    print(-1)
else:
    distss = WarshallFloyd(adjL)
    maxDist = max(map(max, distss))
    print(maxDist+1)

Solution (Python):

from collections import deque


def is_bipartite() -> bool:
    stack, color = [(1, 1)], [0] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = -cur_color
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if not color[u]:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(source: int) -> int:
    queue = deque([source])
    dist = [0] * (N + 1)  
    dist[source] = 1
    while queue:
        v = queue.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                queue.append(u)
    return max(dist)


def main():
    
    global N, E
    N, *S = open(0)
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
graph = [[300] * (N+1) for _ in range(N+1)] 
edges = []
for i in range(N+1):
    graph[i][i] = 0
for i in range(1, N+1):
    S = list(str(input()))
    for j in range(len(S)):
        if S[j] == '1':
            edges.append((i, j+1))
            graph[i][j+1] = graph[j+1][i] = 1
for k in range(N+1):
    for i in range(N+1):
        for j in range(i+1, N+1):
            x = graph[i][k] + graph[k][j]
            if x < graph[i][j]:
                graph[i][j] = graph[j][i] = x

colors = [None] * (N+1)
colors[1] = 0
que = [1]
while que:
    x = que.pop()
    for i in range(1, N+1):
        if graph[x][i] != 1 or x == i:
            continue
        if colors[i] is None:
            colors[i] = 1 - colors[x]
            que.append(i)


is_bg = all(colors[a] != colors[b] for a, b in edges)
if not is_bg:
    print(-1)
    exit()
print(max(max(x[1:]) for x in graph[1:]) + 1)

Solution (Python):


from collections import deque
n = int(input())
l = [input() for i in range(n)]

diam = -1    
for i in range(n):
    queue = deque([i])
    dist = [-1]*n
    dist[i] = 0
    while queue:
        u = queue.popleft()
        d = dist[u]
        ll = l[u]
        for v in range(n):
            if ll[v]=="1":
                if dist[v]==-1: 
                    dist[v] = d + 1
                    queue.append(v)
                else:
                    if abs(d-dist[v]) != 1:
                        print(-1)
                        exit()
    diam = max(diam, max(dist))

print(diam + 1)

Solution (Python):
n = int(input())
dis = [[0] * 205 for _i in range(205)]
for i in range(1, n + 1):
    dis[i][i] = 0
for i in range(1, n + 1):
    a = list(map(str, input().strip()))
    for j in range(n):
        if a[j] == '1':
            dis[i][j + 1] = 1


def bfs(x):
    mx = 0
    from collections import deque
    q = deque()
    l = [0] * 205
    q.append(x)
    l[x] = 1
    while len(q):
        x = q.popleft()
        mx = max(mx, l[x])
        for i in range(1, n + 1):
            if dis[x][i]:
                if l[i]:
                    if abs(l[i]-l[x]) == 1:
                        continue
                    else:
                        print(-1)
                        exit(0)
                else:
                    l[i] = l[x] + 1
                    q.append(i)
    return mx


ans = [0] * 205
for i in range(1, n + 1):
    ans[i] = bfs(i)

mark = [0] * 205
p = 0


def dfs(x):
    mark[x] = 1
    global p
    p = max(p, ans[x])
    for i in range(1, n + 1):
        if dis[x][i] and not mark[i]:
            dfs(i)


aas = 0
for i in range(1, n + 1):
    if not mark[i]:
        p = 0
        dfs(i)
        aas += p
print(aas)

Solution (Python):
import numpy as np
import sys
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
N = int(sys.stdin.buffer.readline())
S = np.frombuffer(sys.stdin.buffer.read(),
                  dtype='S1').reshape(N, -1)[:, :N].astype(int)
G = csgraph_from_dense(S)
F = floyd_warshall(G).astype(int)
F2 = F % 2
I0 = np.where(F2[0] == 0)
I1 = np.where(F2[0] == 1)
if (S[I0][:, I0] == 0).all() and (S[I1][:, I1] == 0).all():
    print(F.max() + 1)
    exit()
print(-1)

Solution (Python):
from collections import deque

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

for i in range(n):
    for j, e in enumerate(input()):
        if int(e): graph[i].append(j)

def bfs(start):
    q = deque([start])
    dist = [-1] * n
    dist[start] = 0
    length = 0
    while q:
        v = q.popleft()
        length = max(length, dist[v])
        for nv in graph[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                q.append(nv)
            elif dist[nv] == dist[v]:
                print(-1)
                exit()
    return length + 1

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

print(ans)

Solution (Python):
def bfs(dp, arr, i,  visited):
	q = []
	q.append(i)
	visited[i] = True
	while q:
		i = q.pop(0)
		visited[i] = True
		for j in arr[i]:
			if dp[j] == -1:
				dp[j] = dp[i] + 1
			elif dp[i] == dp[j]:
				return -1
			
			if visited[j] == False:
				visited[j] = True
				q.append(j)
	return 0

n=int(input())
i=0
arr=[]
degree = [0]*n
while i<n:
	s=input()
	a=[]
	for j,e in enumerate(s):
		if e=='1':
			a.append(j)
			degree[i]+=1
	arr.append(a)	
	i+=1

res = -1
ans = -1
for i in range(n):
	dp = [-1]*n
	visited=[False for x in range(n)]
	dp[i] = 1
	res=bfs(dp, arr, i, visited)
	if res  == 0:
		ans = max(ans , max(dp))

print(ans)

Solution (Python):
def bfs(dp, arr, i,  visited):
	q = []
	q.append(i)
	visited[i] = True
	while q:
		i = q.pop(0)
		visited[i] = True
		for j in arr[i]:
			if dp[j] == -1:
				dp[j] = dp[i] + 1
			elif dp[i] == dp[j]:
				return -1
			
			if visited[j] == False:
				visited[j] = True
				q.append(j)
	return 0

n=int(input())
i=0
arr=[]
degree = [0]*n
while i<n:
	s=input()
	a=[]
	for j,e in enumerate(s):
		if e=='1':
			a.append(j)
			degree[i]+=1
	arr.append(a)	
	i+=1

res = -1
ans = -1
for i in range(n):
	dp = [-1]*n
	visited=[False for x in range(n)]
	dp[i] = 1
	res=bfs(dp, arr, i, visited)
	if res  == 0:
		ans = max(ans , max(dp))

print(ans)

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

lst = [0] * N
lst[0] = 1

stack = [0]
flag = True
while len(stack) != 0:
    tmp = stack.pop()
    for index, x in enumerate(S[tmp]):
        if x == 0:
            continue
        if lst[index] == 0:
            lst[index] = -lst[tmp]
            stack.append(index)
        else:
            if lst[tmp] == -lst[index]:
                pass
            else:
                flag = False
                break
    if not flag:
        print (-1)
        exit()

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

g = np.array(S)
anslst = floyd_warshall(g)
ans = int(np.max(anslst))

print (ans + 1)

Solution (Python):


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




lst = [0] * N
lst[0] = 1

stack = [0]
flag = True
while len(stack) != 0:
    tmp = stack.pop()
    for index, x in enumerate(S[tmp]):
        if x == 0:
            continue
        if lst[index] == 0:
            lst[index] = -lst[tmp]
            stack.append(index)
        else:
            if lst[tmp] == -lst[index]:
                pass
            else:
                flag = False
                break
    if not flag:
        print (-1)
        exit()

INF = 10 ** 9
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])
            
ans = 0
for i in range(N):
    for j in range(N):
        ans = max(S[i][j], ans)

print (ans + 1)

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

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

ans = -1

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

    tmp = 0
    stack = [i]
    visit = [False]*n
    visit[i] = True
    flag = True
    while True:
        li = []
        while stack:
            li2 = []
            l = stack.pop(-1)
            for j in edges[l]:
                li2.append(j)
            for j in li2:
                edges[j].remove(l)
            li += li2
        li = list(set(li))
        for j in li:
            if visit[j]:
                flag = False
        if flag:
            stack = li
            for j in li:
                visit[j] = True
            tmp += 1
        else:
            break
        if not stack:
            ans = max(ans,tmp)
            break

print(ans)

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

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

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

Solution (Python):
import sys
import copy

input = sys.stdin.readline

N = int(input())
OS = [[int(x) for x in list(input().strip())] for y in range(N)]

distmax = 0
for i in range(N):
	S = copy.deepcopy(OS)
	distlist = [-1]*N
	distlist[i] = 0
	queue = [i]
	dist = 0
	shortcut = False
	while len(queue)>0:
		dist += 1
		nq = []
		for ii in queue:
			for jj, neighbor in enumerate(S[ii]):
				if neighbor==1:
					if distlist[jj]==-1:
						distlist[jj] = dist
						S[jj][ii] = 0
						nq.append(jj)
					elif distlist[jj]!=dist:
						shortcut = True
						break
					else:
						S[jj][ii] = 0
			if shortcut: break
		if shortcut: break
		queue = nq
	dist -= 1
	if (not shortcut) and (dist>distmax):
		distmax = dist

if distmax==0:
	ans = -1
else:
	ans = distmax+1
print(ans)

Solution (Python):

from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [0] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = -cur_color
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if not color[u]:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [0] * (N + 1)  
    dist[start] = 1
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [0] * (N + 1)  
    dist[start] = 1
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


def is_bipartite() -> bool:
    stack = deque([(1, 1)])
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [-1] * (N + 1)  
    dist[start] = 0
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if dist[u] == -1:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1)) + 1
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):

def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = [start]
    dist = [-1] * (N + 1)  
    dist[start] = 0
    while que:
        v = que.pop(0)
        cur = dist[v]
        for u in E[v]:
            if dist[u] == -1:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1)) + 1
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [-1] * (N + 1)  
    dist[start] = 0
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if dist[u] == -1:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1)) + 1
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def bfs(n,e,fordfs):
    W = [-1]*n
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if nowv == W[ne]:
                return -1


            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return max(len)

N = int(input())
data = [list(map(int, list(input()))) for i in range(N)]
v = [[] for i in range(N)]
maxlen = [0]*N

for i in range(N):
    for j in range(N):
        if data[i][j] == 1:
            v[i].append(j)
for i in range(N):
    maxlen[i] = bfs(N,i,v)


ans = max(maxlen)+1
if ans==0:
    ans = -1

print(ans)

Solution (Python):

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)



def main():

    n = int(input())


    data = [list(map(int, list(input()))) for i in range(n)]
    fordfs = [[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if data[i][j] == 1:
                fordfs[i].append(j)


    def bfs():
        V = [-1]*n
        V[0] = 0
        que = deque()
        que.append(0)
        while que:
            now = que.popleft()
            nowv = V[now]
            for ne in fordfs[now]:
                if nowv == V[ne]:
                    print(-1)
                    exit()
                elif V[ne] == -1:
                    V[ne] = (nowv+1) % 2
                    que.append(ne)


    bfs()
    
    G = csgraph_from_dense(data)
    d = floyd_warshall(G)
    d.tolist()
    M = 0
    for i in d:
        M = max(M, max(i))
    M = int(M)
    print(M+1)
    return
if __name__ == '__main__':
    main()

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


def input(): return sys.stdin.readline()[:-1]

n = int(input())
data = [list(map(int, list(input()))) for i in range(n)]
fordfs = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if data[i][j] == 1:
            fordfs[i].append(j)

def bfs():
    V = [-1]*n
    V[0] = 0
    que = deque()
    que.append(0)
    while que:
        now = que.popleft()
        nowv = V[now]
        for ne in fordfs[now]:
            if nowv == V[ne]:
                print(-1)
                exit()
            elif V[ne] == -1:
                V[ne] = (nowv+1) % 2
                que.append(ne)

bfs()

G = csgraph_from_dense(data)
d = floyd_warshall(G)
d.tolist()
M = 0
for i in d:
    M = max(M, max(i))
M = int(M)
print(M+1)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
S = [list(map(int, input())) for i in range(N)]
G = [[float('inf')] * N for i in range(N)]

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


colors = [None] * N
stack = [(0, 1)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for i, cost in enumerate(G[n]):
        if cost == float('inf'):
            continue

        if colors[i] == colors[n]:
            print(-1)
            exit()
        else:
            if colors[i] is None:
                stack.append((i, color ^ 1))

for i in range(N):
    G[i][i] = float('inf')

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

for i in range(N):
    G[i][i] = 0

ans = max([max(g) for g in G])
print(ans + 1)

Solution (Python):

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
def solve():
    n=int(input())
    data=[list(map(int,list(input()))) for i in range(n)]
    fordfs=[[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if data[i][j]==1:
                fordfs[i].append(j)

    def dfs():
        V=[-1]*n
        V[0]=0
        que=deque()
        que.append(0)
        while que:
            now=que.popleft()
            nowv=V[now]
            for ne in fordfs[now]:
                if nowv==V[ne]:
                    print(-1)
                    exit()
                elif V[ne]==-1:
                    V[ne]=(nowv+1)%2
                    que.append(ne)
    
    dfs()
    
    G=csgraph_from_dense(data)
    d = floyd_warshall(G)
    d.tolist()
    M=0
    for i in d:
        M=max(M,max(i))
    M=int(M)
    print(M+1)
    return



def main():

    solve()
    return
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[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 is_bipartite()==0:
  print(-1)
  sys.exit()

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[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 is_bipartite()==0:
  print(-1)
  sys.exit()
 
 
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 or visitct!=n:
    ct+=1
    for i in range(len(next)):
      distance[next[i]]=ct
      visited[next[i]]=1
      visitct+=1
      for j in range(len(connection[next[i]])):
        if visited[connection[next[i]][j]]==-1:
          next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[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 is_bipartite()==0:
  print(-1)
  sys.exit()
 

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      distance[next[i]]=ct
      visited[next[i]]=1
      visitct+=1
      for j in range(len(connection[next[i]])):
        if visited[connection[next[i]][j]]==-1:
          next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
    
  return distance

ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[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 is_bipartite()==0:
  print(-1)
  sys.exit()
 
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=[]
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.append(connection[next[i]][j])
    next=next2
    next2=[]
    
  return distance
 
ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)