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:
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n #0:黒, 1:白
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [10**7]*n
    d[i] = 0
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            dist[i][j] = 1
for i in range(n):
    for k in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
for i in range(n):
    for j in range(n):
        if dist[i][j] != 10**7:
            maxdist = max(maxdist, dist[i][j])
print(maxdist+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n #0:黒, 1:白
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [10**7]*n
    d[i] = 0
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            dist[i][j] = 1
for i in range(n):
    for k in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
            if dist[i][j] != 10**7:
                maxdist = max(maxdist, dist[i][j])
print(maxdist)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n #0:黒, 1:白
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    next = []
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [10**7]*n
    d[i] = 0
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            dist[i][j] = 1
for i in range(n):
    for k in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
            if dist[i][j] != 10**7:
                maxdist = max(maxdist, dist[i][j])
print(maxdist+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n #0:黒, 1:白
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    next = []
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [10**7]*n
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            dist[i][j] = 1
for i in range(n):
    for k in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
            if dist[i][j] != 10**7 and i != j:
                maxdist = max(maxdist, dist[i][j])
print(maxdist+1)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]
    INF = 10**5

    dist = [INF for _ in range(N)]
    col = [0 for _ in range(N)]
    dist[0],col[0] = 0,1
    q = deque([(0,1)])
    D = 0
    while q:
        now,nc = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if col[fol] == 0:
                    col[fol] = -1*nc
                    q.append((fol,-1*nc))
                elif col[fol] == nc:
                    print(-1)
                    exit()

    q = deque([0])
    while q:
        now = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] > dist[now]+1:
                    dist[fol] = dist[now]+1
                    q.append(fol)
                    
    e = dist.index(max(dist))
    dist = [INF for _ in range(N)]
    dist[e] = 0
    q = deque([e])
    while q:
        now = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] > dist[now]+1:
                    dist[fol] = dist[now]+1
                    q.append(fol)
    
    print(max(dist)+1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]

    dist = [-1 for _ in range(N)]
    col = [0 for _ in range(N)]
    dist[0],col[0] = 0,1
    q = deque([(0,1)])
    D = 0
    while q:
        now,nc = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if col[fol] == 0:
                    col[fol] = -1*nc
                    q.append((fol,-1*nc))
                elif col[fol] == nc:
                    print(-1)
                    exit()

    q = deque([0])
    while q:
        now = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    q.append(fol)
                    
    e = dist.index(max(dist))
    dist = [-1 for _ in range(N)]
    dist[e] = 0
    q = deque([e])
    while q:
        now = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    q.append(fol)
    
    print(max(dist)+1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]

    dist = [-1 for _ in range(N)]
    dist[0] = 0
    q = deque([0])
    D,e = 0,0
    while q:
        now = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    if dist[fol] > D:
                        e = fol
                    q.append(fol)
                elif dist[now]%2 == dist[fol]%2:
                    print(-1)
                    exit()

    q = deque([e])
    dist = [-1 for _ in range(N)]
    dist[e] = 0
    while q:
        now = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    q.append(fol)

    print(max(dist)+1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]

    dist = [-1 for _ in range(N)]
    col = [0 for _ in range(N)]
    dist[0],col[0] = 0,1
    q = deque([(0,1)])
    D = 0
    while q:
        now,nc = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if col[fol] == 0:
                    col[fol] = -1*nc
                    q.append((fol,-1*nc))
                elif col[fol] == nc:
                    print(-1)
                    exit()

    q = deque([0])
    while q:
        now = q.pop()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    q.append(fol)
                    
    e = dist.index(max(dist))
    dist = [-1 for _ in range(N)]
    dist[e] = 0
    q = deque([e])
    while q:
        now = q.pop()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    q.append(fol)
    
    print(max(dist)+1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]

    dist = [-1 for _ in range(N)]
    col = [0 for _ in range(N)]
    dist[0],col[0] = 0,1
    q = deque([(0,1)])
    D = 0
    while q:
        now,nc = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if col[fol] == nc:
                    print(-1)
                    exit()
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    col[fol] = -1*nc
                    q.append((fol,-1*nc))

    e = dist.index(max(dist))
    q = deque([e])
    dist = [-1 for _ in range(N)]
    dist[e] = 0
    while q:
        now = q.pop()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    q.append(fol)

    print(max(dist)+1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]

    dist = [-1 for _ in range(N)]
    dist[0] = 0
    q = deque([0])
    D,e = 0,0
    while q:
        now = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    if dist[fol] > D:
                        e = fol
                    dist[fol] %= 2
                    q.append(fol)
                elif dist[now] == dist[fol]:
                    print(-1)
                    exit()

    q = deque([e])
    dist = [-1 for _ in range(N)]
    dist[e] = 0
    while q:
        now = q.pop()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    q.append(fol)

    print(max(dist)+1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]

    dist = [-1 for _ in range(N)]
    dist[0] = 0
    q = deque([0])
    D,e = 0,0
    while q:
        now = q.pop()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    if dist[fol] > D:
                        e = fol
                    q.append(fol)
                elif dist[now]%2 == dist[fol]%2:
                    print(-1)
                    exit()

    q = deque([e])
    dist = [-1 for _ in range(N)]
    dist[e] = 0
    while q:
        now = q.pop()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if dist[fol] == -1:
                    dist[fol] = dist[now]+1
                    q.append(fol)

    print(max(dist)+1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n):
    p=list(str(input()))
    for j in range(n):
        if p[j]=='1':
            g[i].append(j)
