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: Wrong Answer

Solution code:
from collections import deque


def search(N, adj, start):
    dist = [-1] * N
    q = deque()
    q.append((start, 0, -1))
    while len(q):
        p, d, prev = q.popleft()
        if dist[p] != -1:
            if dist[p] != d:
                return None
            continue
        dist[p] = d
        for nxt in adj[p]:
            if nxt == prev:
                continue
            if dist[nxt] == -1:
                q.append((nxt, d+1, prev))
    return dist


def main():
    N = int(input())
    S = [input() for _ in range(N)]
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                adj[i].add(j)
    start = 0
    while start < N and len(adj[start]) == 0:
        start += 1
    dist = search(N, adj, 0)
    if dist == None:
        print(-1)
        return
    mx = 0
    idx = 0
    for i in range(N):
        if dist[i] > mx:
            idx = i
            mx = dist[i]
    ans = max(search(N, adj, idx)) + 1
    for i in range(N):
        if len(adj[i]) == 0:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, collections

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

    colq = collections.deque()
    colq.append((0, 0))
    while colq:
        now_node, now_col = colq.popleft()
        if col[now_node] == -1:
            col[now_node] = now_col
            for next_node in edge[now_col]: colq.append((next_node, 1 ^ now_col))
        else:
            if col[now_node] != now_col: 
                print(-1)
                break
    else:
        q = collections.deque()
        farest = [-1, -1]
        dist_to, dist_back = dict(), dict()
        for i in range(N):
            dist_to[i] = -1
            dist_back[i] = -1

        q.append((0, 0))
        while q:
            now_node, now_dist = q.popleft()
            if dist_to[now_node] == -1:
                dist_to[now_node] = now_dist
                if now_dist > farest[0]: farest = [now_dist, now_node] 
                for next_node in edge[now_node]:
                    if dist_to[next_node] == -1: q.append((next_node, now_dist + 1))

        diameter = 0
        q.append((farest[1], 1))
        while q:
            now_node, now_dist = q.popleft()
            if dist_back[now_node] == -1:
                dist_back[now_node] = now_dist
                if now_dist > diameter: diameter = now_dist
                for next_node in edge[now_node]:
                    if dist_back[next_node] == -1: q.append((next_node, now_dist + 1))
        print(diameter)
        #print(dist_back)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
neighbours = [[] for i in range(N)]
for i in range(N):
    line = list(input())
    for j, char in enumerate(line):
        if char == '1': neighbours[i].append(j)

isPossible = True

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

distances[0] = 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))
    for n1 in range(N):
        for n2 in range(n1 + 1, N):
            dists = set()
            for n3 in range(n2 + 1, N):
                if n3 in neighbours[n1] and n3 in neighbours[n2]:
                    dists.add(distances[n3])
            if len(dists) == 1:
                total += 1
    print(total)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

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

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

USE=[-1]*N

Q=deque()
Q.append(0)
USE[0]=0

flag=1

while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[x]==USE[to]:
            print(-1)
            sys.exit()
            
        elif USE[to]==-1:
            USE[to]=1-USE[x]
            Q.append(to)

for i in range(N):
    for j in range(N):
        if S[i][j]=="1" and USE[i]==USE[j]:
            print(-1)
            sys.exit()

Q=deque()
Q.append(0)
USE=[0]*N
USE[0]=1
H=[0]*N

while Q:
    NQ=deque()
    while Q:
        
        x=Q.pop()

        for to in E[x]:
            if USE[to]==0:
                H[to]=H[x]+1
                USE[to]=1
                NQ.append(to)

    Q=NQ


Q=deque()
NOW=H.index(max(H))
Q.append(NOW)
USE=[0]*N
USE[NOW]=1
H=[0]*N

while Q:
    NQ=deque()
    while Q:
        
        x=Q.pop()

        for to in E[x]:
            if USE[to]==0:
                H[to]=H[x]+1
                USE[to]=1
                NQ.append(to)

    Q=NQ

print(max(H)+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, from_, to_):
        self.E[from_].append(to_)
        self.E[to_].append(from_)

        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)

    visited = [False]*N
    q = deque()
    q.append(0)
    while len(q) > 0:
        node = q.popleft()
        visited[node] = True
        for to_ in g.E[node]:
            if visited[to_] is False:
                q.append(to_)

    depth = [INF]*N
    q = deque()
    q.append((node, 1))
    while len(q) > 0:
        node, d = q.popleft()
        depth[node] = d
        for to_ in g.E[node]:
            if depth[to_] == INF:
                q.append((to_, d+1))
            elif abs(d-depth[to_]) != 1:
                print(-1)
                return
    print(d)
    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))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
