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
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def dfs(graph: list, node: int, start: int) -> list:
    
    INF = float("inf")
    dist = [INF] * node

    
    dist[start] = 0
    stack = [(0, start)]

    while stack:
        cost, cur_node = stack.pop()

        
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node], nex_node))

    return dist

def judge(graph, edges):
    node = len(graph)
    start = 0

    dist = dfs(graph, len(graph), 0)

    for i, j in edges:
        if abs(dist[i]-dist[j])%2 == 0:
            return False

    return True

import numpy as np

n = ni()
grid = [lc() for _ in range(n)]
graph = [[] for _ in range(n)]
numgraph = np.zeros((n, n))
edges = []
for row, si in enumerate(grid):
    for col, sij in enumerate(si):
        if sij == "1":
            edges.append((row, col))
            graph[row].append((1, col))
            numgraph[row][col] = 1


is_nibu = judge(graph, edges)

if is_nibu:
    from scipy.sparse.csgraph import floyd_warshall
    dists = floyd_warshall(numgraph)
    ans = 0
    for i in range(n):
        ans = max(ans, max(dists[i,:]))

    print(int(ans) + 1)

else:
    print(-1)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def is_bipartite():
    return dfs(0,1)

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

n = I()
S = [input() for _ in range(n)]
dist = [[inf]*n for _ in range(n)]
colors = [0]*n
es = [[] for _ in range(n)]
for i in range(n):
    s = S[i]
    for j in range(i+1,n):
        if s[j] == '1':
            dist[i][j] = 1
            dist[j][i] = 1
            es[i].append(j)
            es[j].append(i)

for i in range(n):
    dist[i][i] = 0
d = warshall_floyd(dist)
flg = is_bipartite()
if not flg:
    print(-1)
    quit()
ans = 0
for i in range(n):
    ans = max(ans,max(d[i]))
print(ans+1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n=int(input())
l=[list(input()) for i in range(n)]
colors = [0 for i in range(n)]
es=[[] for i in range(n)]
Edges=es
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      es[i].append(j)
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()


def bfs(v):
    Visited=[False]*n
    q=deque()
    q.append((v,0))
    Visited[v]=True
    ret=(v,0)
    while q:
        fr,dist=q.popleft()
        if ret[1]<dist:
            ret=(fr,dist)
        for to in Edges[fr]:
            if not Visited[to]:
                Visited[to]=True
                q.append((to,dist+1))
    return ret

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

Solution (Python):
from collections import deque

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

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

def solve(a):
    rank = [-1] * N
    rank[a] = 0

    Q = deque([a])
    while Q:
        v = Q.popleft()
        r = rank[v]
        for u in E[v]:

            if rank[u] == -1:
                rank[u] = r + 1
                Q.append(u)

            elif rank[u] == r:
                return -2

    return max(rank)


print(max(solve(i) for i in range(N)) + 1)

Solution (Python):

import sys
INF = float("inf")
from collections import deque

import sys
import math
from collections import defaultdict, deque
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]
        pass

    def add_edge(self, from_, to_):
        """必ず0インデックスで入力すること。
        """
        self.E[from_].append((to_, 1))
        pass


def solve(N: int, S: "List[str]"):

    g = Graph(N)
    for i, s in enumerate(S):
        for j, c in enumerate(s):
            if c == "1":
                g.add_edge(i, j)

    ddd = -1
    for node in range(N):
        depth = [-2]*N
        q = deque()
        q.append((node, 1))
        while len(q) > 0:
            node, d = q.popleft()
            if depth[node] != -2:
                continue
            depth[node] = d
            for i, w in g.E[node]:
                if depth[i] == -2:
                    q.append((i, d+1))
                elif d == depth[i]:
                    print(-1)
                    return
        ddd = max(ddd, d)
    print(ddd)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = [next(tokens) for _ in range(N)]  
    solve(N, S)


if __name__ == '__main__':
    main()

