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:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
G = [None] * N
for i in range(N):
    G[i] = list(map(int, input()))

nodes = [[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j]:
            nodes[i].append(j)
            nodes[j].append(i)

def bfs(start):
    visited = list2d(N, N, 0)
    group = [-1] * N
    que = deque()
    que.append((start, 1))
    mx = 0
    while que:
        u, cnt = que.popleft()
        if group[u] == -1:
            group[u] = cnt
        elif group[u] == cnt:
            continue
        else:
            return -1
        mx = max(mx, cnt)
        for v in nodes[u]:
            if visited[u][v]:
                continue
            visited[u][v] = visited[v][u] = 1
            que.append((v, cnt+1))
    return mx

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

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
neighbors = defaultdict(list)
for i in range(n):
    s = list(map(int, list(input())))
    for j in range(n):
        if s[j] == 1:
            neighbors[i].append(j)

def dfs(v0):
    dist = {}
    dist[v0] = 0
    visited = {}
    f = [v0]
    while len(visited) != n:
        nxt_f = []
        for v in f:
            for nn in neighbors[v]:
                if nn in visited:
                    continue
                if nn in dist:
                    if dist[nn] != dist[v] + 1:
                        # contradiction
                        return False
                else:
                    dist[nn] = dist[v] + 1
                    nxt_f.append(nn)
        for v in f:
            visited[v] = True
        f = nxt_f
    return max(dist.values()) + 1

kmax = -1
for v0 in range(n):
    k = dfs(v0)
    if k:
        kmax = max(kmax, k)
print(kmax)

Submission status: Accepted

Solution code:
N = int(input())

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

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

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

baseMod = [d % 2 for d in dist[0]]

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

ans = max([max(D) for D in dist]) + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

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

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

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

ans = max([max(D) for D in minDist]) + 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
field = [input() for _ in range(N)]

from collections import deque
# 木構造を作る
G = [[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if field[i][j] == "1":
            if j not in G[i]:
                G[i].append(j)
            if i not in G[j]:
                G[j].append(i)

ans = 0
# 木をBFSをする
for i in range(N):
    category = [-1] * N
    category[i] = 0
    q = deque([i])
    while len(q) > 0:
        a = q.popleft()
        Vs = G[a]
        c = category[a]
        # print(c)
        for u in Vs: # 頂点以外の要素がグラフにあるときはここ
            if category[u] == -1:
                q.append(u)
                category[u] = c+1
            elif category[u] == c:
                print(-1)
                exit()
    ans = max(ans, len(set(category)))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[[int(s) for s in input()] for _ in range(n)]
    B=[a[:] for a in A]
    from itertools import product
    # 対角以外の0をINF
    for i,j in product(range(n),repeat=2):
        if i==j: continue
        if B[i][j]==0: B[i][j]=INF
    # Warshall-Floyd
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])
    # 直径となる始点を1つ取得
    dia=0; p=0
    for i,j in product(range(n),repeat=2):
        if dia<B[i][j]:
            dia=B[i][j]
            p=i
    for i,j in product(range(n),repeat=2):
        if i>=j: continue # i<j
        if A[i][j]:
            if abs(B[i][p]-B[j][p])!=1:
                print(-1)
                return
    print(dia+1)
resolve()

Submission status: Accepted

Solution code:
from queue import Queue


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


    def bfs(s):
        WHITE = 0
        GRAY = 1
        BLACK = 2

        color = [WHITE] * n
        d = [-1] * n
        q = Queue()
        q.put(s)
        color[s] = GRAY
        d[s] = 0
        while not q.empty():
            u = q.get()
            color[u] = BLACK
            for v, edge in enumerate(S[u]):
                if edge and color[v] == BLACK and d[v] + 1 != d[u]:
                    return -1
                if edge and color[v] == WHITE:
                    q.put(v)
                    color[v] = GRAY
                    d[v] = d[u] + 1

        return max(d) + 1

    cnt = -1
    for i in range(n):
        cnt = max(cnt, bfs(i))

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]


n = int(input())

edge = [[] for _ in [0]*n]
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			edge[i].append(j)


res = -1
for start in range(n):
	par = [-1]*n
	used = [False]*n
	used[start] = True

	tank = set()
	new = {start}
	judge = True

	while len(new) != 0 and judge:
		tank = set()
		for e in new:
			for go in edge[e]:
				if not used[go]:
					if same(e,go):
						judge = False
					else:
						tank.add(go)
		for e in new:
			used[e] = True
		if len(tank) >= 1:
			qqq = list(tank)[0]
			for e in tank:
				unite(e,qqq)
		new = tank

	if judge:
		cnt = 0
		for e in par:
			if e < 0:
				cnt += 1
		res = max(cnt,res)
