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):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    dist = []
    for i in range(N):
        route = [int(i) for i in input()]
        for j in range(N):
            if route[j]:
                G[i].append(j)
            elif i != j:
                route[j] = INF
        dist.append(route)
    
    color = [-1]*N
    color[0] = 0
    stack = [0]
    possible = True
    while stack:
        p = stack.pop()
        for e in G[p]:
            if color[e] >= 0:
                if color[e] == color[p]:
                    possible = False
            else:
                color[e] = color[p]^1
                stack.append(e)
        if not possible:
            break
    
    if possible:
        ans = 0
        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])
        for i in range(N):
            for j in range(N):
                ans = max(ans,dist[i][j])
        print(ans + 1)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            return True
        else:
            return False

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

n = int(input())
wf = WarshallFloyd(n*2)
uf = UnionFind(n*2)
for i in range(n):
    s = input()
    for j in range(i):
        if s[j] == '1':
            wf.path(i,j,1)
            uf.unite(i,j+n)
            uf.unite(i+n,j)
for i in range(n):
    if uf.same(i,i+n):
        print(-1)
        exit(0)
d = wf.build()
ans = 0
for i in range(n):
    for dist in d[i][:i]:
        ans = max(ans,dist)
print(ans+1)

Solution (Python):
def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    v_count: 頂点数
    matrix: 隣接行列(到達不能はfloat("inf"))
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


n = int(input())
g = [[] for _ in range(n)]
m = [list(map(int, input())) for _ in range(n)]
for i, row in enumerate(m):
    for j, c in enumerate(row):
        if c == 1:
            g[i].append(j)
        elif i != j:
            m[i][j] = 10000000000
d = [-1] * n
d[0] = 0
s = [0]
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            s.append(node)
            d[node] = d[p] ^ 1
        elif d[node] == d[p]:
            print(-1)
            exit(0)
ans = 0
warshall_floyd(n, m)
for row in m:
    ans = max(ans, max(row))
print(ans + 1)

Solution (Python):
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self._size = [1 for _ in range(n)]
        self._edges = 0

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self._size[y] += self._size[x]
            self._edges += 1
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self._size[x] += self._size[y]
            self._edges += 1
    
    def size(self, x):
        x = self.find(x)
        return self._size[x]
    
    def trees(self):
        return self.n - self._edges

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

n = ni()
s = nsn(n)

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

def ok(n, dist):
    uf = UnionFind(2 * n)
    for i in range(n):
        for j in range(n):
            if s[i][j] == '1':
                uf.unite(i, j + n)
                uf.unite(i + n, j)
    for i in range(n):
        if uf.same(i, i + n):
            return False
    return True

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == '1':
            dist[i][j] = 1
    dist[i][i] = 0

floyd_warshall(n, dist)

if ok(n, dist):
    ans = 0
    for i in range(n):
        for j in range(n):
            if dist[i][j] != inf:
                ans = max(dist[i][j], ans)
    print(ans + 1)
else:
    print(-1)

Solution (Python):
N = int(input())
E = [[] for _ in range(N)]
for j in range(N):
	t = input()
	for i in range(N):
		if t[i] == '1':
			E[j].append(i)

ANS = -1
for start in range(N):		
	cnt = [0] * N
	cnt[start] = 1
	q = [start]
	cond = 0
	while q:
		cp = q.pop(0)
		if cp < 0:
			continue
		cnt[cp] *= -1

		for nep in E[cp]:
			if cnt[nep] < 0:
				continue
			elif cnt[nep] > 0:
				if cnt[nep] == cnt[cp] * (-1) + 1:
					continue
				else:
					cond = 1
					break
			else:
				cnt[nep] = cnt[cp] * (-1) + 1
				q.append(nep)
	
	if cond:
		continue

	ans = min(cnt) * (-1)
	ANS = max(ANS, ans)

print(ANS)

Solution (Python):
n = int(input())
T = []
graph = [[] for i in range(n)]
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == '1':
            graph[j].append(i)
