Problem:


Score : 500 points

Problem Statement

Given is a connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the edges are described by a grid of characters S.
If S_{i,j} is 1, there is an edge connecting Vertex i and j; otherwise, there is no such edge.

Determine whether it is possible to divide the vertices into non-empty sets V_1, \dots, V_k such that the following condition is satisfied. If the answer is yes, find the maximum possible number of sets, k, in such a division.

Every edge connects two vertices belonging to two "adjacent" sets. More formally, for every edge (i,j), there exists 1\leq t\leq k-1 such that i\in V_t,j\in V_{t+1} or i\in V_{t+1},j\in V_t holds.

Constraints

2 \leq N \leq 200

S_{i,j} is 0 or 1.

S_{i,i} is 0.

S_{i,j}=S_{j,i}

The given graph is connected.

N is an integer.

Input

Input is given from Standard Input in the following format:

N
S_{1,1}...S_{1,N}
:
S_{N,1}...S_{N,N}

Output

If it is impossible to divide the vertices into sets so that the condition is satisfied, print -1.
Otherwise, print the maximum possible number of sets, k, in a division that satisfies the condition.

Sample Input 1

2
01
10

Sample Output 1

2

We can put Vertex 1 in V_1 and Vertex 2 in V_2.

Sample Input 2

3
011
101
110

Sample Output 2

-1

Sample Input 3

6
010110
101001
010100
101000
100000
010000

Sample Output 3

4



Sample input:
2
01
10


Sample output:
2

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc039/submissions/14648645


INF = 10 ** 8
N = int(input())
S = []
for _ in range(N):
    S.append(list(map(int, list(input()))))

# Is G bipartite ?

color = [0] * N
def dfs(x, c):
    color[x] = c
    for i in range(N):
        # 色が同じ = 二部グラフじゃない
        if S[x][i] == 1 and color[i] == c:
            return False
        # 色はついていないけど，反転した二部グラフ判定に失敗 = 二部グラフじゃない
        if S[x][i] == 1 and color[i] == 0 and not dfs(i, -c):
            return False
    # 二部グラフ
    return True

for i in range(N):
    if color[i] == 0 and not dfs(i, 1):
        print(-1)
        exit()

# ワーシャルフロイド
d = [[INF if S[i][j] == 0 else S[i][j] for i in range(N)] for j in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

# 解の計算: 直径(max) + 1
ans = 0
for i in range(N):
    for j in range(N):
        if d[i][j] != INF:
            ans = max(ans, d[i][j] + 1)
print(ans)

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np
from collections import deque

def main():
	n=II()
	G=[]
	for i in range(n):
		G.append(list(map(int,input())))
		#print(G)

	ans=0
	for i in range(n):
		v=[-2]*n
		v[i]=0
		q=deque()
		q.append([i,0])

		while q:
			now,d=q.popleft()
			for j in range(n):
				if G[now][j]==1:
					if v[j]==-2:
						v[j]=d+1
						q.append([j,d+1])
					elif v[j]==d-1 or v[j]==d+1:
						continue
					else:
						print(-1)
						exit(0)
		ans=max(ans,max(v)+1)


	print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

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

def bfs():
    color = [0]*N
    color[0] = 1
    q = deque([0])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
            else:
                if color[nv]==color[v]:
                    return False
    
    return True
    
def warshall_floyd():
    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])
            
N = int(input())
S = [input()[:-1] for _ in range(N)]
G = [[] for _ in range(N)]

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

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

d = [[10**18]*N for _ in range(N)]

for i in range(N):
    d[i][i] = 0
    
for i in range(N):
    for j in range(i+1, N):
        if S[i][j]=='1':
            d[i][j] = 1
            d[j][i] = 1

warshall_floyd()
ans = 0

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

print(ans+1)

Submission status: Accepted