print(res)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import*
n=int(input())
con=[[]for _ in range(n)]
col=[-1]*n
G=[]
for i in range(n):
	x=input()
	for j,c in enumerate(x):
		if c=="1":
			con[i].append(j)
			con[j].append(i)
	G.append([c=="1" or float("inf") for c in x])
q=[0]
col[0]=0
while q:
	cur=q.pop(0)
	for nxt in con[cur]:
		if col[nxt]==col[cur]:
			print(-1)
			exit()
		if col[nxt]<0:
			col[nxt]=1-col[cur]
			q.append(nxt)
print(int(np.amax(floyd_warshall(G,0)+1)))

Submission status: Accepted

Solution code:


N = int(input())
g = [[] for i in [0]*(N+1)]

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

def max_len(g,v):
    visited = [False]*(N+1)
    l = 1
    ls = [v]
    pre_v = []
    while(ls):
        new_ls = []
        for cv in ls:
            for nv in g[cv]:
                if visited[nv] and not nv in pre_v:
                    return -1
                if not visited[nv] and not nv in new_ls:
                    new_ls.append(nv)
            visited[cv] = True
        if new_ls:
            l += 1
        pre_v = ls
        ls = new_ls
    return l

m = -1 
for i in range(1,N+1):
    m = max(m,max_len(g,i))
print(m)

Submission status: Accepted

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

ans = -1
for i in range(N):
    nodes = [-1]*N
    nodes[i] = 0
    q = deque([])

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

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
b=[[]for _ in range(n)]
d=[]
inf=float('inf')
inf=float('inf')
for i in range(n):
  s=input()
  c=[]
  for j in range(n):
    if s[j]=="1":
      b[i]+=[(i,j)]
    c.append(1 if s[j]=="1" else inf)
  d.append(c)
def warshall_floyd(d):
    for i in range(n):d[i][i]=0
    #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=warshall_floyd(d)
x=[-1]*n
x[0]=0
Q=b[0]
while Q:
  p=[]
  for i,j in Q:
    if x[j]<0:
      x[j]=x[i]^1
      p+=b[j]
    elif x[i]==x[j]:print(-1);exit()
  Q=p
z=0
for i in d:
  for j in i:
    if j!=float("inf"):z=max(j,z)
print(z+1)

Submission status: Accepted

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

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

def dfs(x):
  L = [0] * N
  L[x] = 1
  S = [x]
  K = [0] * N
  cnt = 0
  while S:
    cnt += 1
    T = [0] * N
    ST = []
    while S:
      t = S.pop()
      T[t] = 1
      for i in R[t]:
        if L[i] == 1:
          if K[i] == 0:
            return -1
          else:
            L[i] = 1
        else:
          L[i] = 1
          K[i] = 1
          ST.append(i)
    S = ST
    K = T
  return cnt

ma = -1
for i in range(N):
  ma = max(ma, dfs(i))

print(ma)

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

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

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

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

max_num = 0
for root in range(N):
	group = [-1]*N
	group[root] = 0
	group_n = [root]
	num = 1
	judge = 0
	while len(group_n) > 0:
		group_next = []
		for node in group_n:
			for node_next in graph[node]:
				if group[node_next] == -1:
					group[node_next] = num
					group_next.append(node_next)
				elif group[node_next] == num - 1:
					judge = 1
					break
			if judge == 1:
				break
		if judge == 1:
			break
		else:
			num += 1
			group_n = copy.deepcopy(group_next)
	if judge == 0:
		max_num = max(max_num, num)

if max_num > 0:
	print(max_num - 1)
else:
	print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

"""
・二部グラフが必要
・最長の最短距離 + 1 で上からbound
・2部グラフならbfs木が満たすのでよい
"""

N = int(readline())
S = np.frombuffer(read(),'S1').reshape(N,-1)[:,:N].astype(np.int64)

graph = csgraph_from_dense(S)

dist_mat = floyd_warshall(graph).astype(np.int32)

max_d = dist_mat.max()

# 二部グラフの判定
A = np.where(dist_mat[0]%2 == 0)
B = np.where(dist_mat[0]%2 == 1)
bl = (S[A][:,A] == 0).all() and (S[B][:,B] == 0).all()