color = [-1]*n
color[0] = 0
stack = [0]
flag = True
while len(stack) != 0:
    t = stack.pop()
    for i in range(len(graph[t])):
        cur = graph[t][i]
        if color[cur] == -1:
            if color[t] == 1:
                color[cur] = 0
            else:
                color[cur] = 1
            stack.append(cur)
        else:
            if color[t] != color[cur]:
                None
            else:
                flag = False
                break
    if not flag:
        break
ans = 0
if not flag:
    print(-1)
else:
    dist = [[10**5]*n for i in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for i in range(n):
        for j in range(len(graph[i])):
            dist[i][graph[i][j]] = 1
            dist[graph[i][j]][i] = 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])
    for i in range(n):
        for j in range(n):
            ans = max(ans, dist[i][j]+1)
    print(ans)

Solution (Python):
from collections import defaultdict, deque


def grouping(n, N, d):
    group = [-1]*(N+1)
    group[n] = 1

    q = deque([n])
    while q:
        s = q.popleft()
        for t in d[s]:
            if group[t]!=-1:continue
            group[t] = group[s] + 1
            q.append(t)

    for k, v in d.items():
        for j in v:
            if not abs(group[j]-group[k])==1:
                return False
    
    return group


def solve():
    N = int(input())
    d = defaultdict(list)
    for i in range(1, N+1):
        for j, s in enumerate(input(), start=1):
            if s=="1":
                d[i].append(j)
    

    ans = -1
    for i in range(1, N+1):
        res = grouping(i, N, d)
        if res != False:
            ans = max(ans, max(res))
    
    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
N=int(input())
S=[input() for i in range(N)]
l=[None]*N
ni=1
b=[0]
l[0]=False
while b:
    a=[]
    for i in b:
        for j in range(N):
            if S[i][j]=="1":
                if l[j]==None:
                    l[j]=not l[i]
                    a.append(j)
                else:
                    if l[j]==l[i]:
                        ni=0
    b=a
s=[[1000]*N for i in range(N)]
for i in range(N):
    s[i][i]=0
for i in range(N):
    for j in range(N):
        if S[i][j]=="1":
            s[i][j]=1
for i in range(N):
    for j in range(N):
        for k in range(N):
            s[j][k] = min(s[j][k],s[j][i] + s[i][k])
M=0
for i in s:
    M=max(M,max(i))
