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):
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    f = 0
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        while que:
            v, c = que.popleft()
            if col[v] == -1:
                col[v] = c
            elif col[v] == c:
                continue
            else:
                f = 1
                break
            for ne in E[v]:
                if col[ne] == c:
                    f = 1
                    break
                if col[ne] < 0:
                    que.append([ne, 1-c])

            if f:
                break
        if f:
            break
    return 1-f

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(max([max(BFS(N, X, i)) for i in range(N)])+1)
else:
    print(-1)

Solution (Python):
N=int(input())
S=[[int(s) for s in input()] for i in range(N)]
c=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j]:
            c[i].append(j)
def bfs(p,g,d):
    r=0
    q=[]
    for e in p:
        if x[e]==g^1:
            return -1
        elif x[e]==-1:
            x[e]=g
            for f in c[e]:
                q.append(f)
    if len(q)==0:
        return d
    return bfs(q,g^1,d+1)
r=0
for i in range(N):
    x=[-1]*N
    d=bfs([i],0,0)
    if d==-1:
        break
    r=max(r,d)
print(r if d!=-1 else d)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    node_num = int(input())
    data = [list(map(int, list(input()))) for i in range(node_num)]

    graph_data = defaultdict(set)
    dist_data = [[200 for i in range(node_num)] for j in range(node_num)]
    for i in range(node_num):
        dist_data[i][i] = 0
        for j in range(node_num):
            if data[i][j]:
                dist_data[i][j] = 1
                graph_data[i].add(j)

    which_graph = [-1 for i in range(node_num)]
    now_set = set()
    next_set = set()
    now_set.add(0)
    which_graph[0] = 0
    flg = 0
    while len(now_set) > 0:
        for now_ele in now_set:
            for next_ele in graph_data[now_ele]:
                if which_graph[next_ele] == -1:
                    which_graph[next_ele] = 1 ^ which_graph[now_ele]
                    next_set.add(next_ele)
                else:
                    if which_graph[now_ele] ^ which_graph[next_ele] == 0:
                        flg = 1
                        break
        now_set = next_set
        next_set = set()


    if flg:
        print(-1)
        sys.exit()



    for k in range(node_num):
        for i in range(node_num):
            for j in range(node_num):
                dist_data[i][j] = min(dist_data[i][j], dist_data[i][k] + dist_data[k][j])

    ans = 0
    for i in range(node_num):
        ans = max(ans, max(dist_data[i]))

    print(ans + 1)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = []
for i in range(N):
  Ss = input()
  S.append(Ss)
E = [set() for i in range(N)]
D = [[100000]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
  for j in range(i+1, N):
    if S[i][j] == "1":
      
      E[i].add(j)
      E[j].add(i)
      D[i][j] = 1
      D[j][i] = 1
ok = True
V = [-1]*N
c = 0
V[0] = 0
q = [0]
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if V[n] == V[c]:
      ok = False
    if not V[n] < 0:
      continue
    V[n] = 1 if V[c] == 0 else 0
    q.append(n)
if not ok:
  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])

r = max([max(Ds) for Ds in D])+1
print(r)

Solution (Python):
import sys, collections

def dfs(i, c, col, edge):
    col[i] = c
    for next_node in edge[i]:
        if col[next_node] == c: return False
        if col[next_node] == 0 and dfs(next_node, -c, col, edge) == False: return False

    return True

def longest(i, edge, N):
    q = collections.deque()
    q.append((i, 1))
    dist = dict()
    ans = 1
    for j in range(N): dist[j] = -1
    flag = True
    while q:
        nn, nd = q.popleft()
        if dist[nn] == -1:
            ans = max(nd, ans)
            dist[nn] = nd
            for next_node in edge[nn]:
                if dist[next_node] == -1: q.append((next_node, nd + 1))
                elif abs(dist[next_node] - nd) != 1: flag = False
        elif dist[nn] != nd:
            ans = -1
            break
    
    return (ans if flag else -1)

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = 0
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    is_bipartite = dfs(0, 1, col, edge)
    if not is_bipartite: print(-1)
    else:
        ans = -1
        for i in range(N):
            ans = max(ans, longest(i, edge, N))
        print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys, collections

def dfs(i, c, col, edge):
    col[i] = c
    for next_node in edge[i]:
        if col[next_node] == c: return False
        if col[next_node] == 0 and dfs(next_node, -c, col, edge) == False: return False

    return True

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = 0
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    is_bipartite = dfs(0, 1, col, edge)
    if not is_bipartite: print(-1)
    else:
        INF = 10 ** 15
        dist = [[INF for j in range(N)] for i in range(N)]
        for i in range(N):
            for j in range(N):
                if i == j: dist[i][j] = 0
                elif j in edge[i]: 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])

        ans = -1
        for i in range(N):
            for j in range(N):
                if dist[i][j] < INF: ans = max(ans, dist[i][j])
        print(ans + 1)

    

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as wf
from collections import deque
input = sys.stdin.readline