q=deque([0])
v=[-1]*n
v[0]=0
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
        else:
            if v[i]!=1-v[p]:
                print(-1)
                exit()
q=deque([0])
v=[0]*n
v[0]=1
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1+v[p]
            q.append(i)
s=v.index(max(v))
q=deque([s])
v=[0]*n
v[s]=1
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1+v[p]
            q.append(i)
print(max(v))

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n):
    p=list(str(input()))
    for j in range(n):
        if p[j]=='1':
            g[i].append(j)
q=deque([0])
v=[-1]*n
v[0]=0
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
        else:
            if v[i]!=1-v[p]:
                print(-1)
                exit()
q=deque([0])
v=[0]*n
v[0]=1
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1+v[p]
            q.append(i)
s=v.index(max(v))
q=deque([s])
v=[0]*n
v[0]=1
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1+v[p]
            q.append(i)
print(max(v))

Submission status: Wrong Answer

Solution code:
class Graph(): #non-directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append(e[1] - 1)
            self.graph[e[1] - 1].append(e[0] - 1)

    def is_bipartite(self):
        group = [None for _ in range(self.n)]
        stack = [(0, 1)]
        while stack:
            node, nodecolor = stack.pop()
            group[node] = nodecolor
            for adj in self.graph[node]:
                if group[adj] == nodecolor:
                    return False
                if group[adj] is None:
                    adjcolor = 1 - nodecolor
                    stack.append((adj, adjcolor))
        return True

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        diam = 1
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j in self.graph[i]:
                dist[i][j] = 1
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                        diam = max(diam, dist[i][j] + 1)
        return dist, diam

N = int(input())
E = []

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

G = Graph(N, E)

if G.is_bipartite():
    dist, diam = G.warshall_floyd()
    print(diam)
    
else:
    print(-1)

Submission status: Wrong Answer

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

def floyd_warshall(dist):
    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])

def is_bipartite(u):
    for v in range(N):
        if u == v or dist[u][v] != 1:
            continue
        if color[v] == -1:
            color[v] = 1 - color[u]
            return is_bipartite(v)
        elif color[u] == color[v]:
            return False
    return True

N = int(input())
S = [input().rstrip() for _ in range(N)]
dist = [[1 if S[i][j] == '1' else (0 if i == j else float('inf')) for j in range(N)] for i in range(N)]
color = [-1] * N
color[0] = 0
ans = 0
if is_bipartite(0):
    floyd_warshall(dist)
    ans = max(max(d) for d in dist) + 1
else:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(G, s):
    cost=[-1]*len(G)
    cost[s]=1
    stack=[s]
    while stack:
        u=stack.pop()
        for v in G[u]:
            if cost[v]<0:
                cost[v]=cost[u]+1
                stack.append(v)
            elif abs(cost[u]-cost[v])!=1:
                return -1
    return max(cost)