print(M+1 if ni else -1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = [list(map(int, list(input()))) for _ in range(N)]
graph = csr_matrix(S)
dist_matrix = floyd_warshall(graph, directed=False)
ans = np.array(dist_matrix, dtype=np.int64).max()+1

g = [[] for _ in range(N)]
for i in range(N):
	for j in range(N):
		if S[i][j]:
			g[i].append(j)

color = [0]*N
def f(v, c):
    color[v] = c
    for node in g[v]:
        if color[node] == c:
            return False
        elif color[node] == 0 and not f(node, -c):
            return False
    return True

k = 1
for i in range(N):
	if color[i] == 0 and not f(i, 1):
		k = -1
		break

if k == 1:
	print(ans)
else:
	print(-1)

Solution (Python):
from collections import deque
n = int(input())
s = [list(map(int, list(input()))) for _ in range(n)]
bord = [[] for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        if s[i][j]==1:
            bord[i].append(j)
            bord[j].append(i)

result = []
for i in range(n):
    ch = True
    visit = [-1 for _ in range(n)]
    visit[i] = 1
    q = deque([i])
    while q:
        x = q.popleft()
        for y in bord[x]:
            if visit[y]<0:
                visit[y] = visit[x]+1
                q.append(y)
            elif (visit[y] == visit[x]+1) or (visit[y]==visit[x]-1):
                continue
            else:
                ch = False
                break
    if ch:
        result.append(max(visit))
    else:
        result = [-1]
        break
print(max(result))

Solution (Python):
from collections import deque
n = int(input())
s = [list(map(int, list(input()))) for _ in range(n)]
bord = [[] for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        if s[i][j]==1:
            bord[i].append(j)
            bord[j].append(i)

result = []
for i in range(n):
    ch = True
    visit = [-1 for _ in range(n)]
    visit[i] = 1
    q = deque([i])
    while q:
        x = q.popleft()
        for y in bord[x]:
            if visit[y]<0:
                visit[y] = visit[x]+1
                q.append(y)
            elif (visit[y] == visit[x]+1) or (visit[y]==visit[x]-1):
                continue
            else:
                ch = False
                break
    if ch:
        result.append(max(visit))
    else:
        result = [-1]
        break
print(max(result))

Solution (Python):
N=int(input())
d=[[float("inf") for i in range(0,N)] for i in range(0,N)]
for i in range(0,N):
    S=input()
    for j in range(0,N):
        if S[j]=="1":
            d[i][j]=1

for k in range(0,N):
    for i in range(0,N):
        for j in range(0,N):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]

ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        ans=max(ans,d[i][j])
for i in range(1,N-1):
    for j in range(i+1,N):
        if d[i][j]==1 and d[0][i]==d[0][j]:
            ans=-2

print(ans+1)

Solution (Python):



from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      dq = deque()
      dq.append(0)
      colors[0] = 0
      while dq:
        inode = dq.popleft()
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(colors[inode]-1)
            dq.append(ichild)
          else:
            if colors[ichild] == colors[inode]:
              return False
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Solution (Python):
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n 
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [10**10]*n
    d[i] = 0
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '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])
for i in range(n):
    for j in range(n):
        maxdist = max(maxdist, dist[i][j])
print(maxdist+1)

Solution (Python):

import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**5]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


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

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys

from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]

    dist = [-1 for _ in range(N)]
    col = [0 for _ in range(N)]
    dist[0],col[0] = 0,1
    q = deque([(0,1)])
    D = 0
    while q:
        now,nc = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if col[fol] == 0:
                    col[fol] = -1*nc
                    q.append((fol,-1*nc))
                elif col[fol] == nc:
                    print(-1)
                    exit()

    def getmax(x):
        dist = [-1 for _ in range(N)]
        dist[x] = 1
        q = deque([x])
        while q:
            now = q.popleft()
            for i in range(N):
                if edge[now][i] == "1":
                    fol = i
                    if dist[fol] == -1:
                        dist[fol] = dist[now]+1
                        q.append(fol)
        return max(dist)
    
    print(max(getmax(i) for i in range(N)))
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

from collections import deque

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

def bfs(start):
    res = 0
    dist = [-1] * N
    dist[start] = 1
    q = deque()
    q.append([start, 1])
    st = set()
    st.add((start, 1))

    while q:
        i, d = q.popleft()
        if dist[i] == -1:
            dist[i] = d
            res = max(res, d)
        elif dist[i] != d:
            res = -1
            break
        for j in range(N):
            if S[i][j] == '1' and dist[j] != d-1:
                if (j, d+1) not in st:
                    q.append([j, d+1])
                    st.add((j, d+1))
    return res

ans = -1
for i in range(N):
    k = bfs(i)
    if k == -1:
        break
    else:
        ans = max(ans, k)

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

from collections import deque

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

def bfs(start):
    res = 0
    dist = [-1] * N
    dist[start] = 1
    q = deque()
    q.append([start, 1])
    st = set()
    st.add((start, 1))

    while q:
        i, d = q.popleft()
        if dist[i] == -1:
            dist[i] = d
            res = max(res, d)
        elif dist[i] != d:
            res = -1
            break
        for j in range(N):
            if S[i][j] == '1' and dist[j] != d-1:
                if (j, d+1) not in st:
                    q.append([j, d+1])
                    st.add((j, d+1))
    return res

ans = -1
for i in range(N):
    k = bfs(i)
    if k == -1:
        break
    else:
        ans = max(ans, k)

print(ans)

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

def dfs(v, color):
    colors[v] = color
    for to in g[v]:
        if colors[to] == color: return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def Washall_Floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

n = int(input())
g = [[] for _ in range(n)]
f_inf =float('inf')
dist = [[f_inf]*n for _ in range(n)]
for i in range(n): dist[i][i]=0

