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 collections


class Graph:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.edges = [[] for _ in range(n_nodes)]

    def add_edge(self, s, t):
        self.edges[s].append(t)
        self.edges[t].append(s)


n = int(input())
graph = Graph(n)
for i in range(n):
    s = input().rstrip()
    for j in range(i + 1, n):
        if s[j] == '1':
            graph.add_edge(i, j)


def check(node):
    for new_node in graph.edges[node]:
        if orders[new_node] == -1:
            q.append(new_node)
            orders[new_node] = orders[node] + 1
        elif abs(orders[new_node] - orders[node]) != 1:
            return False
    return True


res = []
for i in range(n):
    orders = [-1] * n
    q = collections.deque()
    q.append(i)
    orders[i] = 1
    while q:
        node = q.popleft()
        ok = check(node)
        if not ok:
            break
    else:
        res.append(max(orders))
if len(res) == 0:
    print(-1)
else:
    print(max(res))

Solution (Python):
n = int(input())
s = []
for i in range(n):
    s.append(list(input()))
flag = True
num = [True] * n
num[0] = "e"
check_list = [1]
while check_list:
    check = check_list.pop(0)
    for i in range(n):
        if s[check - 1][i] == "1":
            if num[check - 1] == "e":
                if num[i] == "e":
                    flag = False
                    break
                elif num[i] == "o":
                    pass
                else:
                    num[i] = "o"
                    check_list.append(i + 1)
            else:
                if num[i] == "o":
                    flag = False
                    break
                elif num[i] == "e":
                    pass
                else:
                    num[i] = "e"
                    check_list.append(i + 1)
    if flag == False:
        break
if flag == False:
    print(-1)
else:
    step_list = []
    for i in range(n):
        num = [True] * n
        step = 0
        check_list = [[i + 1]]
        num[i] = False
        while check_list != [[]]:
            check_list2 = check_list.pop(0)
            new_check_list = []
            for j in check_list2:
                for k in range(n):
                    if s[j - 1][k] == "1":
                        if num[k] == True:
                            num[k] = False
                            new_check_list.append(k + 1)
            check_list.append(new_check_list)
            step += 1
        step_list.append(step)
    print(max(step_list))

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

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










ans_max = 0

for fp in range(N):
    ans = 0
    d = deque()
    d.append(fp)
    used_array = [-1] * N
    value_array = [-1] * N
    used_array[fp] = 1
    value_array[fp] = 1
    while len(d):
        p = d.popleft()
        v = value_array[p]
        
        for i, s in enumerate(S_array[p]):
            if s == 0:
                continue
            if used_array[i] == -1:
                used_array[i] = 1
                value_array[i] = v + 1
                ans = max(ans, v + 1)
                d.append(i)
            else:
                if value_array[i] != v - 1 and value_array[i] != v + 1:
                    print(-1)
                    exit()
    ans_max = max(ans, ans_max)

print(ans_max)

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
G = [None] * N
for i in range(N):
    G[i] = list(map(int, input()))