Solution (Python):
def f1(l1):
    ret = []
    for i in l1:
      for n,j in enumerate(li[i]):
        if j:
            if n in used or n in l1:
                return False
            elif n not in tree[nest-1] and n not in ret:
                ret.append(n)
    return ret


N = int(input())
li = []
for _ in range(N):
    li.append(list(map(int,list(input()))))
    
max_nest = 0
for i in range(N):
    tree = [[]]
    used = []
    tree.append([i])
    nest = 1
    while True:
        ret = f1(tree[nest])
        nest += 1
        if ret == False:
            break
        elif ret != []:
            tree.append(ret)
            used.extend(tree[nest-2])
        else:
            if max_nest < nest:
                max_nest = nest
            break
        
print(max_nest-1)

Solution (Python):
n = int(input())
connect_matrix = [ list(input()) for i in range(n) ]

def bfs(x):
    node_set = [ None for i in range(n)]
    color_list = [ "White" for i in range(n) ]
    search_list = [x]
    d = 0
    node_set[x] = 0
    color_list[x] = "Black"
    ans = 0
    while search_list != []:
        d += 1
        new_search_list = []
        for i in search_list:
            for j, v in enumerate(connect_matrix[i]):
                if v == "1":
                    if color_list[j] == "White":
                        if node_set[j] is None:
                            node_set[j] = node_set[i] + 1

                        new_search_list.append(j)
                        color_list[j] = "Black"
                    else:
                        if (node_set[j] + node_set[i]) % 2 == 0:
                            ans = -1
        search_list = new_search_list
    return ans, d-1

judge_list = []
dist_list = []
for i in range(n):
    a = bfs(i)
    judge_list.append(a[0])
    dist_list.append(a[1])

if -1 in judge_list:
    print(-1)
else:
    print(max(dist_list)+1)

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

M = [set(y for y in range(N) if S[x][y]) for x in range(N)]
v_max = -1
for i in range(N):
  V = [set([i])]
  nodes = set(range(N)) - V[0]
  while len(nodes) > 0:
    V.append(set().union(*[M[x] for x in V[-1]]).intersection(nodes))
    for v in V[-1]:
      if V[-1] & M[v]:
        break
    else:
      nodes -= V[-1]
      continue
    break
  else:
    v_max = max(v_max, len(V))
print(v_max)

Solution (Python):
n=int(input())
gg=[input() for _ in [0]*n]
graph=[[] for _ in [0]*n]


inf=10**10
dist=[[inf for _ in [0]*n] for _ in [0]*n]

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


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

        

if flag==False:
    print(-1)
else:
    for k in range(n):
        for i in range(n):
            for j in range(n):dist[i][j]=min(dist[i][j],(dist[i][k]+dist[k][j]))
    print(max([max([i for i in j]) for j in dist])+1)

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

n = int(input())
s = list()
for i in range(n):
    s.append([int(x) for x in list(input())])
s=np.array(s)
d=floyd_warshall(csr_matrix(s))
c=d[:, np.argmax(d)%n]
for i in range(n):
    for j in range(i+1, n):
        if (s[i, j] == 1) and abs(c[i] - c[j]) != 1:
            print(-1)
            exit()
r=int(np.amax(d)+1)
print(r)

Solution (Python):
from collections import deque

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

def bfs(s, start):
    plan = deque([(start, 0)])
    lengths = {}
    while len(plan) > 0:
        vertex, length = plan.popleft()
        if vertex in lengths:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1 and i not in lengths])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)

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

graph=[]
for i in range(N):
  graph.append([])

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

max_set=-1
for i in range(N):
  node_list=[-1]*N
  
  d=1
  queue={i}
  illegal=False
  while(True):
    new_queue=set()
    for q in queue:
      node_list[q]=d
      for qq in graph[q]:
        if node_list[qq]==-1:
          new_queue.add(qq)
        elif node_list[qq]!=d-1:
          illegal=True
          break
      
    if illegal:
      break
    elif len(new_queue)==0:
      
      max_set=max(max_set,d)
      break
    else:
      
      queue=new_queue
      d+=1
      