s = []
for i in range(N):
    s.append(list(input()))
for i in range(N):
    s[i] = [int(j) for j in s[i]]

from collections import deque
from collections import defaultdict

g = defaultdict(set)

for i in range(N):
    for j in range(N):
        if s[i][j] == 1:
            g[i+1].add(j+1)
            g[j+1].add(i+1)

color = [0 for i in range(N+1)]


color[1] = 1
que = deque([1])#始点を追加
bipartite = True

while len(que):
    p = que.popleft()#直近で追加したグラフの頂点を取得
    for q in list(g[p]):#結合しているグラフの頂点を参照
        if color[q] == 0:#塗られていないなら別の色で塗る
            color[q] = -color[p]
            que.append(q)
        elif color[q] == color[p]:#同じ色だったら2部グラフではないと返し終了させる
            bipartite = False
            break

if bipartite:
    ans = 0
    for i in range(N):
        q = []
        q.append(i+1)
        visit = [False]*(N+1)
        visit[i+1] = True
        dia = 0
        while q:
            dia += 1
            now = q.pop()
            nextq = []
            for next in g[now]:
                if not visit[next]:
                    visit[next] = True
                    nextq.append(next)
            q = nextq[:]
        ans = max(dia, ans)

    print(ans)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
S = list(list(input()) for i in range(N))
for i in range(N):
    for j in range(N):
        S[i][j] = int(S[i][j])
ans = 0
for i in range(N):
    V = [0]*N
    T = [[0]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            T[i][j] = S[i][j]
    V[i] = 1
    queue = deque([i])
    while queue:
        q = queue.popleft()
        for i in range(N):
            if T[q][i] == 1:
                queue.append(i)
                if not(V[i] == 0 or V[i] == V[q]+1):
                    print(-1)
                    exit()
                V[i] = V[q]+1
                T[i][q] = 0
                T[q][i] = 0
    ans = max(max(V),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

S = []

for i in range(N):

    s = input()
    S.append(s)

lis = [float("inf")] * N
lis[0] = 0
q = deque([])

q.append(0)

#print (S,lis)

while len(q) > 0:

    now = q.pop()

    for i in range(N):

        #print (i,now)
        if S[now][i] == "1" and lis[i] > lis[now] + 1:
            lis[i] = lis[now] + 1
            q.append(i)

mind = 0
#print (lis)

for i in lis:
    if lis[mind] < lis[i]:
        mind = i


lis = [float("inf")] * N
lis[mind] = 0
q = deque([])
q.append(mind)

#print (q,len(q),lis)

while len(q) > 0:

    now = q.pop()
    #print (now)
    

    for i in range(N):

        if S[now][i] == "1" and lis[i] > lis[now] + 1:

            lis[i] = lis[now] + 1
            q.append(i)


nlis = [None] * N
nlis[mind] = 0
q = deque([])
q.append(mind)
flag = True

while len(q) > 0:

    now = q.pop()  

    for i in range(N):

        if S[now][i] == "1" and nlis[i] == None:
   
            nlis[i] = nlis[now] ^ 1
            q.append(i)

        elif S[now][i] == "1" and nlis[now] == nlis[i]:
            flag = False
            break

    if not flag:
        break

if flag:
    print (max(lis) + 1)

else:
    print (-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, from_, to_):
        self.E[from_].append(to_)
        self.E[to_].append(from_)

        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)

    visited = [False]*N
    q = deque()
    q.append(0)
    while len(q) > 0:
        node = q.popleft()
        visited[node] = True
        for to_ in g.E[node]:
            if visited[to_] is False:
                q.append(to_)

    depth = [INF]*N
    q = deque()
    q.append((node, 1))
    while len(q) > 0:
        node, d = q.popleft()
        depth[node] = d
        for to_ in g.E[node]:
            if depth[to_] == INF:
                q.append((to_, d+1))
            elif depth[to_] == d+1 or depth[to_] == d-1:
                continue
            else:
                print(-1)
                return
            # print(q)
    print(max(depth))
    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))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def search(N, adj, start):
    dist = [-1] * N
    q = deque()
    q.append((start, 0, -1))
    while len(q):
        p, d, prev = q.popleft()
        if dist[p] != -1:
            if dist[p] != d:
                return None
            continue
        dist[p] = d
        for nxt in adj[p]:
            if nxt == prev:
                continue
            if dist[nxt] == -1:
                q.append((nxt, d+1, prev))
    return dist