nodes = [[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j]:
            nodes[i].append(j)
            nodes[j].append(i)

def bfs(start):
    visited = list2d(N, N, 0)
    group = [-1] * N
    que = deque()
    que.append((start, 1))
    mx = 0
    while que:
        u, cnt = que.popleft()
        if group[u] == -1:
            group[u] = cnt
        elif group[u] == cnt:
            continue
        else:
            return -1
        mx = max(mx, cnt)
        for v in nodes[u]:
            if visited[u][v]:
                continue
            visited[u][v] = visited[v][u] = 1
            que.append((v, cnt+1))
    return mx

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

Solution (Python):
from collections import defaultdict
n = int(input())
neighbors = defaultdict(list)
for i in range(n):
    s = list(map(int, list(input())))
    for j in range(n):
        if s[j] == 1:
            neighbors[i].append(j)

def dfs(v0):
    dist = {}
    dist[v0] = 0
    visited = {}
    f = [v0]
    while len(visited) != n:
        nxt_f = []
        for v in f:
            for nn in neighbors[v]:
                if nn in visited:
                    continue
                if nn in dist:
                    if dist[nn] != dist[v] + 1:
                        
                        return False
                else:
                    dist[nn] = dist[v] + 1
                    nxt_f.append(nn)
        for v in f:
            visited[v] = True
        f = nxt_f
    return max(dist.values()) + 1

kmax = -1
for v0 in range(n):
    k = dfs(v0)
    if k:
        kmax = max(kmax, k)
print(kmax)

Solution (Python):
N = int(input())

dist = [[1 if s == '1' else float('inf') for s in input()] for _ in range(N)]

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

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

baseMod = [d % 2 for d in dist[0]]

for i in range(N):
    A = [0] * N
    for j, d in enumerate(dist[i]):
        A[j] = (d + baseMod[i]) % 2
    if A != baseMod:
        print(-1)
        exit()

ans = max([max(D) for D in dist]) + 1
print(ans)

Solution (Python):
from collections import deque

N = int(input())

minDist = [[1 if s == '1' else float('inf') for s in input()] for _ in range(N)]

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

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

base = [d % 2 for d in minDist[0]]

for i in range(N):
    A = [0] * N
    for j, d in enumerate(minDist[i]):
        A[j] = (d + base[i]) % 2
    if A != base:
        print(-1)
        exit()

ans = max([max(D) for D in minDist]) + 1
print(ans)

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

from collections import deque

G = [[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if field[i][j] == "1":
            if j not in G[i]:
                G[i].append(j)
            if i not in G[j]:
                G[j].append(i)

ans = 0

for i in range(N):
    category = [-1] * N
    category[i] = 0
    q = deque([i])
    while len(q) > 0:
        a = q.popleft()
        Vs = G[a]
        c = category[a]
        
        for u in Vs: 
            if category[u] == -1:
                q.append(u)
                category[u] = c+1
            elif category[u] == c:
                print(-1)
                exit()
    ans = max(ans, len(set(category)))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[[int(s) for s in input()] for _ in range(n)]
    B=[a[:] for a in A]
    from itertools import product
    
    for i,j in product(range(n),repeat=2):
        if i==j: continue
        if B[i][j]==0: B[i][j]=INF
    
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])
    
    dia=0; p=0
    for i,j in product(range(n),repeat=2):
        if dia<B[i][j]:
            dia=B[i][j]
            p=i
    for i,j in product(range(n),repeat=2):
        if i>=j: continue 
        if A[i][j]:
            if abs(B[i][p]-B[j][p])!=1:
                print(-1)
                return
    print(dia+1)
resolve()

Solution (Python):
from queue import Queue


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


    def bfs(s):
        WHITE = 0
        GRAY = 1
        BLACK = 2

        color = [WHITE] * n
        d = [-1] * n
        q = Queue()
        q.put(s)
        color[s] = GRAY
        d[s] = 0
        while not q.empty():
            u = q.get()
            color[u] = BLACK
            for v, edge in enumerate(S[u]):
                if edge and color[v] == BLACK and d[v] + 1 != d[u]:
                    return -1
                if edge and color[v] == WHITE:
                    q.put(v)
                    color[v] = GRAY
                    d[v] = d[u] + 1

        return max(d) + 1

    cnt = -1
    for i in range(n):
        cnt = max(cnt, bfs(i))

    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):



def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]


n = int(input())

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


res = -1
for start in range(n):
	par = [-1]*n
	used = [False]*n
	used[start] = True

	tank = set()
	new = {start}
	judge = True

	while len(new) != 0 and judge:
		tank = set()
		for e in new:
			for go in edge[e]:
				if not used[go]:
					if same(e,go):
						judge = False
					else:
						tank.add(go)
		for e in new:
			used[e] = True
		if len(tank) >= 1:
			qqq = list(tank)[0]
			for e in tank:
				unite(e,qqq)
		new = tank

	if judge:
		cnt = 0
		for e in par:
			if e < 0:
				cnt += 1
		res = max(cnt,res)
print(res)

Solution (Python):
N = int(input())
graph = []
for _ in range(N):
	graph.append(list(map(int, input().strip())))

def check(graph):
	queue = [0]
	dists = [None] * N
	dists[0] = 0
	while queue:
		cur = queue.pop()
		dist = dists[cur] + 1
		col = graph[cur]
		for i in range(N):
			c = col[i]
			if c == 1:
				d = dists[i]
				if d == None:
					dists[i] = dist
					queue.append(i)
				else:
					if d % 2 != dist %2:
						return False
					elif d > dist:
						dists[i] = dist
						queue.append(i)
	return True

