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 is_bin_graph(edges,st):
    """
    :param edges: 辺のdictionary,0-indexedを想定
    :param st: start
    :return:is_bin:二部グラフかどうか
    """
    que = deque()
    v = [0 for i in range(len(edges))]
    que.append([st,0])
    v[st] = 1
    is_bin = True
    while True:
        if len(que) > 0:
            top = que.popleft()
            col = v[top[0]]
            cos = top[1]
            for nex in edges[top[0]]:
                if v[nex] == 0:
                    v[nex] = -col
                    que.append([nex,cos+1])
                else:
                    if v[nex] == col:
                        is_bin = False
                    else:
                        continue
        else:
            break
        if not is_bin:
            break

    return  is_bin

def dfs(edges,st):
    que = deque()
    v = [0 for i in range(len(edges))]
    que.append([st,0])
    v[st] = 1
    max_cos = 0
    while True:
        if len(que) > 0:
            top = que.popleft()
            cos = top[1]
            for nex in edges[top[0]]:
                if v[nex] == 0:
                    v[nex] = 1
                    que.append([nex,cos+1])
                    if cos +1 > max_cos:
                        max_cos = cos+1
        else:
            break

    return  max_cos

n = int(input())
edges = {}
for i in range(n):
    s = input()
    edges[i] = []
    for j in range(n):
        if s[j] == "1":
            edges[i].append(j)

if is_bin_graph(edges,0):
    tp = 0
    for i in range(n):
        cos = dfs(edges,i)
        if tp < cos:
            tp = cos
    print(cos+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    
    adj=[[]for _ in range(N)]
    
    deg=N+1
    degv=0
    
    #一番次数が小さいところから始めるか
    
    for i in range(N):
        S=list(input())
        cnt=0
        for j in range(N):
            if S[j]=="1":
                adj[i].append(j)
                cnt+=1
        if cnt<deg:
            deg=cnt
            degv=i
            
    import queue
    
    q=queue.Queue()
    q.put((degv,1))
    V=[-1]*N
    V[degv]=1
    
    flag=0
    
    while not q.empty():
        v,d=q.get()
        for nv in adj[v]:
            if V[nv]==-1:
                V[nv]=d+1
                q.put((nv,d+1))
            else:
                if abs(V[nv]-V[v])!=1:
                    flag=1
                    break
                
    for v in range(N):
        for nv in adj[v]:
            if abs(V[nv]-V[v])!=1:
                flag=1
                break
                
    if flag:
        print(-1)
    else:
        print(max(V))
        
        

main()

Submission status: Wrong Answer

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    
    adj=[[]for _ in range(N)]
    
    deg=N+1
    degv=0
    
    #一番次数が小さいところから始めるか
    
    for i in range(N):
        S=list(input())
        cnt=0
        for j in range(N):
            if S[j]=="1":
                adj[i].append(j)
                cnt+=1
        if cnt<deg:
            deg=cnt
            degv=i
            
    import queue
    
    q=queue.Queue()
    q.put((degv,1))
    V=[0]*N
    V[degv]=1
    
    flag=0
    
    while not q.empty():
        v,d=q.get()
        for nv in adj[v]:
            if V[nv]==0:
                V[nv]=d+1
                q.put((nv,d+1))
            else:
                if abs(V[nv]-V[v])!=1:
                    flag=1
                    break
                
    if flag:
        print(-1)
    else:
        print(max(V))
        
        

main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for i in range(n):
    s = list(map(int, list(input().rstrip())))
    for j in range(n):
        if s[j]:
            edges[i].append(j)


def dfs(v, parent, d):
    visited[v] = 1
    depth[v] = d
    for v2 in edges[v]:
        if v2 == parent:
            continue
        if visited[v2]:
            d2 = depth[v2]
            n_cycle = d-d2+1
            if 0 < n_cycle:
                cycle.append(n_cycle)
            continue
        dfs(v2, v, d+1)


cycle = []
depth = [0]*n
visited = [0]*n
dfs(0, -1, 0)


def bfs(init_v):
    next_v = deque([init_v])
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)
    return dist