Solution code:
#AGC039-B
"""
二部グラフで無いなら分割はできない。
二部グラフの場合、頂点間の最も長い距離＋１
が答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
g = [[float("inf")]*n for i in range(n)]
g2 = [[] for i in range(n)] #g[i]:点iに隣接している点のリスト
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    for j in range(n):
        if s[j] == "1":
            g[i][j] = 1
            g2[i].append(j)
            g2[j].append(i)
for i in range(n):
    g[i][i] = 0 #自分自身への距離は0とする

def warshall_floyd(d): #隣接行列を入れる
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

FW = warshall_floyd(g)

color = [0] * n #color[i]:点iの色(1 or -1)。但し塗られていないときは0とする

def f(v,c,g):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(g[v])):
        if color[ g[v][i] ] == c:
            return False
        elif color[ g[v][i] ] == 0 and not f(g[v][i],-c,g2):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True

k = 1 #判定　1ならYes -1ならNo
for i in range(n):
    if color[i] == 0:
        if not f(i,1,g2):
            k = -1

if k != 1:
    print(-1)
else:
    ans = 0
    for i in FW:
        for j in i:
            if j != float("inf"):
                ans = max(ans,j)
    print(ans+1)

Submission status: Accepted

Solution code:
import sys

INF = 10 ** 8
N = int(input())
S = []
for _ in range(N):
    S.append(list(map(int,list(input()))))

color = [0] * N

def dfs(x, c):
    color[x] = c
    for i in range(N):
        if S[x][i] and color[i] == c:
            return False
        if S[x][i] and color[i] == 0 and not dfs(i, -c):
            return False
    return True

for i in range(N):
    if color[i] == 0 and not dfs(i, 1):
        print(-1)
        sys.exit()

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i != j:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())

G = {k: [] for k in range(N)}
for i in range(N):
    S = input()
    for j in range(N):
        if S[j] == '1':
            G[i].append(j)
            G[j].append(i)


def bfs(i):
    visited = [-1 for _ in range(N)]
    visited[i] = 1
    M = 1
    que = deque([(i, -1)])

    while que:
        ci, p = que.popleft()

        for ni in G[ci]:
            if ni != p:
                if visited[ni] != -1:
                    if (visited[ci]+1-visited[ni]) % 2 == 1:
                        print(-1)
                        exit()
                else:
                    que.append((ni, ci))
                    visited[ni] = visited[ci]+1
                    M = max(M, visited[ni])

    return M


ans = 0
for i in range(N):   # start node
    ans = max(ans, bfs(i))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=[list(map(int,list(input()))) for i in range(N)]
VE=[[] for i in range(N)]
for i in range(N):
  for j in range(N):
    if S[i][j]:
      VE[i].append(j)
C=[0]*(N*N+1)
def ni(v,c):
  global S,C,N
  C[v]=c
  for i in range(len(VE[v])):
    if C[VE[v][i]]==c:
      return False
    if C[VE[v][i]]==0 and not(ni(VE[v][i],-c)):
      return False
  return True

if not(ni(0,1)):
  print(-1)
  exit()
INF=10**12
D=[[INF]*N for i in range(N)]
for i in range(N):
  D[i][i]=0
  for j in range(len(VE[i])):
    D[i][VE[i][j]]=1
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])
P=0
for i in range(N):
  P=max(P,max(D[i]))
print(P+1)

Submission status: Accepted

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):
    edges[i] = []
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == "1":
            edges[i].append(j)
            edges[j].append(i)

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

Submission status: Accepted

Solution code:
n = int(input())
link = [[] for _ in range(n)]
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            link[i].append(j)

from collections import deque
Q = deque()
Q.append([0,0])
visited=[-1]*n
visited[0]=0 # 0 or 1
while Q:
    now,color = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            if visited[nxt] == (color+1)%2:
                continue
            else:
                print(-1)
                exit()
        visited[nxt]=(color+1)%2
        Q.append([nxt,(color+1)%2])

ans=0
for i in range(n):
    Q = deque()
    Q.append([i,0])
    visited=[-1]*n
    visited[i]=1
    while Q:
        now,cnt = Q.popleft()
        for nxt in link[now]:
            if visited[nxt]!=-1:
                continue
            visited[nxt]=cnt+1
            Q.append([nxt,cnt+1])
    mx = max(visited)
    ans=max(ans,mx)

print(ans+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

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


def warshall_floyd(n, d):
    # d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


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

    def bfs(start, S):
        visited = [False] * N
        visited[start] = True
        group = [-1] * N
        group[start] = 0
        q = deque([(start, 0)])
        while q:
            n, g = q.popleft()

            for i in range(N):
                if S[n][i] == "1":
                    if visited[i]:
                        if abs(group[i] - g) != 1:
                            return -1
                        else:
                            continue
                    else:
                        group[i] = g + 1
                        visited[i] = True
                        q.append((i, g + 1))
                else:
                    continue
        n_group = 1
        for i in range(N):
            if group[i] == -1:
                return -1
            if n_group < group[i] + 1:
                n_group = group[i] + 1
        return n_group

    answer = -1
    for i in range(N):
        n_group = bfs(i, S)
        if n_group > answer:
            answer = n_group
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    def bfs(start):
        q = deque([start])
        visited = [-1 for _ in range(N)]
        visited[start] = 0
        prev = [set() for _ in range(N)]
        prev[start].add(-1)

        while q:
            cur = q.popleft()

            for nex in range(N):
                if cur == nex:
                    continue

                if S[cur][nex] == "0":
                    continue

                if nex in prev[cur]:
                    continue

                if visited[nex] == visited[cur] + 1:
                    prev[nex].add(cur)
                    continue

                if visited[nex] > 0:
                    return -1

                visited[nex] = visited[cur] + 1
                prev[nex].add(cur)
                q.append(nex)

        return max(visited) + 1

    # 端を決め打ちして全探索
    ans = -1
    for i in range(N):
        tmp = bfs(i)
        if ans < tmp:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n = int(input())
    s = [list(input()) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if (i==j):
                s[i][j] = 0
                continue
            if (s[i][j]=="1"):
                s[i][j] = 1
            else:
                s[i][j] = float("inf")
    #print(s)
    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)
    w = [[] for _ in range(n)]
    m = [s[0][0],0,0]
    for i in range(n):
        for j in range(n):
            if (s[i][j] > m[0]):
                m = [s[i][j],i,j]
    #print(m)
    for i in range(n):
        w[s[m[1]][i]].append(i)
    #print(w)
    for i in range(n):
        if (len(w[i])>=2):
            for j in range(len(w[i])-1):
                for k in range(j+1,len(w[i])):
                    if (s[w[i][j]][w[i][k]]==1):
                        print(-1)
                        exit()
    print(m[0]+1)
    

if __name__=="__main__":
    main()

Submission status: Accepted

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)]
    
    
    for i in range(N):
        S=list(input())
        for j in range(N):
            if S[j]=="1":
                adj[i].append(j)
            
    import queue
    
    ans=0
    
    
    def bfs(x):
        q=queue.Queue()
        q.put((x,1))
        V=[-1]*N
        V[x]=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))
                if abs(V[nv]-V[v])!=1:
                    flag=1
                    break
                
        if flag:
            return -1
        return max(V)
    
    ans=0
    for i in range(N):
        temp=bfs(i)
        if temp==-1:
            ans=-1
            break
        ans=max(ans,temp)
    print(ans)
    
                    

        
        

main()

Submission status: Accepted

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, c=0):
    color[v] = c
    for v2 in edges[v]:
        if color[v2] != -1:
            if color[v] == color[v2]:
                global is_ok
                is_ok = 0
            continue
        dfs(v2, color[v] ^ 1)


color = [-1]*n
is_ok = 1
dfs(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 is_ok:
    ans = 0
    for i in range(n):
        dist = bfs(i)
        x = max(dist)
        if ans < x:
            ans = x
    print(ans+1)
else:
    print(-1)

Submission status: Accepted

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):
    for v2 in edges[v]:
        if color[v2] != -1:
            if color[v] == color[v2]:
                global is_ok
                is_ok = 0
            continue
        color[v2] = color[v] ^ 1
        dfs(v2)


color = [-1]*n
color[0] = 0
is_ok = 1
dfs(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 is_ok:
    ans = 0
    for i in range(n):
        dist = bfs(i)
        x = max(dist)
        if ans < x:
            ans = x
    print(ans+1)
else:
    print(-1)

Submission status: Accepted

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):
    ans = 0
    for i in range(n):
        dist = bfs(i)
        x = max(dist)
        if ans < x:
            ans = x
    print(ans+1)
else:
    print(-1)

Submission status: Accepted

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
                    if group[cur_v] == group[next_v]:
                        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: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, shortest_path

def main():
    n = int(input())
    s = np.array([list(input()) for _ in range(n)], dtype=np.int64)
    wf = csgraph_from_dense(s)
    wf = shortest_path(wf, method="FW")
    idx = -1
    tmp = 0
    for i in range(n):
        for j in range(n):
            if wf[i][j] > tmp:
                idx = i
                tmp = wf[i][j]
    st = [set() for _ in range(int(tmp)+1)]
    f = True
    for j in range(n):
        x = int(wf[idx][j])
        for v in st[x]:
            if s[j][v] != 0:
                f = False
        st[x].add(j)
    if f:
        print(int(tmp)+1)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

from collections import deque

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

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

INF = float("inf")
def solve(s):
    dist = [INF] * N
    dist[s] = 0
    union = [[] for _ in range(N)]
    union[0].append(s)

    q = deque()
    q.append(s)
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[curr] + 1 >= dist[nxt]:
                continue

            dist[nxt] = dist[curr] + 1
            union[dist[nxt]].append(nxt)
            q.append(nxt)

    return dist, union



d, u = solve(0)

for i in range(N):
    if len(u[i]) > 1:
        for a in u[i]:
            for b in u[i]:
                if S[a][b] == "1":
                    print(-1)
                    exit()

ans = 0
for i in range(N):
    d, _ = solve(i)
    ans = max(ans, max(d) + 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict, deque #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N = ii()
#S = [list(map(int, list(input()))) for _ in range(N)]
rel = [[] for _ in range(N)]

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

flag = [0]*N
ans = 0

for i in range(N):
    flag = [0]*N
    que = deque([i])
    add = 0
    flag[i] = 1
    while que != deque([]):
        node = que.popleft()
        for nn in rel[node]:
            if not flag[nn]:
                que.append(nn)
                flag[nn] = flag[node] + 1
    ans = max(ans, max(flag))

for i in range(N):
    for t in rel[i]:
        if abs(flag[t] - flag[i]) != 1:
            print(-1)
            exit()

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[[j for j,k in enumerate(input())if k=="1"]for i in range(n)]
import sys
sys.setrecursionlimit(10**9)
color=[0]*n
def nibu(v,c):
    #True->nibugrahu
    color[v]=c
    for i in l[v]:
        if color[i]==c:return False
        elif color[i]==0 and not nibu(i,-c):
            return False
    return True
if not nibu(0,1):
    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: Accepted

Solution code:
n=int(input())
l=[[j for j,k in enumerate(input())if k=="1"]for i in range(n)]
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(2*n)
for i in range(n):
    for ne in l[i]:
        uf.unite(i,ne+n)
        uf.unite(i+n,ne)
notnibu=0
for i in range(n):
    notnibu|=uf.same(i,i+n)
if notnibu:
    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: Accepted

Solution code:
n=int(input())
s=[list(map(int,list(input()))) for _ in range(n)]
g=[[]for _ in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    if s[i][j]==1:
      g[i].append(j)
      g[j].append(i)
from collections import deque
def bfs(i):#頂点iをグループ１とする。
  seen=[0]*n
  seen[i]=1
  todo=deque([[i,-1]])
  while todo:
    t,p=todo.popleft()
    l=g[t]
    for li in l:
      if li==p:
        continue
      if seen[li]==0:
        seen[li]=seen[t]+1
        todo.append([li,t])
      elif abs(seen[li]-seen[t])==1:
        pass
      else:
        return -1
  return max(seen)
ans=-1
for i in range(n):
  ans=max(bfs(i),ans)
print(ans)

Submission status: Accepted

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 = 0
for e in d:
    ans = max(ans, max(e))
print(ans+1)

Submission status: Accepted

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)

ans = 0
import queue
for i in range(N):
    q = queue.Queue()
    q.put(i)
    nums = [-1]*N
    nums[i] = 1
    while not q.empty():
        v = q.get()
        flag = True
        for nv in edge[v]:
            if nums[nv] == -1:
                nums[nv] = nums[v] + 1
                q.put(nv)
            elif nums[nv]%2 != (nums[v]+1)%2:
                flag = False
                break
        if not flag:
            break
    if flag:
        ans = max(ans, max(nums))
print(ans) if ans != 0 else print(-1)

Submission status: Accepted

Solution code:
n = int(input())

g = [[] * n for i in range(n)]

for i in range(n):
  s = input()
  for j,si in enumerate(s):
    if si == '1':
      g[i].append(j)
      
from collections import deque

def bfs(s):
  que = deque()
  que.append((s,1))
  a[0].append(s)
  chk = [False]*n
  chk[s] =True
  cnt = 1
  while que:
      now,p = que.popleft()
      if cnt == n:
        break
      for i in g[now]:
          if not chk[i]:
            a[p].append(i)
            chk[i] = True
            cnt += 1
            que.append((i,p+1))
          
ans = -1
for i in range(n):
  a = [[] for i in range(n+1)]
  bfs(i)
  cc = 0
  b = False
  #print(a)
  for j in a:
    if j == []:
      ans = max(ans,cc)
      break
    cc += 1
    for k in j:
      #print(set(g[k]), set(j), j,i)
      if set(g[k]) & set(j) != set():
        b = True
        break
    if b:
      break
  
print(ans)