def main():
    N = int(input())
    link = [[0 if c == "0" else 1 for c in list(input().strip())] for i in range(N)]
    
    check = [False] * N
    colors = [True] * N

    q = deque()
    q.append((0, True, 1))
    ok = True
    check[0] = True
    while len(q) > 0:
        i, color, step = q.popleft()
        
        for nex, c in enumerate(link[i]):
            if c == 1:
                if check[nex]:
                    if colors[nex] == color:
                        ok = False
                        break
                else:
                    check[nex] = True
                    colors[nex] = not(color)
                    q.append((nex, not(color), step+1))
        if not ok:
            break
    
    if ok:
        ans = 0
        link = wf(link)
        for i in range(N):
            ans = max(ans, int(max(link[i])))
        print(ans + 1)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque

INF = float('inf')


def bfs(n, es):
    parity = [-1] * n
    parity[0] = 0

    dq = deque()
    dq.append(0)
    while dq:
        v = dq.popleft()
        nxt_par = parity[v] ^ 1
        for u in es[v]:
            if parity[u] == -1:
                parity[u] = nxt_par
                dq.append(u)
            else:
                if parity[u] != nxt_par:
                    return False
                    
    return True
    


def warshall_floyd(n, g):
    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])
    return g


def solve():
    n = int(input())
    es = tuple(set() for _ in range(n))
    g = []
    for v in range(n):
        s = input()
        for u, is_adj in enumerate(map(int, s)):
            if is_adj:
                es[v].add(u)
                es[u].add(v)
        g.append(list(map(int, s)))
    for r, row in enumerate(g):
        for c, cell in enumerate(row):
            if cell == 0 and r != c:
                g[r][c] = INF
        
        
        
    
    

    
    bipartite = bfs(n, es)
    if not bipartite:
        return -1

    
    g = warshall_floyd(n, g)
    d = max(max(row) for row in g)
    return d + 1


if __name__ == '__main__':
    print(solve())

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


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n = I()
graph = SR(n)


def bfs(i):
    cost = [INF] * n
    cost[i] = 0
    que = deque([i])
    while que:
        cur = que.popleft()
        for nxt in range(n):
            if int(graph[cur][nxt]):
                c1 = cost[cur]
                if cost[nxt] != INF and cost[nxt] % 2 != (c1 + 1) % 2:
                    return -1
                else:
                    if cost[nxt] > c1 + 1:
                        cost[nxt] = c1 + 1
                        que += [nxt]
    return max(cost)



ret = 0
for j in range(n):
    if bfs(j) < 0:
        print(-1)
        break
    else:
        ret = max(ret, bfs(j))
else:
    print(ret + 1)

Solution (Python):
import collections

n = int(input())
s = []
for _ in range(n):
    ch = input()
    s.append([int(c) for c in ch])


def graph(i, n, s):
    flag = [-2 for _ in range(n)]
    flag[i] = 1
    que = collections.deque([i])
    while que:
        target = que.popleft()
        for j in range(n):
            if s[target][j] == 1:
                if flag[j] == -2:
                    flag[j] = flag[target] + 1
                    que.append(j)
                elif flag[j] != flag[target] + 1 and flag[j] != flag[target] - 1:
                    return [-1, -1]
    mf = max(flag)
    return [flag.index(mf), mf]


r1 = graph(0, n, s)
if r1[0] == -1:
    print(-1)
else:
    res = r1[1]
    for i in range(1, n):
        r = graph(i, n, s)
        res = max(res, r[1])
    print(res)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(list(map(int, input()[:-1])))

INF = float('inf')

def is_bipartite_graph():
    team = [0] * N
    valid = True
    q = deque()
    q.append(0)
    team[0] = 1
    while valid and len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if not team[v]:
                    team[v] = team[u]%2 + 1
                    q.append(v)
                else:
                    if (team[v] - team[u])%2 == 0:
                        valid = False
                        break
    return valid


def get_distances(s):
    q = deque()
    q.append(s)
    d = [INF] * N
    d[s] = 0
    while len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                    q.append(v)
    return d


def get_diameter():
    dmax = 0
    for i in range(N):
        d = get_distances(i)
        dmax = max(max(d), dmax)
    return dmax


if is_bipartite_graph():
    print(get_diameter()+1)
else:
    print(-1)

Solution (Python):
import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
sys.setrecursionlimit(10**7)