for i in range(n):
    S = input()
    for j in range(n):
        if S[j] == '1':
            g[i].append(j)
            dist[i][j] = 1
            dist[j][i] = 1

colors = [0] * n
ans = -1
if not dfs(0, 1):
    print(ans)
else:
    Washall_Floyd(dist)
    for d in dist:
      tmp = max(d)
      ans = max(tmp, ans)
    print(ans+1)

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

def dfs(v, color):
    colors[v] = color
    for to in g[v]:
        if colors[to] == color: return
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def Washall_Floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

n = int(input())
g = [[] for _ in range(n)]
f_inf =float('inf')
dist = [[f_inf]*n for _ in range(n)]
for i in range(n): dist[i][i]=0

for i in range(n):
    S = input()
    for j in range(n):
        if S[j] == '1':
            g[i].append(j)
            dist[i][j] = 1
            dist[j][i] = 1

colors = [0] * n
ans = -1
if not dfs(0, 1):
    print(ans)
else:
    Washall_Floyd(dist)
    for d in dist:
      tmp = max(d)
      ans = max(tmp, ans)
    print(ans+1)

Solution (Python):
"""
AtCoder Grand Contest 039  B - Graph Partition / 


（１）ある集合V_iに含まれるノードから伸びる辺について、その先の集合がV_i-1かV_i+1になるように分ける
（２）その時の集合の個数の最大値を求める

（１）を言い換えると、あるノードが偶数番の集合に属しているとき、それと繋がっているノードが奇数番号の集合かつ差が１である
　→二部グラフ
（２）V_1とV_kがあるとき、少なくともそれらはk本の辺をたどらなければ繋がれないはずなので、最も距離の長い辺（直径）を探す
"""

from collections import deque

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

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


q = deque()
q.append(0)
checked = [0] * N
checked[0] = 1
while q:
    curr = q.popleft()
    for nxt in es[curr]:
        
        if checked[nxt] == 0:
            checked[nxt] = checked[curr] * -1
            q.append(nxt)
        else:
            
            if checked[nxt] == checked[curr]:
                print(-1)
                exit()




ans = 0
for i in range(N):
    q = deque()
    q.append(i)
    dist = [0] * N
    
    dist[i] = 1
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[nxt] == 0:
                dist[nxt] = dist[curr] + 1
                q.append(nxt)

    ans = max(ans, max(dist))

print(ans)

Solution (Python):
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n):
    p=list(str(input()))
    for j in range(n):
        if p[j]=='1':
            g[i].append(j)
q=deque([0])
v=[-1]*n
v[0]=0
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
        else:
            if v[i]!=1-v[p]:
                print(-1)
                exit()
ans=0
for s in range(n):
    q=deque([s])
    v=[0]*n
    v[s]=1
    while q:
        p=q.popleft()
        for i in g[p]:
            if v[i]==0:
                v[i]=1+v[p]
                q.append(i)
    ans=max(ans,max(v))
print(ans)

Solution (Python):
class Graph(): 
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append(e[1] - 1)
            self.graph[e[1] - 1].append(e[0] - 1)

    def is_bipartite(self):
        group = [None for _ in range(self.n)]
        stack = [(0, 1)]
        while stack:
            node, nodecolor = stack.pop()
            group[node] = nodecolor
            for adj in self.graph[node]:
                if group[adj] == nodecolor:
                    return False
                if group[adj] is None:
                    adjcolor = 1 - nodecolor
                    stack.append((adj, adjcolor))
        return True

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j in self.graph[i]:
                dist[i][j] = 1
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist

    def diam(self):
        res = 0
        dist = self.warshall_floyd()
        for i in range(self.n):
            for j in range(self.n):
                res = max(res, dist[i][j] + 1)
        return res

N = int(input())
E = []

for i in range(N - 1):
    S = list(map(int,input()))
    for j in range(i + 1, N):
        if S[j]:
            E.append((i + 1, j + 1))

G = Graph(N, E)

if G.is_bipartite():
    print(G.diam())

else:
    print(-1)