def main():
    N = int(input())
    S = [input() for _ in range(N)]
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                adj[i].add(j)
    dist = search(N, adj, 0)
    if dist == None:
        print(-1)
        return
    mx = 0
    idx = 0
    for i in range(N):
        if dist[i] > mx:
            idx = i
            mx = dist[i]
    ans = max(search(N, adj, idx)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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

possible= True
for home in range(N):
    q = deque([(home, -1, 0)])
    while len(q) > 0:
        src, prev, dist = q.popleft()
        if src == home and dist > 0:
            possible = False
            break
        #
        for dst in graph[src]:
            if dst == prev:
                continue
            elif dist < 3:
                q.append((dst, src, dist + 1))
            else:
                continue

if possible:
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall
    #
    S = csr_matrix(S)
    dist = floyd_warshall(csgraph=S, directed=False)
    ans_tmp = int(np.max(dist)) + 1
    print(ans_tmp)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
ans = 0
for i in range(int(input())): ans ^= int(input(), 2)
ans = sum(map(int,list(bin(ans)[2::])))
if ans==0: print(-1)
else: print(ans)

Submission status: Wrong Answer

Solution code:
import collections


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

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


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


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


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

Submission status: Wrong Answer

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

s = list(input())
k = int(input())

flag = False
if s[0] == s[-1]:
#    print("flag")
    flag = True
else:
    pass

#sの中だけ考える
count = 0
dp = ""
for i in range(len(s)):
    if dp == s[i]:
        count += 1
        dp = ""
    else:
        dp = s[i]
ans = count * k


if flag:
    try:
        #もし後ろ３つが同じなら
#        print("here")
        if len(set([s[-1],s[-2],s[-3]])) == 1:
            if len(set([s[0],s[1]])) == 1:
                pass
                if len(set([s[0],s[1],s[2]])) == 1:
                    ans = ans + (k-1)
                else:
                    pass
            else:
                ans = ans + (k-1)
    except IndexError:
        pass
else:
    pass

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

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

if N % 2 == 0:
    print(-10)
    exit()

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

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

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

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

if ans == float('inf'):
    print(-1)
    exit()
print(ans + 1)

Submission status: Wrong Answer

Solution code:
import sys
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)]
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()

for i in range(len(es)):
  if len(es[i])==1:
    x=i
connection=es
distance1=[-1 for i in range(n)]
distance1[i]=0
next=connection[i]
next2=[]
check=[-1 for i in range(n)]
check[i]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance1[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]
 
print(max(distance1)+1)

Submission status: Wrong Answer

Solution code:
s = str(input())
k=int(input())



if len(s)==1:
    if k<2:
        ans = 0
    else:
        ans = k//2
elif len(s)==2:
    if s[0]==s[1]:
        ans = k
    else:
        ans = 0
else:
    if k == 1:
        ans = 0
        bef = ""
        befchen = False
        trignum = 0
        for i in range(len(s)):
            now = s[i]
            if bef==now:
                if befchen == False:
                    ans += 1
                    befchen = True
                    trignum = i
            if  befchen == True:
                if trignum == i-1:
                    befchen = False
            bef = now

    elif k >=2:
        ans = 0
        bef = ""
        befchen = False
        trignum = 0
        for i in range(len(s)):
            now = s[i]
            if bef==now:
                if befchen == False:
                    #print(now)
                    ans += 1
                    befchen = True
                    trignum = i
            if  befchen == True:
                if trignum == i-1:
                    befchen = False
            bef = now
        
        if s[0]==s[-1]:
            if befchen == False:
                ans += 1
                
        ans *= k
        
        if s[0]==s[-1]:
            if befchen == False:
                ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
table=[[0]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    table[i][j]=int(s[j])
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)
ans=0
for i in range(n):
  for j in range(i+1,n):
    ans=max(ans,int(d[i][j])+1)
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if table[i][j]*table[j][k]*table[k][i]==1:
        ans=-1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections


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

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


n = int(input())
graph = Graph(n)
for i in range(n):
    s = input().rstrip()
    for j in range(n):
        if s[j] == '1':
            graph.add_edge(i, j, undirected=True)