def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        T = []
        for i, e in enumerate(S):
            if e == 1:
                T.append(i)
        G.append(T)
    
    colors = [-1] * N
    visited = [False] * N
    def is_binarygraph(v, color):
        visited[v] = True
        for n in G[v]:
            if colors[n] == color:
                return False
            if visited[n]:
                continue
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, colors[n]):
                return False
        return True
    
    colors[0] = 0
    if not is_binarygraph(0, 0):
        return -1

    inf = 10**3
    d = [[inf]*N for _ in range(N)]
    for i in range(N):
        for j in G[i]:
            d[i][j] = 1
    for i in range(N):
        d[i][i] = 0
    
    fw = floyd_warshall(d)
    return np.max(fw) + 1

if __name__ == '__main__':
    print(int(main()))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def warshall_floyd(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

def solve():
    N = II()
    edge_list = {}
    
    for i in range(N):
        edge_list[i] = []
        ei = SI()
        for j, e in enumerate(ei):
            if e == '1':
                edge_list[i].append(j)

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

    
    from collections import deque
    qu = deque()
    qu.append((-1, 0)) 

    
    seen = set()
    is_bip = True


    while qu:
        parent_bip, n = qu.popleft()

        
        if parent_bip * bip[n] == 1:
            is_bip = False
            print(-1)
            return

        
        bip[n] = parent_bip * -1

        if n not in seen:
            for neib in edge_list[n]:
                qu.append((bip[n], neib))
        dprint('parent_bip:',parent_bip, 'n:', n, 'edge:', edge_list[n], 'q:', qu, seen)
        seen.add(n)

    dprint(bip)

    
    mx = N + 1
    d = [[mx for i in range(N)] for i in range(N)]
    for i in range(N):
        for e in edge_list[i]:
            d[i][e] = 1
        d[i][i] = 0
    d = warshall_floyd(d)

    ans = 0
    for i in range(N):
        for j in range(N):
            ans = max(ans, d[i][j])

    dprint(d)

    print(ans+1)

solve()

Solution (Python):
from collections import deque

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


memo = [-1] * n
memo[0] = 0
q = deque([(0, -1)])
while q:
    v, p = q.popleft()
    for nv in range(n):
        if s[v][nv] == '1':
            if nv == p:
                continue
            if memo[nv] == -1:
                memo[nv] = (memo[v] + 1) % 2
                q.append((nv, v))
            else:
                if memo[nv] == memo[v]:
                    print(-1)
                    exit()


INF = float('inf')
dp = [[1 if c == '1' else INF for c in row] for row in s]

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

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

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

print(dist+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)]


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):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N = int(input())
S = [input().strip() for _ in range(N)]

flg = False
max_cnt = 1
for sp, row in enumerate(S):
    
    C = [0]*N
    C[sp] = 1
    q = deque([])
    for i, v in enumerate(row):
        if v == '1':
            q.append(int(i))

    cnt = 1 
    c = -1 
    while q:
        for i in range(len(q)):
            np_ind = q.popleft()
            if C[np_ind] == -c:
                print(-1)
                exit()
            elif C[np_ind] == c:
                pass
            else:
                C[np_ind] = c
                for i, v in enumerate(S[np_ind]):
                    if v == '1' and C[i] == 0:
                        q.append(int(i))
        cnt += 1
        c *= -1
    if max_cnt < cnt:
        max_cnt = cnt

print(max_cnt)

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):
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 scipy.sparse.csgraph import floyd_warshall
import sys
sys.setrecursionlimit(10**8)