Solution (Python):
import scipy.sparse.csgraph as s
def b(u,x):c[u]=x;return all(d[u][v]^1or(c[u]!=c[v])&(c[v]or b(v,-x))for v in X)
N,*S=open(0)
N=int(N)
X=range(N)
d=[[i^j and(S[i][j]=='1'or N)for j in X]for i in X]
c=[0]*N
print(int(b(0,1)and s.floyd_warshall(d).max()+2)-1)

Solution (Python):
def b(u,x):
 c[u]=x
 return all((c[u]!=c[v])&(c[v]or b(v,-x))for v in X if d[u][v]==1)
N=int(input())
X=range(N)
S=[input()for _ in X]
d=[[1 if S[i][j]=='1'else(N if i^j else 0)for j in X]for i in X]
for k in X:
 for i in X:
  for j in X:d[i][j]=min(d[i][j],d[i][k]+d[k][j])
c=[0]*N
print(max(max(e)for e in d)+1 if b(0,1)else-1)

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

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

def is_bipartite(u):
    for v in range(N):
        if u == v or dist[u][v] != 1:
            continue
        if color[v] == -1:
            color[v] = 1 - color[u]
            if not is_bipartite(v):
                return False
        elif color[u] == color[v]:
            return False
    return True

N = int(input())
S = [input().rstrip() for _ in range(N)]
dist = [[1 if S[i][j] == '1' else (0 if i == j else float('inf')) for j in range(N)] for i in range(N)]
color = [-1] * N
color[0] = 0
ans = 0
if is_bipartite(0):
    floyd_warshall(dist)
    ans = max(max(d) for d in dist) + 1
else:
    ans = -1
print(ans)

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

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N = int(input())
S = [input().rstrip() for _ in range(N)]
uf = UnionFind(N)
for i in range(N):
    for j in range(i):
        if S[i][j] == '1':
            uf.unite(i, j)
depth = defaultdict(int)
for i in range(N):
    color = [-1] * N
    queue = deque()
    queue.append((i, 1))
    color[i] = 0
    max_d = 1
    while queue:
        j, d = queue.popleft()
        max_d = max(max_d, d)
        for k in range(N):
            if k == j or S[j][k] == '0':
                continue
            if color[k] == -1:
                color[k] = 1 - color[j]
                queue.append((k, d+1))
            elif color[k] == color[j]:
                print(-1)
                exit()
    depth[uf.find(i)] = max(depth[uf.find(i)], max_d)
ans = sum(depth[i] for i in range(N))
print(ans)

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

read = sys.stdin.read
readline = sys.stdin.readline

N = int(readline())
S = np.array([list(i) for i in read().split()], np.int64)
edges = np.where(S == 1)


graph = [[] for _ in range(N)]

for i, j in zip(edges[0].tolist(), edges[1].tolist()):
    graph[i].append(j)
    graph[j].append(i)


def judge(start):
    colors = [-1] * N
    colors[start] = 0
    queue = deque([(start, 0)])
    while queue:
        V, c = queue.popleft()
        c ^= 1
        for v in graph[V]:
            if colors[v] == -1:
                colors[v] = c
                queue.append((v, c))
            else:
                if colors[v] != c:
                    return False
    return True


start = edges[0][0]
if judge(start):
    d = floyd_warshall(S)
    print(int(np.max(d)) + 1)
else:
    print(-1)

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

read = sys.stdin.read
readline = sys.stdin.readline

N = int(readline())
S = np.array([list(i) for i in read().split()], np.int64)
edges = np.where(S == 1)


graph = [[] for _ in range(N)]
start = None
for i, j in zip(edges[0].tolist(), edges[1].tolist()):
    graph[i].append(j)
    graph[j].append(i)
    start = i


def judge(start):
    colors = [-1] * N
    colors[start] = 0
    queue = deque([(start, 0)])
    while queue:
        V, c = queue.popleft()
        c ^= 1
        for v in graph[V]:
            if colors[v] == -1:
                colors[v] = c
                queue.append((v, c))
            else:
                if colors[v] != c:
                    return False
    return True


if judge(start):
    d = floyd_warshall(S)
    print(int(np.max(d)) + 1)
else:
    print(-1)