l = [(len(edge), i) for i, edge in enumerate(graph.edges)]
l.sort()


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


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque


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

    visited = [False]*N
    q = deque()
    q.append(0)
    while len(q) > 0:
        node = q.popleft()
        visited[node] = True
        for to_, ex in enumerate(S[node]):
            if ex == 0:
                continue
            if visited[to_] is False:
                q.append(to_)

    depth = [INF]*N
    q = deque()
    q.append((node, 1))
    while len(q) > 0:
        node, d = q.popleft()
        depth[node] = d
        # print(node, S[node])
        for to_, ex in enumerate(S[node]):
            if ex == 0:
                continue
            if depth[to_] == INF:
                q.append((to_, d+1))
            elif depth[to_] == d+1 or depth[to_] == d-1:
                continue
            else:
                # print(depth)
                print(-1)
                return
            # print(q)
    print(max(depth))
    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))  # type: int
    S = [[int(c) for c in next(tokens)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

if N == 2:
    print('hhh')
    exit()

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

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

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

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

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

print(ans // 2)

Submission status: Wrong Answer

Solution code:
import collections


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

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


n = int(input())
graph = Graph(n)
for i in range(n):
    s = input().rstrip()
    for j in range(n):
        if s[j] == '1':
            graph.add_edge(i, j, undirected=True)
l = [(len(edge), i) for i, edge in enumerate(graph.edges)]
l.sort()

orders = [-1] * n
q = collections.deque()
index = l[0][1]
q.append(index)
orders[index] = 1


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


while q:
    node = q.pop()
    ok = check(node)
    if not ok:
        print(-1)
        break
else:
    print(max(orders))

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(links):
    color = [-1] * n
    last_v = None
    q = deque([(0, 0)])
    while q:
        v, c = q.popleft()
        if color[v] != -1:
            if color[v] != c:
                return -1
            continue
        else:
            color[v] = c
        last_v = v
        new_c = c ^ 1
        for u in links[v]:
            if color[u] != -1:
                if color[u] != new_c:
                    return -1
                continue
            q.append((u, new_c))
    return last_v


def bfs2(s, links):
    visited = set()
    q = deque([(s, 1)])
    last_d = -1
    while q:
        v, d = q.popleft()
        if v in visited:
            continue
        visited.add(v)
        last_d = d
        for u in links[v]:
            if u in visited:
                continue
            q.append((u, d + 1))
    return last_d


def solve(n, links):
    res = bfs(links)
    if res == -1:
        return -1
    return bfs2(res, links)


n = int(input())
links = [set() for _ in range(n)]
for i in range(n):
    s = input()
    for j, c in enumerate(s):
        if c == '0':
            continue
        links[i].add(j)

print(solve(n, links))

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

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

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

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

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

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

if ans % 2 == 1:
    print(0)
print(ans + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

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

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

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

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

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

if ans % 2 == 0:
    print(0)
print(ans + 1)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import*
n=int(input())
G=floyd_warshall([[x=="1" or float("inf") for x in input()]for _ in range(n)],0)
m=1
for a in G:
	ids=np.where(a==1.)
	m=max(np.amax(a)+1,m)
	for i,j in combinations(ids[0],2):
		if G[i,j]%2:
			print(-1)
			exit()
print(int(m))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

USE=[-1]*N

from collections import deque

Q=deque()
Q.append(0)
USE[0]=0

flag=1

while Q:
    x=Q.pop()

    for i in range(N):
        if S[x][i]=="1":
            if USE[i]==USE[x]:
                flag=0
                break

            elif USE[i]==-1:
                USE[i]=1-USE[x]
                Q.append(i)

    if flag==0:
        print(-1)
        sys.exit()

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

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

Q=deque()
Q.append(0)
USE=[0]*N
USE[0]=1
H=[0]*N

while Q:
    NQ=deque()
    while Q:
        
        x=Q.pop()

        for to in E[x]:
            if USE[to]==0:
                H[to]=H[x]+1
                USE[to]=1
                NQ.append(to)

    Q=NQ


Q=deque()
NOW=H.index(max(H))
Q.append(NOW)
USE=[0]*N
USE[NOW]=1
H=[0]*N

while Q:
    NQ=deque()
    while Q:
        
        x=Q.pop()

        for to in E[x]:
            if USE[to]==0:
                H[to]=H[x]+1
                USE[to]=1
                NQ.append(to)

    Q=NQ

print(max(H)+1)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[input() for i in range(N)]
G=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j]=="1":
            G[i].append(j)
q=[0]
dist=[-1 for i in range(N)]
dist[0]=0
while(q):
    r=q.pop()
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=1-dist[r]
            q.append(p)
for i in range(N):
    for j in G[i]:
        if (dist[i]-dist[j])%2==0:
            print(-1)
            exit()
#possible
#print(G)
d=[[10**9 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in G[i]:
        d[i][j]=1
    d[i][i]=0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
X=[]
Y=[]
for i in range(N):
    if dist[i]==1:
        X.append(i)
    else:
        Y.append(i)
ans=2
for x in X:
    for y in Y:
        ans=max(ans,d[x][y]+1)
print(ans)