if all(c % 2 == 0 for c in cycle):
    dist = bfs(0)
    dmax = max(dist)
    ans = dmax
    for i in range(n):
        if dist[i] != dmax:
            continue
        dist = bfs(i)
        x = max(dist)
        if ans < x:
            ans = x
    print(ans+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for i in range(n):
    s = list(map(int, list(input().rstrip())))
    for j in range(n):
        if s[j]:
            edges[i].append(j)


def dfs(v, parent, d):
    visited[v] = 1
    depth[v] = d
    for v2 in edges[v]:
        if v2 == parent:
            continue
        if visited[v2]:
            d2 = depth[v2]
            n_cycle = d-d2+1
            if 0 < n_cycle:
                cycle.append(n_cycle)
            continue
        dfs(v2, v, d+1)


cycle = []
depth = [0]*n
visited = [0]*n
dfs(0, -1, 0)


def bfs(init_v):
    next_v = deque([init_v])
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)
    return dist


if all(c % 2 == 0 for c in cycle):
    dist = bfs(0)
    idx = dist.index(max(dist))
    dist = bfs(idx)
    print(max(dist)+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    adj = []
    for i in range(N):
        adj.append(S())

    def bfs(v):
        group = [-1] * N
        q = deque([(v, 0)])
        group[v] = 0
        while q:
            cur_v, gid = q.popleft()
            for next_v in range(N):
                if adj[cur_v][next_v] == '0':
                    continue
                if group[next_v] != -1:
                    if abs(group[cur_v] - group[next_v]) > 1:
                        return -1
                    else:
                        continue
                group[next_v] = gid + 1
                q.append((next_v, gid+1))
        return max(group) + 1

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

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[j for j,k in enumerate(input())if k=="1"]for i in range(n)]
table=[-1]*n
def nibu(x):
    for i in l[x]:
        if table[i]==-1:
            table[i]=1-table[x]
        else:
            if table[i]==table[x]:return 1
    return 0
table[0]=0
if nibu(0):
    print(-1)
