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



Sample input:
2
01
10


Sample output:
2

Submission status: Accepted

Solution code:
n=int(input())
G=[""]+["x"+input() for s in range(n)]
V=[0 for i in range(n+1)] 

V[1]=1
que=[1]
head=0
while len(que)>head:
    now=que[head]
    head+=1
    nexr=G[now]
    for i in range(1,n+1):
        if nexr[i]=="1" and V[i]==0:
            V[i]=V[now]+1
            que.append(i)

flg=True
for i in range(1,n):
    for q in range(i+1,n+1):
        if G[i][q]=="1" and abs(V[i]-V[q])!=1:
            flg=False

if flg:
    ans=0
    for sta in range(1,n+1):
        V=[0 for i in range(n+1)] 
        V[sta]=1
        que=[sta]
        head=0
        while len(que)>head:
            now=que[head]
            head+=1
            nexr=G[now]
            for i in range(1,n+1):
                if nexr[i]=="1" and V[i]==0:
                    V[i]=V[now]+1
                    que.append(i)
        ans=max(max(V),ans)
    print(ans)
        
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def judge(g):
    n = len(g)
    bi = [-1] * n
    bi[0] = 0
    for cn in range(n):
        for i, row in enumerate(g):
            for j, column in enumerate(row):
                if column == "1":
                    if bi[i] == -1 and bi[j] == -1:
                        pass
                    elif bi[i] == -1:
                        bi[i] = bi[j] ^ 1
                    elif bi[j] == -1:
                        bi[j] = bi[i] ^ 1
                    else:
                        if bi[i] == bi[j]:
                            print(-1)
                            sys.exit()




def solve():
    n = getN()
    g = []
    for i in range(n):
        g.append([c for c in getS()])

    judge(g)

    costs = [[INF for i in range(n)] for j in range(n)]
    for i in range(n):
        costs[i][i] = 0

    for i, row in enumerate(g):
        for j, column in enumerate(row):
            if column == "1":
                costs[i][j] = 1

    V = n
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if costs[i][k] != INF and costs[k][j] != INF:
                    costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

    ans = max([max(x) for x in costs])
    print(ans + 1)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
from itertools import count
def max_dist(adj,v):

    q = [v]
    visited = [False]*len(adj)
    visited[v] = True
    last = None
    for d in count():
        if not q:
            return d,last
        nq = []
        last = q[0]
        for v in q:
            for u in adj[v]:
                if not visited[u]:
                    visited[u] = True
                    nq.append(u)
        q = nq


def solve(S):

    N = len(S)

    adj = [[] for _ in range(N)]
    for i,l in enumerate(S):
        for j,f in enumerate(l):
            if f:
                adj[i].append(j)

    stack = [0]
    color = [None]*N
    color[0] = True

    while stack:
        v = stack.pop()
        nc = not color[v]
        for u in adj[v]:
            if color[u] is None:
                color[u] = nc
                stack.append(u)
            elif color[u] != nc:
                return -1

    return max(max_dist(adj,v)[0] for v in range(N))

if __name__ == '__main__':
    N = int(input())
    S = [[c=='1' for c in input()] for _ in range(N)]
    print(solve(S))

Submission status: Accepted

Solution code:
from collections import*
n=int(input())
s=[input() for _ in range(n)]
e=[[]for _ in range(n)]
INF=10**18
for i,x in enumerate(s):
  for j,y in enumerate(x):
    if y=='1':e[i]+=[j]
ans=0
for i in range(n):
  d=[INF]*n
  q=deque([i])
  d[i]=1
  while q:
    now=q.popleft()
    for to in e[now]:
      if d[to]==INF:
        q+=[to]
        d[to]=d[now]+1
      elif d[to]!=d[now]+1 and d[to]!=d[now]-1:
        print(-1)
        exit()
  ans=max(max(d),ans)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8

def check_merge(merged,S):
    merged = np.array(merged)
    check = S[merged][:, merged]
    if check.sum():
        return False
    return True

def run():
    N = int(sysread())
    S = []
    for i in range(N):
        S.append(list(map(int, list(input()))))
    S = np.array(S, dtype=np.int8)

    ans = 0

    #for s in S:
    #    print(s)
    for k in range(N):
        #print(k, '-------------------')
        seen = set()
        seen.add(k)
        merged = [k]
        count = 0
        while merged:
            #print(merged)
            count += 1
            nexts = []
            for i in merged:
                for j, e in enumerate(S[i]):
                    if int(e) and not j in seen:
                        nexts.append(j)
                        seen.add(j)
            if not check_merge(merged, S):
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
N = int(input())
S = [input() for i in range(N)]

es = [[] for _ in range(N)]
for i,row in enumerate(S):
    for j,c in enumerate(row):
        if c=='1':
            es[i].append(j)
            es[j].append(i)

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