answer = max_d + 1 if bl else -1
print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def Floyd_Warshall(dist):
    num_of_vertices = n
    for k in range(num_of_vertices):
        for i in range(num_of_vertices):
            for j in range(num_of_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k]+ dist[k][j])


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

#n,m = [int(i) for i in readline().split()]

n = int(input())


dist = [None for i in range(n)]
INF = float("inf")

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

for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == "1":
            g[i].append(j)
    dist[i] = [1 if j == "1" else INF for j in s]

for i in range(n):
    dist[i][i] = 0


from collections import deque
def bfs(g,root):
        
    q = deque()
    memo = [-1]*(len(g))
    """初期化、キューに入れて訪問済みにする"""
    memo[root] = 0
    q.append(root)
    """BFS"""
    while q: #キューが空になるまで
        v = q.popleft() #キューから情報を取り出す
        for c in g[v]:
            if memo[c] >= 0:
                if memo[c] ==  memo[v] ^ 1:
                    continue
                else:
                    return False
            memo[c] = memo[v] ^ 1
            q.append(c)
    return True

if bfs(g,0):
    #print(dist)
    Floyd_Warshall(dist)
    #print(dist)
    ans = 0
    for i in range(n):
        for j in range(n):
            ans = max(ans,dist[i][j])
    print(ans+1)
            

else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

ans = 0
for i in range(N):
    que = deque()
    que.append(i)
    seen = [0] * N
    seen[i] = 1
    while que:
        v = que.pop()
        for u in adj[v]:
            if seen[u] == 0:
                que.appendleft(u)
                seen[u] = -seen[v] - 1 if seen[v] > 0 else -seen[v] + 1
            else:
                if seen[v] * seen[u] > 0:
                    print(-1)
                    exit()
    ans_i = max(max(seen), -min(seen))
    ans = max(ans, ans_i)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    k = I()
    n = len(s)
    for i in range(n):
        if s[i] != s[0]:
            break
    else:
        print((k*n)>>1)
        return
    s += s
    t = s[i-1]
    for j in range(n)[::-1]:
        if s[j] != t:
            break
    s = s[i:j+1]
    ans = (i>>1)+((n-1-j)>>1)+((n-1-j+i)>>1)*(k-1)
    i = 0
    n = len(s)
    while i < n:
        t = s[i]
        l = 0
        while i < n and t == s[i]:
            i += 1
            l += 1
        ans += (l >> 1)*k
    print(ans)
    return

#B
def B():
    n = I()
    s = [list(map(int, input())) for i in range(n)]
    v = [[] for i in range(n)]
    for i in range(n):
        for j  in range(i+1,n):
            if s[i][j]:
                v[i].append(j)
                v[j].append(i)
    bfs = [-1]*n
    q = deque([0])
    q[0] = 0
    f = 1
    while f and q:
        x = q.popleft()
        nb = 1-bfs[x]
        for y in v[x]:
            if bfs[y] >= 0:
                if bfs[y] != nb:
                    f = 0
                    break
            else:
                bfs[y] = nb
                q.append(y)
    if not f:
        print(-1)
        return
    ans = -1
    for i in range(n):
        bfs = [0]*n
        bfs[i] = 1
        q.append(i)
        while q:
            x = q.popleft()
            nb = bfs[x]+1
            for y in v[x]:
                if not bfs[y]:
                    bfs[y] = nb
                    q.append(y)
        m = max(bfs)
        if m > ans:
            ans = m
    print(ans)
    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

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

E = [[] for _ in [0]*N]
for i,row in enumerate(S):
    for j,s in enumerate(row):
        if s :
            E[i].append(j)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

ans = -1
for i in range(N):
    d = dist_bfs(N,E,i)
    ans = max(ans,max(d)+1)
#check
for i,e in enumerate(E):
    for j in e:
        if j > i : break
        if abs(d[i] - d[j]) != 1 : ans = -1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
e_list = [[] for i in range(N)]
for i in range(N):
    S = input()
    for j in range(i+1,N):
        if S[j]=="1":
            e_list[i].append(j)
            e_list[j].append(i)

from collections import deque

ans = -1
for vi in range(N):
    flag = True
    Q = deque([vi])
    min_path_list = [10**27]*N #問題によりここを変える
    min_path_list[vi] = 0
    max_path = 0
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if min_path_list[v1]==10**27:
                Q.appendleft(v1)
                min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
                max_path = max(max_path,min_path_list[v1])
            elif min_path_list[v1]!=min_path_list[v]+1 and min_path_list[v1]!=min_path_list[v]-1:
                flag=False
                break
    if flag:
        ans = max(max_path,ans)

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for _ in range(N):
    S.append(list(map(int, input())))

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