n=int(input())
arr=[input() for _ in range(n)]
g=[[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if arr[i][j]=='1':
      g[i].append(j)
g2=[[0]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g2[i][j]=int(arr[i][j])

colors=[0]*n

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

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

if is_bipartite()==False:
  print(-1)
  exit()

ans=0
d=floyd_warshall(g2)
for i in range(n):
  ans=max(ans,int(max(d[i])+1))
print(ans)

Solution (Python):
import queue
import numpy as np
n = int(input())
class Node:
    def __init__(self):
        self.nextNode = []
        self.checkNgo = -1
        self.group = -1
        
Nodes = [Node() for i in range(n)]
for i in range(n):
    s = input()
    for j in range(len(s)):
        if s[j] == '1':
            Nodes[i].nextNode.append(j)
            
def check(node,ngo):
    if node.checkNgo == -1:
        node.checkNgo = ngo
    elif node.checkNgo != ngo:
        return False
    elif node.checkNgo == ngo:
        return True
    for i in node.nextNode:
        if not check(Nodes[i],(ngo+1)%2):
            return False
    return True
    
def ngoCheck():
    stack = [Nodes[0]]
    Nodes[0].checkNgo = 0
    while stack:
        node = stack.pop()
        for i in node.nextNode:
            if Nodes[i].checkNgo != -1 and Nodes[i].checkNgo == node.checkNgo:
                return False
            if Nodes[i].checkNgo == -1:
                Nodes[i].checkNgo = (node.checkNgo+1)%2
                stack.append(Nodes[i])
    return True
    
if not check(Nodes[0],0):
    print(-1)
    exit(0)
    
def solv():
    d = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if j in Nodes[i].nextNode:
                d[i][j] = 1
            else:
                d[i][j] = np.inf
    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]
    return d
    
def saidai(d):
    maxi = 0
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            maxi = max(maxi,d[i][j])
    return maxi
    
d = solv()
print(saidai(d)+1)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((0, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == d:
        continue
    if dist[v] == -1:
        dist[v] = d
    else:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))

if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print(ans + 1)
else:
    print(-1)

Solution (Python):

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

import sys
import copy

ans = 0
adj_list = [[]for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if int(S[i][j]):
            adj_list[i].append(j)
            adj_list[j].append(i)


for kk in range(N):
    q = []
    visited = [False] * N
    cnt = 1
    visited[kk] = True
    q.append(kk)
    VC = 1
    while VC < N:
        nextv = copy.copy(q)
        q = []
        nextv = list(set(nextv))
        
        L = len(nextv)
        for i in range(L):
            if not(visited[nextv[i]]):
                visited[nextv[i]] = True
                VC += 1
            for j in range(i+1,L):
                if (int(S[nextv[i]][nextv[j]])):
                    print(-1)
                    sys.exit()
        
        for nv in nextv:
            for v in adj_list[nv]:
                if not(visited[v]):
                    q.append(v)
    
        cnt += 1
    
    ans = max(ans,cnt-1)
        

print(ans)

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
illegal=False
for i in range(N):
  if illegal:
    break
  
  node_list=[-1]*N
  
  d=1
  queue={i}
  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 collections import deque

def solve(init):
  groups = [-1 for i in range(N)]
  groups[init] = 1
  q = deque()
  q.append(init)
  while len(q) > 0:
    u = q.popleft()
    for v in range(N):
      if M[u][v] == 0:
        continue
      if groups[v] != -1:
        if groups[v] == groups[u]-1 or groups[v] == groups[u]+1:
          continue
        else:
          return -1
      groups[v] = groups[u] + 1
      q.append(v)
  return max(groups)


N = int(input())
M = [list(map(int, list(input()))) for i in range(N)]

res = -1
for u in range(N):
  res = max(res, solve(u))

print(res)

Solution (Python):
from collections import deque, defaultdict
from itertools import combinations
from itertools import product

def bipartite(V, E):
    '''
    Input:
    V = [0, 1, ..., N-1]: a list of vertices of the graph
    E: the adjacency list of the graph
    Output:
    If the graph is bipartite, return [(U_1, U_2) (the parts of the bipartite graph) for each component].
    Else, return None.
    '''
    color = {v: None for v in V}
    part = []
    for v in V:
        if color[v] is not None: continue
        stack = [(v, 0)] 
        parts = {0: [], 1: []}
        while stack:
            v, c = stack.pop()
            if color[v] is not None: 
                continue
            color[v] = c
            parts[c].append(v)
            for u in E[v].keys():
                if color[u] is None: 
                    stack.append((u, c^1)) 
                elif color[u] != c: 
                    continue
                else: 
                    return None
        part.append(parts)
    return part

def floyd_warshall(V, E):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
    Output:
        If there exists a negative cycle, return (None, prev), where prev is
        the table, whose (i, j)-element is the previous vertices in the shortest (i, j)-path
        Otherwise return (dist, prev), where dist is the table of the minimum cost
        between arbitrary vertex u, v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = {u: {v: INF for v in V} for u in V}
    prev = {u: {v: None for v in V} for u in V}
    for v in V:
        dist[v][v] = 0; prev[v][v] = -1
        for u, c in E[v].items(): dist[v][u] = c; prev[v][u] = v;
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                prev[i][j] = prev[k][j]
    for v in V:
        if dist[v][v] < 0: return None, prev
    return dist, prev

N = int(input())
V = list(range(N))
E = defaultdict(dict)
for u in range(N):
    for v, s in enumerate(input()):
        if s == '1': E[u][v] = 1
if bipartite(V, E) is None:
    print(-1)
else:
    dist, _ = floyd_warshall(V, E)
    diameter = -1
    for u, v in combinations(V, 2):
        diameter = max(diameter, dist[u][v])
    print(diameter + 1)

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)