else:
    class WarshallFloyd:
        #O(V^3)で任意２頂点の最短距離
        def __init__(self,n,_first_index=0):
            self.v = n
            self._first_idx=_first_index
            self.d = [[float("INF")]*(n) for _ in range(n)]
            for i in range(n):
                self.d[i][i] = 0
    
        def path(self,x,y,c):
            if x == y:
                return False
            f=self._first_idx
            self.d[x-f][y-f] = c
            self.d[y-f][x-f] = c
            return True
    
        def build(self):
            for k in range(self.v):
                for i in range(self.v):
                    for j in range(self.v):
                        self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
            return self.d
    w=WarshallFloyd(n)
    for x in range(n):
        for j in l[x]:
            w.path(x,j,1)
    d=w.build()
    ans=0
    for i in range(n):
        ans=max(ans,max(d[i]))
    print(ans+1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
S = [list(input()) for _ in range(N)]
INF = 10**12
dist = [[INF]*N for _ in range(N)]
edge = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i==j:
            dist[i][j] = 0
        if S[i][j]=='1':
            edge[i].append(j)
            dist[i][j] = 1

def WarshallFloyd(d, N):
    #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

d = WarshallFloyd(dist, N)
def dfs(v, c):
    colors[v] = c
    for nv in edge[v]:
        if colors[nv] == c:
            return False
        if colors[nv] == -1:
            if not dfs(nv, c^1):
                return False
    return True

colors = [-1]*N
if not dfs(0,0):
    print(-1)
    exit()

ans = max(max(d))
print(ans+1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
S = [list(input()) for _ in range(N)]
INF = 10**12
dist = [[INF]*N for _ in range(N)]
edge = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i==j:
            dist[i][j] = 0
        if S[i][j]=='1':
            edge[i].append(j)
            dist[i][j] = 1

def WarshallFloyd(d, N):
    #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

d = WarshallFloyd(dist, N)
def dfs(v, p, even, ret):
    even += 1
    if color[v] == -1:
        color[v] = even
    elif color[v]%2 != even%2:
        return False
    else:
        color[v] = min(color[v], even)
        return True
    for nv in edge[v]:
        if nv == p:continue
        ret &= dfs(nv, v, even, ret)
    return ret

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

ans = max(max(d))
print(ans+1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

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

def dfs(v, p, even, ret):
    even += 1
    if color[v] == -1:
        color[v] = even
    elif color[v]%2 != even%2:
        return False
    else:
        color[v] = min(color[v], even)
        return True
    for nv in edge[v]:
        if nv == p:continue
        ret &= dfs(nv, v, even, ret)
    return ret

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

ans = 0
for i in range(N):
    color = [-1]*N
    dfs(i, -1, 0, True)
    res = max(color)
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

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

# 奇数長のループがあるかどうかをチェック
node_to_idx = {}
visited = [False] * N
def dfs(node, par, n):
  global node_to_idx
  res = True
  for i, s in enumerate(S[node]):
    if s and i != par:
      if i in node_to_idx:
        idx = node_to_idx[i]
        if (n - idx) % 2:
          return False
        else:
          return True
      else:
        if visited[i]:
          continue
        visited[i] = True
        node_to_idx[i] = n
        res *= dfs(i, node, n+1)
  return res

node_to_idx[0] = 0
visited[0] = True
res = dfs(0, -1, 1)
if res:
  from scipy.sparse.csgraph import floyd_warshall
  import numpy as np
  dist = floyd_warshall(S).astype(int)
  print(dist.max() + 1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush

INF = float("inf")

# ２部グラフの判定
def bfs():
  stack = deque()
  stack.append((0, 1)) #頂点:0, 色:1
  colors[0] = 1
  while stack:
    v, c = stack.popleft()
    for i in edges[v]:
      if colors[i] == c:
        return False
      if colors[i] == 0:
        stack.append((i, -c))
        colors[i] = -c
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] # (距離, 頂点)
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

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

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
  
# 0: 未踏, 1 or -1: 踏破
colors = [0] * n

if bfs() == True:
  dist1 = dijkstra(n, edges, 0)
  nextn = dist1.index(max(dist1))
  dist2 = dijkstra(n, edges, nextn)
  rad = max(dist2)
  print(rad + 1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush

INF = float("inf")

# ２部グラフの判定
def bfs():
  stack = deque()
  stack.append((0, 1)) #頂点:0, 色:1
  colors[0] = 1
  while stack:
    v, c = stack.popleft()
    for i in edges[v]:
      if colors[i] == c:
        return False
      if colors[i] == 0:
        stack.append((i, -c))
        colors[i] = -c
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] # (距離, 頂点)
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

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

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
      edges[j].append(i)
  
# 0: 未踏, 1 or -1: 踏破
colors = [0] * n

if bfs() == True:
  dist1 = dijkstra(n, edges, 0)
  nextn = dist1.index(max(dist1))
  dist2 = dijkstra(n, edges, nextn)
  rad = max(dist2)
  print(rad + 1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush

INF = float("inf")

# ２部グラフの判定
def bfs():
  stack = deque()
  stack.append((0, 1)) #頂点:0, 色:1
  colors[0] = 1
  while stack:
    v, c = stack.pop()
    for i in edges[v]:
      if colors[i] == c:
        return False
      if colors[i] == 0:
        stack.append((i, -c))
        colors[i] = -c
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] # (距離, 頂点)
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

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

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
      edges[j].append(i)
  
# 0: 未踏, 1 or -1: 踏破
colors = [0] * n

if bfs() == True:
  dist1 = dijkstra(n, edges, 0)
  nextn = dist1.index(max(dist1))
  dist2 = dijkstra(n, edges, nextn)
  rad = max(dist2)
  print(rad + 1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush

INF = float("inf")

# ２部グラフの判定
def bfs():
  stack = deque()
  stack.append((0, 1)) #頂点:0, 色:1
  colors[0] = 1
  while stack:
    v, c = stack.pop()
    for i in edges[v]:
      if colors[i] == c:
        return False
      if not colors[i]:
        stack.append((i, -c))
        colors[v] = c
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] # (距離, 頂点)
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

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

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
      edges[j].append(i)
  
# 0: 未踏, 1 or -1: 踏破
colors = [0] * n

if bfs() == True:
  dist1 = dijkstra(n, edges, 0)
  nextn = dist1.index(max(dist1))
  dist2 = dijkstra(n, edges, nextn)
  rad = max(dist2)
  print(rad + 1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush

INF = float("inf")

# ２部グラフの判定
def bfs():
  stack = deque()
  stack.append((0, 1)) #頂点:0, 色:1
  while stack:
    v, c = stack.pop()
    colors[v] = c
    for i in edges[v]:
      if colors[i] == c:
        return False
      if not colors[i]:
        stack.append((i, -c))
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] # (距離, 頂点)
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

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

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
      edges[j].append(i)
  
# 0: 未踏, 1 or -1: 踏破
colors = [0] * n

if bfs() == True:
  dist1 = dijkstra(n, edges, 0)
  nextn = dist1.index(max(dist1))
  dist2 = dijkstra(n, edges, nextn)
  rad = max(dist2)
  print(rad + 1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush

INF = float("inf")

# ２部グラフの判定
def bfs():
  stack = deque()
  stack.append((0, 1)) #頂点:0, 色:1
  while stack:
    v, c = stack.pop()
    colors[v] = c
    for i in edges[v]:
      if not colors[i]:
        stack.append((i, -c))
      else:
        if colors[i] != -c:
          return False
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] # (距離, 頂点)
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

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

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
      edges[j].append(i)
  
# 0: 未踏, 1 or -1: 踏破
colors = [0] * n

if bfs() == True:
  dist1 = dijkstra(n, edges, 0)
  nextn = dist1.index(max(dist1))
  dist2 = dijkstra(n, edges, nextn)
  rad = max(dist2)
  print(rad + 1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush

INF = float("inf")

# ２部グラフの判定
def bfs():
  stack = deque()
  stack.append((0, 1)) #頂点:0, 色:1
  while stack:
    v, c = stack.pop()
    for i in edges[v]:
      if not colors[i]:
        stack.append((i, -c))
        colors[i] = -c
      else:
        if colors[i] != -c:
          return False
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] # (距離, 頂点)
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

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

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
      edges[j].append(i)
  
# 0: 未踏, 1 or -1: 踏破
colors = [0] * n

if bfs() == True:
  dist1 = dijkstra(n, edges, 0)
  nextn = dist1.index(max(dist1))
  dist2 = dijkstra(n, edges, nextn)
  rad = max(dist2)
  print(rad + 1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]#それぞれの要素の根を再帰的に求める

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]


def main():
    input = sys.stdin.readline
    n = int(input())
    s = [None]*n
    for i in range(n):
        s[i] = input()
    
    dist = [0]*n
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    while not_yet:
        key = not_yet.popleft()
        for i in range(key, n):
            if s[key][i] == "1" and not already[i]:
                already[i] = True
                not_yet.append(i)
                dist[i] = dist[key]+1
    
    length = max(dist)
    sub = [[] for _ in range(length+1)]
    for i in range(n):
        sub[dist[i]].append(i)
    
    for i in range(n):
        for j in range(i+1, n):
            if s[i][j] == "1":
                key = dist[i]
                if dist[j] != key-1 and dist[j] != key+1:
                    print(-1)
                    sys.exit()
    
    union = UnionFind(n)
    for i in range(1, n):
        for j in range(i+1, n):
            if s[i][j] == "1":
                union.union(i+1, j+1)
    
    key = dict()
    for i in range(1, n+1):
        for v in key:
            if union.same(i, v):
                break
        else:
            if i == 1:
                continue
            key[i] = 1
    
    for i in range(1, n):
        for v in key:
            if union.same(i, v) and key[v] < dist[i-1]:
                key[v] = dist[i-1]

    ans = [0, 0]
    for v in key.values():
        if ans[0] <= v:
            ans[0], ans[1] = v, ans[0]
        elif ans[1] <= v:
            ans[1] = v
    print(sum(ans)+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]#それぞれの要素の根を再帰的に求める

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]


def main():
    input = sys.stdin.readline
    n = int(input())
    s = [None]*n
    for i in range(n):
        s[i] = input()
    
    dist = [0]*n
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    while not_yet:
        key = not_yet.popleft()
        for i in range(key, n):
            if s[key][i] == "1" and not already[i]:
                already[i] = True
                not_yet.append(i)
                dist[i] = dist[key]+1
    
    length = max(dist)
    sub = [[] for _ in range(length+1)]
    for i in range(n):
        sub[dist[i]].append(i)
    
    for i in range(n):
        for j in range(i+1, n):
            if s[i][j] == 1:
                key = dist[i]
                if dist[j] != key-1 and dist[j] != key+1:
                    print(-1)
                    sys.exit()
    
    union = UnionFind(n)
    for i in range(1, n):
        for j in range(i+1, n):
            if s[i][j] == "1":
                union.union(i+1, j+1)
    
    key = dict()
    for i in range(1, n):
        for v in key:
            if union.same(i, v):
                break
        else:
            if i == 0:
                continue
            key[i] = 1
    
    for i in range(1, n):
        for v in key:
            if union.same(i, v) and key[v] < dist[i-1]:
                key[v] = dist[i-1]

    ans = [0, 0]
    for v in key.values():
        if ans[0] <= v:
            ans[0], ans[1] = v, ans[0]
        elif ans[1] <= v:
            ans[1] = v
    print(sum(ans)+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    S = [[int(x) for x in sys.stdin.readline().rstrip()] for _ in range(N)]

    max_k = 0

    for i in range(N):
        node = [-1] * N
        q = collections.deque()
        q.append((i,1))
        node[i] = 1
        s = copy.deepcopy(S)
        f = True
        while q:
            v,d = q.popleft()
            for j in range(N):
                if s[i][j] == 0: continue
                if node[j] == d+1 or node[j] == d-1: continue
                if node[j] < 0:
                    node[j] = d+1
                    q.append((j,d+1))
                else:
                    f = False
                    break
            else:
                continue
            break
        if f: max_k = max(max_k,max(node))
    if max_k == 0:
        print(-1)
    else:
        print(max_k)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# キュー
from collections import deque

n = int(input())
links = [[] for _ in range(n+1)]
for i in range(1,n+1):
    ss = input()
    for j,s in enumerate(ss,1):
        if(s=='1'):
            links[i].append(j)

ans = -1
for i in range(1,n+1):
    ng_flag = False

    depth = [-1] * (n+1)
    depth[i] = 1
    max_depth = 1
    d = deque()
    d.append(i)
    while(d):
        now = d.pop()
        for j in links[now]:
            if(depth[j] == -1):
                depth[j] = depth[now] + 1
                d.append(j)
                max_depth = max(max_depth, depth[j])
            else:
                if(abs(depth[j] - depth[now]) != 1):
                    ng_flag = True
                    break
        if(ng_flag):
            break
    if(not ng_flag):
        ans = max(ans, max_depth)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
mat=[[10**18 for i in range(n+1)] for j in range(n+1)]
#ab = [[] for i in range(n)]

for i in range(n):
    si = input()
    for j in range(n):
        if int(si[j]) == 1:
            #print(i,j)
            mat[i+1][j+1] = 1

print(mat)

#N,M=map(int,input().split())

for i in range(n+1):
	mat[i][i]=0

for i in range(1,n+1):
	for x in range(1,n+1):
		for y in range(1,n+1):
			mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])

ans = 0

for i in range(n):
    for j in range(i+1,n):
        ans = max(ans,mat[i][j])
        
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
ab = [[] for i in range(n)]

for i in range(n):
    si = input()
    for j in range(n):
        if int(si[j]) == 1:
            #print(i,j)
            ab[i].append(j)

#print(ab)

print(-1)
exit()

st = -1

for i in range(n):
    if len(ab[i]) == 1:
        st = i
        break
    
if st == -1:
    print(-1)
    exit()
    
q = deque()
q.appendleft(st)

check = [0]*(n)
check[st] = 1

ans = 0
#print(st)

while len(q) > 0:
    #print(q)
    for i in range(len(q)):
        tmp = q.popleft()
        check[tmp] = 1
        cnt = 0
        #print(tmp,111111)
        li = []
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                q.append(ab[tmp][j])
                li.append(ab[tmp][j])
        """        
        for k in range(len(li)):
            for l in range(len(ab[li[k]])):
                for m in range(k+1,len(li)):
                    print(k,m)
                    if ab[li[k]][l] == li[m]:
                        print(-1)
                        exit()
                
        """
    ans += 1
        
print(ans)