def search(graph, start):
	queue = [start]
	dists = [None] * N
	dists[start] = 0
	while queue:
		cur = queue.pop()
		dist = dists[cur] + 1
		col = graph[cur]
		for i in range(N):
			c = col[i]
			if c == 1:
				d = dists[i]
				if d == None or d > dist:
					dists[i] = dist
					queue.append(i)
	return max(dists)

if check(graph):
	diam = 0
	for i in range(N):
		d = search(graph, i)
		if d > diam:
			diam = d
	print(diam + 1)
else:
	print(-1)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import*
n=int(input())
con=[[]for _ in range(n)]
col=[-1]*n
G=[]
for i in range(n):
	x=input()
	for j,c in enumerate(x):
		if c=="1":
			con[i].append(j)
			con[j].append(i)
	G.append([c=="1" or float("inf") for c in x])
q=[0]
col[0]=0
while q:
	cur=q.pop(0)
	for nxt in con[cur]:
		if col[nxt]==col[cur]:
			print(-1)
			exit()
		if col[nxt]<0:
			col[nxt]=1-col[cur]
			q.append(nxt)
print(int(np.amax(floyd_warshall(G,0)+1)))

Solution (Python):


N = int(input())
g = [[] for i in [0]*(N+1)]

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

def max_len(g,v):
    visited = [False]*(N+1)
    l = 1
    ls = [v]
    pre_v = []
    while(ls):
        new_ls = []
        for cv in ls:
            for nv in g[cv]:
                if visited[nv] and not nv in pre_v:
                    return -1
                if not visited[nv] and not nv in new_ls:
                    new_ls.append(nv)
            visited[cv] = True
        if new_ls:
            l += 1
        pre_v = ls
        ls = new_ls
    return l

m = -1 
for i in range(1,N+1):
    m = max(m,max_len(g,i))
print(m)

Solution (Python):
from collections import deque
N = int(input())
S = [input() for _ in range(N)]
S = [[int(S[i][j]) for j in range(N)] for i in range(N)]
m = N
i = -1
for j in range(N):
    if sum(S[j]) < m:
        i = j
        m = sum(S[j])

ans = -1
for i in range(N):
    nodes = [-1]*N
    nodes[i] = 0
    q = deque([])

    for j in range(N):
        if i == j:
            continue
        if S[i][j] == 1:
            nodes[j] = 1
            q.append(j)

    pos = True
    while q:
        i = q.popleft()
        for j in range(N):
            if S[i][j] == 1:
                if nodes[j] == -1:
                    nodes[j] = nodes[i]+1
                    q.append(j)
                elif abs(nodes[i]-nodes[j]) != 1:
                    pos = False
                    break
        if not pos:
            break
    if pos:
        ans = max(max(nodes)+1,ans)

print(ans)

Solution (Python):
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 check(vSt):
    vs = set([vSt])
    useds = [False] * (N)
    useds[vSt] = True
    depth = 0
    while vs:

        v2s = set()
        for v in vs:
            for v2 in adjL[v]:
                if not useds[v2]:
                    v2s.add(v2)
                    useds[v2] = True
        for u in v2s:
            for v in v2s:
                if Sss[u][v] == '1':
                    return -1
        vs = v2s
        depth += 1
    return depth

ans = -1
for v in range(N):
    ret = check(v)
    if ret != -1:
        ans = max(ans, ret)

print(ans)

Solution (Python):
N=int(input())
S=[input() for i in range(N)]
G=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j]=="1":
            G[i].append(j)
q=[0]
dist=[-1 for i in range(N)]
dist[0]=0
while(q):
    r=q.pop()
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=1-dist[r]
            q.append(p)
for i in range(N):
    for j in G[i]:
        if dist[i]==dist[j]:
            print(-1)
            exit()