print(max_set)

Solution (Python):
from scipy.sparse.csgraph import dijkstra as di
from collections import deque

def dfs(graph, start, n):
    queue = deque()
    tmp = []
    visited = [0] * n
    queue.append(start)
    visited[start] = 1

    while queue:
        a = queue.popleft()
        for j in range(n):
            if not graph[a][j]:
                continue
            elif graph[a][j] and not visited[j]:
                queue.append(j)
                visited[j] = visited[a] + 1
            elif graph[a][j] and visited[j]:
                if abs(visited[a] - visited[j]) != 1:
                    
                    return False
    return True

n = int(input())
ad_lst = [list(map(int, input())) for _ in range(n)]
p_route = di(ad_lst)
ans = 0
mx = [0,0]
for i in range(n):
    for j in range(n):
        if p_route[mx[0]][mx[1]] < p_route[i][j]:
            mx = [i,j]
print(int(p_route[mx[0]][mx[1]] + 1) if dfs(ad_lst, mx[0], n) else -1)

Solution (Python):
from collections import deque
n=int(input())
graph=[[False for j in range(n)] for i in range(n)]
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            graph[i][j]=True
L=0
def bfs(i):
    longest=0
    global dist
    dist=[-1]*n
    dist[i]=0
    D=deque([i])
    while D:
        v=D.popleft()
        for j in range(n):
            if graph[v][j]==False:continue
            if dist[j]!=-1:
                if abs(dist[v]-dist[j])==1:continue
                else:return -1
            else:
                D.append(j)
                dist[j]=dist[v]+1
                if dist[j]>longest:longest=dist[j]
    return longest
for i in range(n):
    A=bfs(i)
    
    if A==-1:print(-1);exit()
    if A>L:L=A
print(L+1)

Solution (Python):
n=int(input())
t=[[]for i in range(n)]
for i in range(n):
    c=input()
    for j in range(n):
        if c[j]=="1":
            t[i].append(j)
def f(x):
    a=[-1]*n
    a[x],q=1,[[x,1]]
    while q:
        b,c=q.pop(0)
        for i in t[b]:
            if a[i]!=-1:
                if abs(a[i]-c)!=1:
                    return -1
                    break
            else:
                a[i]=c+1
                q.append([i,c+1])
    return max(a)
print(max([f(i)for i in range(n)]))

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7



show_flg=False


inf=float('inf')
n=I()
s=[[inf]*n for _ in range(n)]
g=[[] for i in range(n)]
for r in range(n):
    ri=list(input())
    for c in range(n):
        if ri[c]=='1':
            s[r][c]=1
            g[r].append(c)  