def bfs(pt,v):
    used = [[False]*N for _ in range(N)]
    d = [-1]*N
    d[v] = 0
    q = [v]
    c = 1
    while q:
        flag = False
        q1 = []
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    used[i][j] = True
                    used[j][i] = True
                    flag = True
                    d[j] = c
                    q1.append(j)
                else:
                    if used[i][j]==False and d[j]!=c:
                        return -float('inf')
                    else:
                        if used[i][j]==False and d[j]==c:
                            used[i][j] = True
                            used[j][i] = True
        q = q1
        if flag:
            c += 1
    return c

ans = -1
for i in range(N):
    x = bfs(pt,i)
    if x>ans:
        ans = x

print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

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

graph = [set() for _ in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j] == '1':
            graph[i].add(j)
            graph[j].add(i)


def count(v1):
    # bfs
    groups = [INF] * N
    groups[v1] = 0

    vs = [v1]
    g = 0
    while vs:
        nexts = set()
        for v in vs:
            nexts |= graph[v]
        vs = set()
        for u in nexts:
            if groups[u] not in [g - 1, INF]:
                return -1
            if groups[u] == INF:
                groups[u] = g + 1
                vs.add(u)
        g += 1
    return g


# グループ 1 にするやつを決め打つ
# つながってるやつは+1
ans = -1
for v1 in range(N):
    ans = max(ans, count(v1))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
S = [list(map(int,list(input))) for _ in range(N)]
G = {i:[] for i in range(N)}
for i in range(N):
    for j in range(N):
        if S[i][j]==1:
            G[i].append(j)
que = deque([(0,-1)])
hist = [0 for _ in range(N)]
hist[0]=1
flag = 0
A = [0]
while que:
    x,z = que.popleft()
    A.append(x)
    for y in G[x]:
        if y!=z:
            if hist[y]==1:
                flag = 1
                break
            hist[y]=1
            que.append((y,x))
    if flag==1:break
if flag==1:
    print(-1)
else:
    a = A[-1]
    que = deque((a,0))
    hist = [0 for _ in range(N)]
    hist[a]=1
    cnt = 0
    while que:
        x,d = que.popleft()
        for y in G[x]:
            if hist[y]==0:
                hist[y]=1
                que.append((y,d+1))
                cnt = d+1
    print(cnt)

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
s=[input() for i in range(n)]

g=[[]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j]=="1":
            g[i].append(j)

# print(g)
ans=-float('inf')
for i in range(n):
    itta=[0]*n
    d=deque([i])
    cnt=0
    while d:
        # print(d)
        cnt+=1
        for i in range(len(d)):
            tmp=d.popleft()
            if itta[tmp]==0:
                itta[tmp]=cnt
                for j in range(len(g[tmp])):
                    if itta[g[tmp][j]]==0:
                        d.append(g[tmp][j])
            elif itta[tmp]==cnt:
                continue
            else:
                cnt=-float('inf')
    ans=max(ans,cnt)
if ans==-float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
g=[[] for i in range(N)] 
cnt=0
for i in range(N):
  s=input()
  for j in range(N):
    if s[j]=='1':
      g[i].append(j)
      cnt+=1
w=cnt//2

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

def f(v,c):
    #頂点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):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True

def warshall(d,n):
  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

k=1
for i in range(N):
  if color[i]==0:
    if not f(i,1):
      k=-1

if k==0:
  print(-1)
else:
  d=[[float('inf')]*N for i in range(N)]
  for i in range(N):
    for j in g[i]:
      d[i][j]=1
  for i in range(N):
    d[i][i]=0
  A=warshall(d,N)
  ans=0
  for i in range(N):
    for j in range(N)
      ans=max(ans,d[i][j])
  print(ans+1)

Submission status: Runtime Error

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()
ana=0
for s in range(n):
    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)
    ans=max(ans,max(v))
print(ans)

Submission status: Runtime Error

Solution code:
# AGC039B - Graph Partition (153ms)
from collections import deque


def is_bipartite() -> bool:
    stack, color = [(1, 1)], [0] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = -cur_color
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if not color[u]:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(source: int) -> int:
    queue = deque([source])
    dist = [0] * (N + 1)  # dist[i] := distance from V_source to V_i
    dist[start] = 1
    while queue:
        v = queue.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                queue.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()