d=[[10**9 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in G[i]:
        d[i][j]=1
    d[i][i]=0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
ans=2
for i in range(N):
    for j in range(N):
        ans=max(ans,d[i][j]+1)
print(ans)

Solution (Python):
n=int(input())
b=[[]for _ in range(n)]
d=[]
inf=float('inf')
inf=float('inf')
for i in range(n):
  s=input()
  c=[]
  for j in range(n):
    if s[j]=="1":
      b[i]+=[(i,j)]
    c.append(1 if s[j]=="1" else inf)
  d.append(c)
def warshall_floyd(d):
    for i in range(n):d[i][i]=0
    
    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
d=warshall_floyd(d)
x=[-1]*n
x[0]=0
Q=b[0]
while Q:
  p=[]
  for i,j in Q:
    if x[j]<0:
      x[j]=x[i]^1
      p+=b[j]
    elif x[i]==x[j]:print(-1);exit()
  Q=p
z=0
for i in d:
  for j in i:
    if j!=float("inf"):z=max(j,z)
print(z+1)

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

R = {}
for i in range(N):
  R[i] = []
  for j in range(N):
    if S[i][j] == "1":
      R[i].append(j)

def dfs(x):
  L = [0] * N
  L[x] = 1
  S = [x]
  K = [0] * N
  cnt = 0
  while S:
    cnt += 1
    T = [0] * N
    ST = []
    while S:
      t = S.pop()
      T[t] = 1
      for i in R[t]:
        if L[i] == 1:
          if K[i] == 0:
            return -1
          else:
            L[i] = 1
        else:
          L[i] = 1
          K[i] = 1
          ST.append(i)
    S = ST
    K = T
  return cnt

ma = -1
for i in range(N):
  ma = max(ma, dfs(i))

print(ma)

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

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

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

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

max_num = 0
for root in range(N):
	group = [-1]*N
	group[root] = 0
	group_n = [root]
	num = 1
	judge = 0
	while len(group_n) > 0:
		group_next = []
		for node in group_n:
			for node_next in graph[node]:
				if group[node_next] == -1:
					group[node_next] = num
					group_next.append(node_next)
				elif group[node_next] == num - 1:
					judge = 1
					break
			if judge == 1:
				break
		if judge == 1:
			break
		else:
			num += 1
			group_n = copy.deepcopy(group_next)
	if judge == 0:
		max_num = max(max_num, num)

if max_num > 0:
	print(max_num - 1)
else:
	print(-1)

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

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

"""
・二部グラフが必要
・最長の最短距離 + 1 で上からbound
・2部グラフならbfs木が満たすのでよい
"""

N = int(readline())
S = np.frombuffer(read(),'S1').reshape(N,-1)[:,:N].astype(np.int64)

graph = csgraph_from_dense(S)

dist_mat = floyd_warshall(graph).astype(np.int32)

max_d = dist_mat.max()


A = np.where(dist_mat[0]%2 == 0)
B = np.where(dist_mat[0]%2 == 1)
bl = (S[A][:,A] == 0).all() and (S[B][:,B] == 0).all()

answer = max_d + 1 if bl else -1
print(answer)

Solution (Python):



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


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 



n = int(input())


dist = [None for i in range(n)]
INF = float("inf")

g = [[] for i in range(n)]

for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == "1":
            g[i].append(j)
    dist[i] = [1 if j == "1" else INF for j in s]

for i in range(n):
    dist[i][i] = 0


from collections import deque
def bfs(g,root):
        
    q = deque()
    memo = [-1]*(len(g))
    """初期化、キューに入れて訪問済みにする"""
    memo[root] = 0
    q.append(root)
    """BFS"""
    while q: 
        v = q.popleft() 
        for c in g[v]:
            if memo[c] >= 0:
                if memo[c] ==  memo[v] ^ 1:
                    continue
                else:
                    return False
            memo[c] = memo[v] ^ 1
            q.append(c)
    return True

if bfs(g,0):
    
    Floyd_Warshall(dist)
    
    ans = 0
    for i in range(n):
        for j in range(n):
            ans = max(ans,dist[i][j])
    print(ans+1)
            

else:
    print(-1)

Solution (Python):
from collections import deque

N = int(input())

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

ans = 0
for i in range(N):
    que = deque()
    que.append(i)
    seen = [0] * N
    seen[i] = 1
    while que:
        v = que.pop()
        for u in adj[v]:
            if seen[u] == 0:
                que.appendleft(u)
                seen[u] = -seen[v] - 1 if seen[v] > 0 else -seen[v] + 1
            else:
                if seen[v] * seen[u] > 0:
                    print(-1)
                    exit()
    ans_i = max(max(seen), -min(seen))
    ans = max(ans, ans_i)
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    s = S()
    k = I()
    n = len(s)
    for i in range(n):
        if s[i] != s[0]:
            break
    else:
        print((k*n)>>1)
        return
    s += s
    t = s[i-1]
    for j in range(n)[::-1]:
        if s[j] != t:
            break
    s = s[i:j+1]
    ans = (i>>1)+((n-1-j)>>1)+((n-1-j+i)>>1)*(k-1)
    i = 0
    n = len(s)
    while i < n:
        t = s[i]
        l = 0
        while i < n and t == s[i]:
            i += 1
            l += 1
        ans += (l >> 1)*k
    print(ans)
    return


def B():
    n = I()
    s = [list(map(int, input())) for i in range(n)]
    v = [[] for i in range(n)]
    for i in range(n):
        for j  in range(i+1,n):
            if s[i][j]:
                v[i].append(j)
                v[j].append(i)
    bfs = [-1]*n
    q = deque([0])
    q[0] = 0
    f = 1
    while f and q:
        x = q.popleft()
        nb = 1-bfs[x]
        for y in v[x]:
            if bfs[y] >= 0:
                if bfs[y] != nb:
                    f = 0
                    break
            else:
                bfs[y] = nb
                q.append(y)
    if not f:
        print(-1)
        return
    ans = -1
    for i in range(n):
        bfs = [0]*n
        bfs[i] = 1
        q.append(i)
        while q:
            x = q.popleft()
            nb = bfs[x]+1
            for y in v[x]:
                if not bfs[y]:
                    bfs[y] = nb
                    q.append(y)
        m = max(bfs)
        if m > ans:
            ans = m
    print(ans)
    return


def C():

    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    B()

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

E = [[] for _ in [0]*N]
for i,row in enumerate(S):
    for j,s in enumerate(row):
        if s :
            E[i].append(j)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

ans = -1
for i in range(N):
    d = dist_bfs(N,E,i)
    ans = max(ans,max(d)+1)

for i,e in enumerate(E):
    for j in e:
        if j > i : break
        if abs(d[i] - d[j]) != 1 : ans = -1
print(ans)

Solution (Python):
N = int(input())

E = []
es = [[] for _ in range(N)]
for j in range(N):
    s = input()
    e = []
    for i, c in enumerate(s):
        e.append(1 if c=="1" else float("inf"))
        if c=="1":
            es[i].append(j)
    E.append(e)




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


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

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

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

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

ans = 0
for e in E:
    ans = max(ans, max(e))
print(ans+1)

Solution (Python):
N = int(input())
e_list = [[] for i in range(N)]
for i in range(N):
    S = input()
    for j in range(i+1,N):
        if S[j]=="1":
            e_list[i].append(j)
            e_list[j].append(i)

from collections import deque

ans = -1
for vi in range(N):
    flag = True
    Q = deque([vi])
    min_path_list = [10**27]*N 
    min_path_list[vi] = 0
    max_path = 0
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if min_path_list[v1]==10**27:
                Q.appendleft(v1)
                min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) 
                max_path = max(max_path,min_path_list[v1])
            elif min_path_list[v1]!=min_path_list[v]+1 and min_path_list[v1]!=min_path_list[v]-1:
                flag=False
                break
    if flag:
        ans = max(max_path,ans)

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

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



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

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

def bfs(pt,v):
    used = [[False]*N for _ in range(N)]
    d = [-1]*N
    d[v] = 0
    q = [v]
    c = 1
    while q:
        flag = False
        q1 = []
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    used[i][j] = True
                    used[j][i] = True
                    flag = True
                    d[j] = c
                    q1.append(j)
                else:
                    if used[i][j]==False and d[j]!=c:
                        return -float('inf')
                    else:
                        if used[i][j]==False and d[j]==c:
                            used[i][j] = True
                            used[j][i] = True
        q = q1
        if flag:
            c += 1
    return c

ans = -1
for i in range(N):
    x = bfs(pt,i)
    if x>ans:
        ans = x

print(ans)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

N = int(sys.stdin.readline())
S = [sys.stdin.readline().rstrip() for _ in range(N)]

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


def count(v1):
    
    groups = [INF] * N
    groups[v1] = 0

    vs = [v1]
    g = 0
    while vs:
        nexts = set()
        for v in vs:
            nexts |= graph[v]
        vs = set()
        for u in nexts:
            if groups[u] not in [g - 1, INF]:
                return -1
            if groups[u] == INF:
                groups[u] = g + 1
                vs.add(u)
        g += 1
    return g




ans = -1
for v1 in range(N):
    ans = max(ans, count(v1))
print(ans)