def wf(d):
    n=len(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

d=wf(s)
diam=-1
bg=0
ed=n-1
for r in range(n):
    for i,dist in enumerate(d[r]):
        if i==r:
            continue
        if diam<dist:
            diam=dist
            bg=r
            ed=i

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return

bfs(bg)

for i in range(n):
    for nb in g[i]:
        if abs(v[nb]-v[i])!=1:
            print(-1)
            exit()
            

print(diam+1)
exit()
'''
show(s)
show(wf(s))
show(diam,bg,ed)
show(v)
'''

Solution (Python):
import sys
from collections import deque

n = int(input())
nex = [[] for _ in range(n)]
d = [[1000]*n for _ in range(n)]
for i in range(n):
    ni = list(sys.stdin.readline().rstrip())
    for j in range(n):
        if ni[j] == '1':
            nex[i].append(j)
            d[i][j] = 1
        elif i == j:
            d[i][j] =0
        else:
            d[i][j] = 1000000

maxi = 0
maxii = 0
vr = [set() for _ in range(n)]
nexcache = deque()
di = 1
dil = [-1] * n
dil[0] = 0
vr[0].add(0)
for i in range(len(nex[0])):
        vr[nex[0][i]].add(1)
        vr[nex[0][i]].add(-1)
        nexcache.append(nex[0][i])
        maxi = 1
        maxii = nex[0][i]
        dil[nex[0][i]] = 1
error = False
while len(nexcache) > 0:
    nnx = []
    for ne in nexcache:
        couho = set()
        for i in vr[ne]:
            couho.add(i+1)
            couho.add(i-1)
        for i in nex[ne]:
            if dil[i] == -1:
                vr[i] = vr[i].union(couho)
                nnx.append(i)
                dil[i] = di+1
                if maxi < di+1:
                    maxi = di+1
                    maxii = i
            else:
                if dil[i] != di-1 and dil[i] != di+1:
                    error = True
                    break
        if error:
            break
    di+=1
    nexcache = nnx

if error:
    print(-1)
    exit()

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

result = 0
for i in range(n):
    for j in range(i):
        if d[i][j] > result:
            result = d[i][j]

print(result+1)

Solution (Python):
from collections import deque
N = int(input())
S = [list(input()) for _ in range(N)]


def bfs(i):

    d = [-1 for _ in range(N)]
    d[i] = 0

    que = deque([(i, 0, -1)])

    finished = set()
    while que:
        ci, dist, p = que.popleft()
        

        for j in range(N):
            if S[ci][j] == '1':
                if j != p and d[j] >= 0:
                    if d[j] == dist or (d[j] != dist+1 and j not in finished):
                        
                        return -1
                elif d[j] == -1:
                    d[j] = dist+1
                    que.append((j, dist+1, ci))
        finished.add(ci)

    return dist+1


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

print(ans)

Solution (Python):
import collections

def read():
    N = int(input().strip())
    S = list()
    for i in range(N):
        has_nodes = list(input().strip())
        s = list()
        for i, has_node in enumerate(has_nodes):
            if has_node == '1':
                s.append(i)
        S.append(s)
    return N, S

def bfs(start, V, graph):
    q = collections.deque()
    q.appendleft(start)
    depth = [-1] * V
    depth[start] = 0
    while len(q) > 0:
        s = q.pop()
        for t in graph[s]:
            if depth[t] == -1:
                depth[t] = depth[s] + 1
                q.appendleft(t)
    return depth

def argsort(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)

def make_groups(V, depth):
    max_depth = max(depth)
    groups = dict()
    for v in range(V):
        d = depth[v]
        if d in groups.keys():
            groups[d].append(v)
        else:
            groups[d] = [v]
    return groups

def has_edge_in_sibling_nodes(V, graph, depth):
    for i in range(V):
        for j in range(i+1, V):
            if depth[i] == depth[j]:
                if j in graph[i]:
                    return True
    return False


def solve(N, S):
    
    max_depth = -1
    for i in range(N):
        depth = bfs(i, N, S)
        if not has_edge_in_sibling_nodes(N, S, depth):
            max_depth = max(max_depth, max(depth) + 1)
    return max_depth

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Solution (Python):
N=int(input())
S=[input() for _ in range(N)]
min_v=200
for i in range(N):
  v=S[i].count('1')
  if v<min_v:
    min_v=v
start_candidates=[]
for i in range(N):
  start_candidates.append(i)
ans_lst=[]
for start in start_candidates:
  visited=[False for _ in range(N)]
  visited[start]=True
  current=[start]
  ans=1
  while True:
    flag=True
    candidates=[]
    for i in current:
      for j in range(N):
        if not visited[j] and S[i][j]=='1':
          candidates.append(j)
          visited[j]=True
    if not candidates:
      break
    
    for a in candidates:
      for b in candidates:
        if S[a][b]=='1':
          ans=-1
          flag=False
          break
      if not flag:
        break
    if not flag:
      break
    
    ans+=1
    current=candidates
  ans_lst.append(ans)
print(max(ans_lst))

Solution (Python):
import copy
def main():
    n = int(input())
    s = [list(map(int,list((input())))) for i in range(n)]
    k = []
    f = True
    for start in range(n):
        s_ = copy.deepcopy(s)
        group = [0]*n
        group[start] = 1
        v = [start]
        searched = set([start])
        mx_k = 2
        f = True
        while True:
            v_ = []
            for i in v:
                edge = s_[i]
                for j in range(n):
                    if edge[j] == 1:
                        if group[j] == 0:
                            v_.append(j)
                            group[j] = mx_k
                        elif not abs(group[j]-group[i])==1:
                            f = False
                            break
                searched = searched | set(v)
                if not f:
                    break
            if not f:
                break
            if len(searched) == n:
                k.append(mx_k-1)
                break
            v = copy.deepcopy(v_)
            mx_k += 1
    if k:
        print(max(k))
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

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

N = int(input())
graph = [[int(a) for a in list(input().rstrip())] for _ in range(N)]
INF = 10**9

dis = copy.deepcopy(graph)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if dis[i][j] == 0:
            dis[i][j] = INF

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

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

D = [INF for _ in range(N)]
checked = [False for _ in range(N)]
D[0] = 0
checked[0] = True
ok = True

def dfs(p, d, ok):
    for np in state[p]:
        if checked[np]:
            c = d + 1 - D[np]
            if c > 1 and c % 2 == 1:
                ok = False
        else:
            checked[np] = True
            D[np] = d+1
            ok = dfs(np, d+1, ok)
    return ok

ok = dfs(0, 0, ok)

if not ok:
    print(-1)
else:
    ans = 0
    for i in range(N):
        for j in range(N):
            ans = max(ans, dis[i][j]+1)
    print(ans)

Solution (Python):
N = int(input())
dist = []
neighbours = [[] for i in range(N)]
for i in range(N):
    line = list(input())
    dist.append([1 if c == '1' else float('inf') for c in line ])
    for j, char in enumerate(line):
        if char == '1': neighbours[i].append(j)

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][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

startVertex = 0
startDiam = 0
for i in range(N):
    for j in range(N):
        if dist[i][j] > startDiam:
            startDiam = dist[i][j]
            startVertex = i
            
isPossible = True


distances = [float('inf') for i in range(N)]
visited = [False for i in range(N)]

distances[startVertex] = 0

while True:
    curNode = min(range(N), key=lambda n:(visited[n], distances[n]))

    if visited[curNode]:
        break
    visited[curNode] = True

    for neighbour in neighbours[curNode]:
        if distances[neighbour] == float('inf'):
            distances[neighbour] = distances[curNode] + 1
        else:
            if abs(distances[neighbour] - distances[curNode]) != 1:
                isPossible = False

if not isPossible:
    print(-1)
else:
    total = len(set(distances))
    print(total)

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



ans=0
for i in range(1,n+1):
    bubun=[[] for iii in range(n+1)]
    bubun[0].append(i)
    check=0
    for j in range(n):
        for k in bubun[j]:
            for y in edge[k]:
                if y in bubun[j-1]:
                    continue
                elif y in bubun[j]:
                    break
                elif y in bubun[j+1]:
                    continue
                else:
                    bubun[j+1].append(y)
            else:
                continue
            break
        else:
            continue
        break
    else:
        for ii in bubun:
            if ii:
                check+=1
        ans=max(ans,check)
if ans==0:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import deque
N = int(input())
G = {i:[] for i in range(N)}
for i in range(N):
    S = input().strip()
    for j in range(N):
        if S[j]=="1":
            G[i].append(j)
cmax = 0
for i in range(N):
    hist = [0 for _ in range(N)]
    hist[i]=1
    num = 0
    heap = deque([(i,1)])
    ind = 0
    while ind==0 and num<N:
        cur = heap.popleft()
        num += 1
        y = cur[0]
        g = cur[1]
        cmax = max(cmax,g)
        for x in G[y]:
            if hist[x]==0:
                heap.append((x,g+1))
                hist[x]=g+1
            elif hist[x]==hist[y]:
                ind = 1
                break
    if ind==1:break
if ind==1:
    print(-1)
else:
    print(cmax)

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

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

from collections import deque

ans_tmp = 0
possible = True
for home in range(N):
    iswhite = [None] * N
    q = deque([(home, False, 0)])
    iswhite[home] = False
    while len(q) > 0:
        src, white, depth = q.popleft()
        
        if depth > ans_tmp:
            
            ans_tmp = depth
        
        for dst in graph[src]:
            
            if iswhite[dst] == None:
                white_dst = (white != True)
                q.append((dst, white_dst, depth + 1))
                iswhite[dst] = white_dst
            elif white == iswhite[dst]:
                possible = False
                break
            else:
                continue
        
        if possible == False:
            break
    
if possible:
    print(ans_tmp + 1)
else:
    
    print(-1)

Solution (Python):
from collections import deque

class UnionFind:
    def __init__(self, n):
        self.rank = [0]*n
        self.parent = [i for i in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def merge(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
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            self.rank[y] += 1

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



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

min_i = 0
min_count = n + 1
for i in range(n):
    count = 0
    for j in range(n):
        if s[i][j]:
            count += 1
    if count < min_count:
        min_count = count
        min_i = i

uf = UnionFind(n)

INF = 1001001001
ans = 0

for min_i in range(n):
    dist = [INF] * n
    dist[min_i] = 0
    q = deque([(min_i, 0, -1)])

    while q:
        v, d, p = q.popleft()
        box = []
        for nv in range(n):
            if s[v][nv] == '1':
                if nv == p:
                    continue
                if uf.same(v, nv):
                    print(-1)
                    exit()
                if d + 1 < dist[nv]:
                    dist[nv] = d + 1
                    q.append((nv, d + 1, v))
                    box.append(nv)
        for i in range(len(box) - 1):
            uf.merge(box[i], box[i + 1])
    ans = max(ans, max(dist) + 1)

print(ans)

Solution (Python):
N = int(input())
S = [list(map(int, list(input()))) for _ in range(N)]
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    if S[i][j] == 0:
      S[i][j] = float("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])

"""
g = [[0] * N for _ in range(2 * N)]
ig = [0] * N
order = [i for i in range(N)]
order.sort(key = lambda x: -max(S[x]))
g[N][order[0]] = 1
ig[order[0]] = N
"""
color = [0] * N
def dfs(v, c):
  global color
  color[v] = c
  for i in range(N):
    if S[v][i] == 1:
      if color[i] == c:
        return False
      if color[i] == 0 and not (dfs(i, -c)):
        return False
  return True

if dfs(1, 1):
  res = 0
  for r in S:
    res = max(max(r), res)
  print(res + 1)
else:
  print(-1)

Solution (Python):

def acinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))
    

def search(x):
    global g,N,nodenum
    queue=[(x,1)]
    wnum=2
    nodenum=[-1]*N
    nodenum[x]=1
    visited=[0]*N
    while True:
        nqueue=[]
        for node,k in queue:
            for snode in g[node]:
                if nodenum[snode]<0:                    
                    nodenum[snode]=wnum
                    nqueue.append((snode,wnum))
                else:
                    if (not visited[snode]) and nodenum[snode]!=wnum:
                        return -1
            visited[node]=1

        queue=nqueue
        if len(queue)==0:
            return wnum-1
        wnum+=1
        
        

N=int(input())

g=[[] for i in range(N)]
for i in range(N):
    s=list(input())
    for j in range(len(s)):
        if s[j]=="1":
            g[i].append(j)

res=-1
for i in range(N):
    res=max(res,search(i))

print(res)