def main():
    N=int(input())
    S=[[bool(int(i)) for i in input()] for _ in range(N)]
    G=[[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j]:
                G[i].append(j)
    print(max(dfs(G,i) for i in range(N)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
N = gi()
S = []
for i in range(N):
    S.append(gw())
    #print(i, S[i])


def bfs(sv):
    q = deque()
    q.append(sv)
    d = [0] * N
    d[sv] = 1

    while len(q):
        v = q.pop()
        for u in range(N):
            if S[u][v] == "0":
                continue
            if d[u]:
                if abs(d[u] - d[v]) != 1:
                    return 0
            # print(u, v, d[u], d[v])
            else:
                d[u] = d[v] + 1
                q.append(u)
    return max(d)


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

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
ls = [list(input()) for i in range(n)]
graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
parity = [-1 for i in range(n+1)]
dist = [0 for i in range(n+1)]
for i in range(n):
  for j in range(i,n):
    if ls[i][j] == "1":
      graph[i+1].append(j+1)
      graph[j+1].append(i+1)
que = deque([(1,0)])
parity[1] = 0
visited[1] = 1
while que:
  x,cnt = que.popleft()
  dist[x] = cnt
  for y in graph[x]:
    if visited[y] == 0:
      que.append((y,cnt+1))
      visited[y] = 1
      parity[y] = 1-parity[x]
k = max(dist)
farls = []
for i in range(1,n+1):
  if dist[i] == k:
    farls.append(i)
ans = []
for far in farls:
  que.append((far,0))
  visited = [0 for i in range(n+1)]
  visited[far] = 1
  dist = [0 for i in range(n+1)]
  while que:
    x,cnt = que.popleft()
    dist[x] = cnt
    for y in graph[x]:
      if visited[y] == 0:
        que.append((y,cnt+1))
        visited[y] = 1
      if parity[y] == parity[x]:
        print(-1)
        exit()
  ans.append(max(dist))
print(max(ans)+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
ls = [list(input()) for i in range(n)]
graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
parity = [-1 for i in range(n+1)]
dist = [0 for i in range(n+1)]
for i in range(n):
  for j in range(i,n):
    if ls[i][j] == "1":
      graph[i+1].append(j+1)
      graph[j+1].append(i+1)
que = deque([(1,0)])
parity[1] = 0
visited[1] = 1
while que:
  x,cnt = que.popleft()
  dist[x] = cnt
  for y in graph[x]:
    if visited[y] == 0:
      que.append((y,cnt+1))
      visited[y] = 1
      parity[y] = 1-parity[x]

far = dist.index(max(dist))
visited[far] = 2
que.append((far,0))
while que:
  x,cnt = que.popleft()
  dist[x] = cnt
  for y in graph[x]:
    if visited[y] == 1:
      que.append((y,cnt+1))
      visited[y] = 2
    if parity[y] == parity[x]:
      print(-1)
      exit()
print(max(dist)+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [list(map(int, list(input()))) for _ in range(N)]
#print("S:", S)

INF = 10 ** 15

AB = []
for i in range(N):
  for j in range(i + 1, N):
    if S[i][j]:
      AB.append((i, j))
#print("AB:", AB)

for i in range(N):
  for j in range(N):
    if S[i][j] == 0:
      S[i][j] = INF

for k in range(N):
  for i in range(N):
    for j in range(N):
      S[i][j] = min(S[i][j], S[i][k] + S[k][j])
#print("S:", S)

answer = -2
for i in range(N):
  flag = 1
  for A, B in AB:
    if abs(S[i][A] - S[i][B]) != 1:
      flag = 0
      break
  if flag:
    answer = max(answer, max(S[i]))

print(answer + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [list(map(int, list(input()))) for _ in range(N)]
#print("S:", S)

INF = 100
graph = [[] for _ in range(N)]
for i in range(N):
  for j in range(N):
    if S[i][j]:
      graph[i].append(j)
#print("graph:", graph)

def dfs(s, i):
  for g in graph[s]:
    #print("i, s, g, dist:", i, s, g, dist)
    if g == i and (dist[s] + 1) % 2:
      print(-1)
      exit()
    else:
      if dist[g] > dist[s] + 1:
        dist[g] = dist[s] + 1
        dfs(g, i)

answer = 0
for i in range(N):
  #print("i:", i)
  stack = [i]
  dist = [INF] * N
  dist[i] = 0
  
  dfs(i, i)
  answer = max(answer, max(dist))

print(answer + 1)

Submission status: Wrong Answer

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

INF = 10 ** 15

for i in range(N):
  for j in range(N):
    if S[i][j] == 0:
      S[i][j] = INF

for k in range(N):
  for i in range(N):
    for j in range(N):
      S[i][j] = min(S[i][j], S[i][k] + S[k][j])
#print("S:", S)

max_dist = -1
max_i = 0
for i in range(N):
  for j in range(N):
    Sij = S[i][j]
    if Sij == INF:
      continue
    else:
      if max_dist < Sij:
        max_dist = Sij
        max_i = i + 1
#print("max_dist, max_i:", max_dist, max_i)

V = [[] for _ in range(N)]
check = [0] * (N + 1)
V[0].append(max_i) 
check[max_i] = 1
#print(V)

for i in range(1, N):
  
  for v in V[i - 1]:
    for j in range(1, N + 1):
      if check[j] == 0 and S[v - 1][j - 1] == 1:
        check[j] = 1
        V[i].append(j)
  #print(V)
  
  lenVi = len(V[i])
  flag = 0
  for i in range(lenVi):
    for j in range(i + 1, lenVi):
      if S[i - 1][j - 1] == 1:
        print(-1)
        exit()

answer = 0
for i in range(N):
  if len(V[i]):
    answer += 1

#print(V)
print(answer)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    ma = 0
    e = [[] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if(S[i][j] == '1'): e[i].append(j) 
    for i in range(N):
        dep = [-1] * N
        q = collections.deque()
        dep[i] = 0
        q.append(i)
        while(len(q) > 0):
            now = q.popleft()
            for nxt in e[now]:
                if dep[nxt] == -1:
                    dep[nxt] = dep[now] + 1
                    q.append(nxt)
        for j in range(N):
            ma = max(ma, dep[j])
    
    print(ma)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
#import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    inf = int(1e9)
    wf = [[inf] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            wf[i][j] = 1 if S[i][j] == '1' else inf
    for k in range(N):
        for i in range(N):
            for j in range(N):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    
    ma = 0
    for i in range(N):
        for j in range(N):
            ma = max(ma, wf[i][j])

    print(ma + 1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    inf = int(1e9)
    wf = [[inf] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            wf[i][j] = 1 if S[i][j] == '1' else inf
    for k in range(N):
        for i in range(N):
            for j in range(N):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    
    ma = 0
    for i in range(N):
        for j in range(N):
            ma = max(ma, wf[i][j])

    print(ma + 1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#二部グラフ化できるか
#最大深さ

import sys
readline = sys.stdin.readline
write = sys.stdout.write
from collections import deque

n = int(input())
s = []

for i in range(n):
    sij = input()
    s.append(sij)
    
d = [-1]*n

Q = deque()

d[0] = 0

Q.append(0)

while Q:
    v = Q.popleft()
    for i in range(n):
        if int(s[v][i]):
            if d[i]<0:
                d[i] = d[v] + 1
                Q.append(i)
            elif (d[i]-d[v])%2==0:
                #print(d)
                print(-1)
                exit()

mxd = max(d)
mxd_id = d.index(mxd)

    
d2 = [-1]*n

d2[mxd_id] = 0

Q.append(mxd_id)

while Q:
    v = Q.popleft()
    for i in range(n):
        if int(s[v][i]):
            if d2[i]<0:
                d2[i] = d2[v] + 1
                Q.append(i)
#print(d)
#print(d2)
print(max(d2)+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[] for i in range(n+1)]
for i in range(1,1+n):
  l1=list(input())
  for j in range(1,1+n):
    if l1[j-1]=="1":
      l[i].append(j)
color=[0 for i in range(n+1)]
b=True
def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(l[v])):
        if color[ l[v][i] ] == c:
            return False
        elif color[ l[v][i] ] == 0 and not f(l[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
b=f(1,1)
if not b:
  print(-1)
else:
  inf=10**10
  d=[[inf for i in range(n+1)] for j in range(n+1)]
  for i in range(n+1):
    for j in l[i]:
      d[i][j]=1
  for k in range(n+1):
    for j in range(1,n+1):
      for i in range(1,n+1):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  max=0
  for i in range(1,n+1):
    for j in range(1,n+1):
      if d[i][j]>max:
        max=d[i][j]
        index1=i
        index2=j
  if index1==index2:
    print(2)
  else: 
    print(max+1)