if not is_bipartite():
    print(-1)
    exit()

dist = [[N]*N for _ in range(N)]
for i,row in enumerate(S):
    for j,c in enumerate(row):
        if i==j:
            dist[i][j] = 0
        elif c=='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])

print(max(max(row) for row in dist) + 1)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    n = int(readline())
    s = [input() for _ in range(n)]
    ans = 0
    que = deque()

    for i in range(n):
        dist = [-1] * n
        dist[i] = 0
        que.append((i, 0))
        while que:
            cur, d = que.popleft()
            adj = s[cur]
            for nx, is_connected in enumerate(adj):
                if is_connected == "1":
                    if dist[nx] == -1:
                        dist[nx] = d + 1
                        que.append((nx, d + 1))
                    else:
                        if dist[nx] % 2 != (d + 1) % 2:
                            return print(-1)
            ans = max(ans, max(dist) + 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse
n = int(input())
s = np.array([list(map(int, list(input()))) for i in range(n)])
d = scipy.sparse.csgraph.floyd_warshall(scipy.sparse.csr_matrix(s))
l = d[:, np.argmax(d) % n]
for i in range(n):
    for j in range(i + 1, n):
        if s[i, j] == 1 and abs(l[i] - l[j]) != 1:
            exit(print(-1))
print(int(np.amax(d) + 1))

Submission status: Accepted

Solution code:
n=int(input())
s=[[0]*n for _ in range(n)]
for i in range(n):
	r=input()
	for j in range(n):
		if r[j]=="1":
			s[i][j]=1
ans=0
from collections import deque
for i in range(n):
	queue=deque([i])
	num=[-1]*n
	num[i]=0
	while queue:
		r=queue.popleft()
		for j in range(n):
			if s[r][j]==1 and num[j]==-1:
				num[j]=num[r]+1
				queue.append(j)
	MAX=max(num)
	p=[[]for _ in range(MAX+1)]
	for i in range(n):
		p[num[i]].append(i)
	ok=1
	for i in range(MAX+1):
		for x in p[i]:
			for y in p[i]:
				if s[x][y]==1:
					ok=0
					break
			if ok==0:
				break
		if ok==0:
			break
	if ok:
		ans=max(ans,MAX+1)
print(ans if ans else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge):

    search = [-1] * N
    search[v0] = 1
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        now_color = search[v]
        for nv in edge[v]:
            if search[nv] == -1:
                q.append(nv)
                search[nv] = now_color + 1
            elif search[nv] == now_color:
                return None

    return max(search)


def main():

    N = in_n()

    edge = [[] for _ in range(N)]
    for i in range(N):
        edge[i] = [j for j, n in enumerate(readline()) if n == ord('1')]

    ans = -1
    for i in range(N):
        color = bfs(N, i, edge)
        if color:
            ans = max(ans, color)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

#https://note.nkmk.me/python-union-find/

'''class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())'''

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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,w = map(int,input().split()) #n:頂点数　w:辺の数
n=I()

w=0
d = [[float("inf")]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
mat=[[] for i in range(n)]
for i in range(n):
    s=list(SI())
    for j in range(n):
        if int(s[j])==1:
            w+=1
            d[i][j]=1
            d[j][i]=1
            mat[i].append(j)
            #mat[j].append(i)
col=[0 for i in range(n)]
#print(mat)

col[0]=1
def dfs(x):
    for y in mat[x]:
        if col[y]==0:
            col[y]=(-1)*col[x]
            dfs(y)
        elif col[y]!=col[x]*(-1):
            print(-1)
            exit()
dfs(0)
#print(col)

        
'''nodes=[0 for i in range(2*n)]
uf=UnionFind(2*n)
for i in range(n):
    for j in range(i,n):
        if d[i][j]==1:
            uf.union(i,n+j)
            uf.union(j,n+i)
for i in range(n):
    if uf.same(i,i+n):
        print(-1)
        sys.exit()'''
warshall_floyd(d)
#print(d)
ans=0
for i in range(n):
    for j in range(n):
        if d[i][j]<inf and d[i][j]>ans:
            ans=d[i][j]
print(ans+1)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

#https://note.nkmk.me/python-union-find/

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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,w = map(int,input().split()) #n:頂点数　w:辺の数
n=I()

w=0
d = [[float("inf")]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for i in range(n):
    s=list(SI())
    for j in range(n):
        if int(s[j])==1:
            w+=1
            d[i][j]=1
            d[j][i]=1
    
nodes=[0 for i in range(2*n)]
uf=UnionFind(2*n)
for i in range(n):
    for j in range(i,n):
        if d[i][j]==1:
            uf.union(i,n+j)
            uf.union(j,n+i)
for i in range(n):
    if uf.same(i,i+n):
        print(-1)
        sys.exit()
warshall_floyd(d)
#print(d)
ans=0
for i in range(n):
    for j in range(n):
        if d[i][j]<inf and d[i][j]>ans:
            ans=d[i][j]
print(ans+1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

# 各頂点からBFSで距離を求める、同じ距離の頂点間の辺がなければ答えの候補
ans = -1

for i in range(N):
    queue = deque([i])
    visit = [-1] * N
    visit[i] = 1

    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
    #print(visit,max(visit),adj)
    dist = [[] for _ in range(max(visit))]
    for j in range(N):
        dist[visit[j]-1].append(j)

    flag = True
    for d in dist:
        if len(d) < 2: continue
        for k in d:
            for l in d:
                if k == l: continue
                if S[k][l] == '1':
                    flag = False
                    break

    if flag:
        ans = max(ans,max(visit))

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(S, i):
    D = [-1] * len(S)
    P = [set() for _ in range(len(S))]
    
    Q = deque()
    Q.append(i)
    D[i] = 1

    while Q:
        v = Q.popleft()

        for w in S[v]:
            if w in P[v]:
                continue
            
            if D[w] > 0 and D[w] < D[v] + 1:
                return -1

            if D[w] < 0:
                Q.append(w)
            P[w].add(v)
            D[w] = D[v] + 1

    return D[v]


def main():
    N = int(input())
    S = [input().strip() for _ in range(N)]
    L = [set(j for j in range(N) if S[i][j] == "1") for i in range(N)]

    res = -1
    for i in range(N):
        r = f(L, i)
        res = max(res, r) 
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import networkx as nx

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

G = nx.Graph()
for i in range(N):
    G.add_node(i)

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

if nx.is_bipartite(G):
    ans = nx.diameter(G)+1
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, graph, cur=0):
        color[v] = cur
        for u in graph[v]:
            if color[u] != -1:
                if color[u] == cur:
                    return False
                continue
            if not dfs(u, graph, 1 - cur):
                return False
        return True

    n = int(input())
    S = [list(input()) for _ in range(n)]
    edge = [[] for _ in range(n)]
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                cost[i][j] = 0
            if S[i][j] == "1":
                edge[i].append(j)
                cost[i][j] = 1

    color = [-1] * n
    if not dfs(0, edge):
        print(-1)
        exit()

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

    res = 0
    for i in range(n):
        res = max(res, max(cost[i]))
    print(res + 1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
route = [[] for i in range(n)]
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == "1":
            route[i].append(j)
            route[j].append(i)
ans = -1
for p in range(n):
    visit = [-1 for i in range(n)]
    visit[p] = 1
    d = deque()
    d.append(p)
    while d:
        now = d.popleft()
        for i in route[now]:
            if visit[i] == -1:
                visit[i] = visit[now] + 1
                d.append(i)
            elif abs(visit[i] - visit[now]) != 1:
                print(-1)
                exit()
    ans = max(ans,max(visit))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d
  


N = I()
data = SLs(N)
graph = [[] for i in range(N)]
U = UnionFind(N*2)
W = WarshallFloyd(N)
for i in range(N):
  for j in range(N):
    if data[i][j] == "1":
      graph[i].append(j)
      U.union(i,j+N)
      U.union(i+N,j)
      W.add(i,j,1)
for i in range(N):
  if U.same(i, i+N):
    print(-1)
    exit()
_,d = W.WarshallFloyd_search()
print(max(max(i) for i in d)+1)

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    sl = []
    for i in range(n):
        si = input()
        si = [1 if i == "1" else 100000 for i in si]
        sl.append(si)

    cm = csr_matrix(sl)
    d = dijkstra(cm,directed=False)
    ma = 0
    for i in range(n):
        for j in range(n):
            if d[i][j] > ma:
                ma = d[i][j]
            if sl[i][j] == 1 and (d[i][0]%2+d[j][0]%2)%2 == 0:
                print(-1)
                exit()
    print(int(ma)+1)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
Map = [[] for _ in range(N)]
for i in range(N):
    S = list(input())[:-1]
    for j in range(N):
        s = S[j]
        if s == "1":
            Map[i].append(j)
error = 0
MAX = 0
for i in range(N):
    E = 0
    flag = 1
    vmax = 0
    depth = [-1]*N
    depth[i] = 1
    q = deque([i])
    while len(q) != 0:
        cur = q.popleft()
        for chi in Map[cur]:
            if depth[chi] == -1:
                depth[chi] = depth[cur]+1
                vmax = max(vmax,depth[cur]+1)
                q.append(chi)
            else:
                if depth[chi] != depth[cur]:
                    continue
                else:
                    E = 1
                    break
    if E == 0:
        MAX = max(vmax,MAX)
    else:
        error += 1
if error == N:
    print(-1)
else:
    print(MAX)