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

N = int(input())

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

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

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

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

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

    ans = max(ans, len(G))

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

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

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

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

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

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

    ans = max(ans, len(G))

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

Submission status: Wrong Answer

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

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

USE=[-1]*N

from collections import deque

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

flag=1

while Q:
    x=Q.pop()

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

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

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

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

while Q:
    x=Q.pop()
    for i in range(N):
        if S[x][i]=="1":
            if USE[i]==0:
                H[i]=H[x]+1
                USE[i]=1
                Q.append(i)

Q=deque()

NOW=H.index(max(H))

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

while Q:
    x=Q.pop()
    for i in range(N):
        if S[x][i]=="1":
            if USE[i]==0:
                H[i]=H[x]+1
                USE[i]=1
                Q.append(i)

print(max(H)+1)

Submission status: Wrong Answer

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.append(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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, c):
        for u in edge[v]:
            if color[u] is None:
                color[u] = c
                dfs(u, c ^ 1)
            else:
                if color[u] != c:
                    print(-1)
                    exit()

    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)
                edge[j].append(i)

    color = [None] * n
    dfs(0, 0)
    for i in range(n):
        for j in range(n):
            if i == j:
                S[i][j] = 0
            else:
                S[i][j] = f_inf if S[i][j] == "0" else 1

    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])

    res = 0
    for s in S:
        res = max(res, max(s))
    print(res + 1)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import*
n=int(input())
s=[input() for _ in range(n)]
e=[[]for _ in range(n)]
INF=10**18
for i,x in enumerate(s):
  for j,y in enumerate(x):
    if y=='1':e[i]+=[j]
ans=0
for i in range(n):
  d=[INF]*n
  q=deque([(i,1)])
  while q:
    now,c=q.popleft()
    d[now]=c
    for to in e[now]:
      if d[to]==INF:
        q+=[(to,c+1)]
      elif d[to]!=c+1 and d[to]!=c-1:
        print(-1)
        exit()
  ans=max(max(d),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
from numba import jit

INF = 1 << 50
EPS = 1e-8

@jit
def solve(S):
    N = S.shape[0]
    ans = 0
    for k in range(N):
        #print(k, '-------------------')
        seen = set()
        seen.add(k)
        merged = np.ones(N, dtype=np.int32) * (-1)
        merged[0] = k
        count = 0
        while merged[0] > -1:
            #print(merged)
            count += 1
            nexts = np.ones(N, dtype=np.int32) * (-1)
            p = 0
            for i in merged:
                if i == -1:break
                for j, e in enumerate(S[i]):
                    if e and not j in seen:
                        #print(j)
                        nexts[p] = j
                        p += 1
                        seen.add(j)
            # merge check
            for i in range(N):
                if nexts[i] == -1:break
            checks = S[nexts[:i],:][:, nexts[:i]]
            #print(checks)
            if checks.sum() != 0:
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


def run():
    N = int(sysread())
    S = []
    for i in range(N):
        S.append(list(map(int, list(input()))))
    S = np.array(S, dtype = np.int8)

    solve(S)


if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8

def check_merge(merged,S):
    merged = set(merged)
    for i in merged:
        for j, e in enumerate(S[i]):
            if int(e) and j in merged:
                return False
    return True

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

    ans = 0

    #for s in S:
    #    print(s)
    for k in range(N):
        #print(k, '-------------------')
        seen = set()
        seen.add(k)
        merged = [k]
        count = 0
        while merged:
            #print(merged)
            count += 1
            nexts = []
            for i in merged:
                for j, e in enumerate(S[i]):
                    if int(e) and not j in seen:
                        nexts.append(j)
                        seen.add(j)
            if not check_merge(merged, S):
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

n = int(input())

graph = [[] for _ in range(n)]
d = [[float("inf")]*n for i in range(n)]

for i in range(n):
    s = input()
    for j, sj in enumerate(s):
        d[i][i] = 1
        if sj == '1':
            graph[i].append(j)
            d[i][j] = 1
            d[j][i] = 1

colors = [0 for i in range(n)]

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    stack = [(0,1)] # (頂点、色)のタプルをスタックする。最初は(頂点0, 黒(1))
    while stack:
        #スタックから最後に追加された(頂点, 色)をpop
        v,color = stack.pop()
        #今いる点を着色
        colors[v] = color
        #今の頂点から行けるところをチェック
        for to in graph[v]:
            #同じ色が隣接してしまったらFalse
            if colors[to] == color:
                return False
            #未着色の頂点があったら反転した色と共にスタックに積む
            if colors[to] == 0:
                stack.append((to, -color))
    #調べ終わったら矛盾がないのでTrue
    return True

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

def warshall_floyd(d, M):
    for k in range(M):
        for i in range(M):
            for j in range(M):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d #d[i][j]に頂点i, j間の最短距離を格納

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


if is_bipartite():
    ret = 0
    for a in warshall_floyd(d,n):
        ret = max(ret, max(a))
    print(ret+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
S = []
for _ in range(N):
  S.append(input())
  
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)

# 2部グラフ判定
visited = [False] * N
willSearch = [False] * N
Color = [-1] * N
Q = deque()
Q.append((0,0))
while Q:
  now, c = Q.pop()
  visited[now] = True
  Color[now] = c
  for nxt in G[now]:
    if Color[nxt] >= 0 and c == Color[nxt]:
      #隣接色が一致してしまった
      print(-1)
      exit(0)
    if visited[nxt] or willSearch[nxt]:
      continue
    Q.append((nxt,1-c)) # 1-cで0/1を交換
    willSearch[nxt] = True
    
INF = 1000
D = [[INF for _ in range(N) ]  for _ in range(N)]
for i in range(N):
  for nxt in G[i]:
    D[i][nxt] = 1
    D[nxt][i] = 1
    
#Warshall-Floyd
for k in range(N):
  for i in range(N):
    for j in range(N):
      #print(i,j,k)
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])
      
#print(*D, sep="\n")

ans = 0
for i in range(N):
  for j in range(i+1,N):
    ans = max(ans, D[i][j])
    
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INFTY = 1000
N = int(input())
S = [list(map(int,list(input()))) for _ in range(N)]
G = {i:[] for i in range(1,N+1)}
for i in range(N-1):
    for j in range(i+1,N):
        if S[i][j]==1:
            G[i+1].append(j+1)
            G[j+1].append(i+1)
heap = deque([(1,0)])
hist = [0 for _ in range(N+1)]
col = [-1 for _ in range(N+1)]
hist[1] = 1
col[1] = 0
flag = 0
while heap:
    x,c = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            col[y] = 1-c
            heap.append((y,1-c))
            hist[y]=1
        else:
            if col[y]!=1-c:
                flag = 1
                break
    if flag==1:break
if flag==1:
    print(-1)
else:
    dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            if i==j:
                dist[i+1][j+1]=0
            if S[i][j]==1:
                dist[i+1][j+1]=1
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
    dmax = 0
    for i in range(1,N+1):
        for j in range(1,N+1):
            dmax = max(dmax,dist[i][j])
    print(dmax+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INFTY = 1000
N = int(input())
S = [list(map(int,list(input()))) for _ in range(N)]
G = {i:[] for i in range(1,N+1)}
for i in range(N-1):
    for j in range(i+1,N):
        if S[i][j]==1:
            G[i+1].append(j+1)
            G[j+1].append(i+1)
heap = deque([(1,0)])
hist = [-1 for _ in range(N+1)]
hist[1] = 0
flag = 0
while heap:
    x,c = heap.popleft()
    for y in G[x]:
        if hist[y]==-1:
            hist[y] = 1-c
            heap.append((y,1-c))
        else:
            if hist[y]!=1-c:
                flag = 1
                break
    if flag==1:break
if flag==1:
    print(-1)
else:
    dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            if i==j:
                dist[i+1][j+1]=0
            if S[i][j]==1:
                dist[i+1][j+1]=1
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
    dmax = 0
    for i in range(1,N+1):
        for j in range(1,N+1):
            dmax = max(dmax,dist[i][j])
    print(dmax+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(S, i):
    D = [-1] * len(S)
    P = [set() for _ in range(len(S))]

    Q = deque()
    Q.append(i)
    D[i] = 1

    while Q:
        v = Q.popleft()

        for w in S[v]:
            if w in P[v]:
                continue
            
            if D[w] > 0 and D[w] < D[v] + 1:
                return -1

            P[w].add(v)
            D[w] = D[v] + 1
            Q.append(w)
    return D[v]


def main():
    N = int(input())
    S = [input().strip() for _ in range(N)]
    L = [set(j for j in range(N) if S[i][j] == "1") for i in range(N)]

    res = -1
    for i in range(N):
        r = f(L, i)
        res = max(res, r) 
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(S, i):
    D = [-1] * len(S)
    P = [set() for _ in range(len(S))]

    Q = deque()
    Q.append(i)
    D[i] = 1

    while Q:
        v = Q.popleft()

        for w, s in enumerate(S[v]):
            if s == "0":
                continue

            if w in P[v]:
                continue
            
            if D[w] > 0 and D[w] < D[v] + 1:
                return -1

            P[w].add(v)
            D[w] = D[v] + 1
            Q.append(w)
    return D[v]


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

    res = -1
    for i in range(N):
        r = f(S, i)
        res = max(res, r) 
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, graph, cur=0):
        color[v] = cur
        for u in graph[v]:
            if color[u] != -1:
                if color[u] == cur:
                    return False
                continue
            if not dfs(u, graph, 1 - cur):
                return False
        return True

    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)

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

    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                cost[i][j] = 0
            if S[i][j] == "1":
                cost[i][j] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    res = 0
    for i in range(n):
        res = max(res, max(cost[i]))
    print(res + 1)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == '1':
            edges[i].append(j)

#可能か
flg = True
l, r = set(), set()
l.add(0)
que = deque()
que.append((0, True))
is_left = True
while que and flg:
    cur, is_left = que.popleft()
    for to in edges[cur]:
        if is_left:
            if to in l:
                flg = False
            elif to not in r:
                r.add(to)
                que.append((to, False))
        else:
            if to in r:
                flg = False
            elif to not in l:
                l.add(to)
                que.append((to, True))

    if is_left:
        is_left = False
    else:
        is_left = True


if not flg:
    print(-1)

else:
    def warshall_floyd(d, v):
        for k in range(v):
            for i in range(v):
                for j in range(v):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    inf = 1000
    d = [[inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if j in edges[i]:
                d[i][j] = 1

    warshall_floyd(d, n)
    
    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            ans = max(ans, d[i][j]+1)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
m=[]
ans=[]
for i in range(n):
  m.append(input())
for start in range(n):
  a=[-1]*n
  q=collections.deque([(start,1)])
  failflag=0
  while q:
    l,r=q.popleft()
    a[l]=r
    for j in range(n):
      if m[l][j]=='1':
        if a[j]==-1:
          q.append((j,r+1))
        elif a[j]!=r+1 and a[j]!=r-1:
          failflag=1
      if failflag==1:
        break
    if failflag==1:
      break
  if failflag==1:
    ans.append(-1)
  else:
    ans.append((max(a)))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
m=[]
ans=[]
for i in range(n):
  m.append(input())
for start in range(n):
  a=[-1]*n
  q=collections.deque([[start,1]])
  failflag=0
  while q:
    p=q.popleft()
    a[p[0]]=p[1]
    for j in range(n):
      if m[p[0]][j]=='1':
        if a[j]==-1:
          q.append([j,p[1]+1])
        elif a[j]!=p[1]+1 and a[j]!=p[1]-1:
          failflag=1
      if failflag==1:
        break
    if failflag==1:
      break
  if failflag==1:
    ans.append(-1)
  else:
    ans.append((max(a)))
print(max(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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()
            group[cur_v] = gid
            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
                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: Time Limit Exceeded

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)])
        valid = True

        while q:
            cur_v, gid = q.popleft()
            group[cur_v] = gid
            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:
                        valid = False
                        break
                    else:
                        continue
                q.append((next_v, gid+1))
        if not valid:
            return -1
        # print('v: ', v)
        # print('group: ', group)
        # print()
        return max(group) + 1

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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)

if uf.same(0,n):
    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: Time Limit Exceeded

Solution code:
def warshall_floyd(g):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])

n = int(input())
s = [[int(i) for i in list(input())] for _ in range(n)]
graph = [[float("inf")]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == 1:
            graph[i][j] = 1
        if i == j:
            graph[i][j] = 0

warshall_floyd(graph)
d = 0
#print(graph)
for i in range(n-1):
    for j in range(i+1,n):
        if graph[i][j] != float("inf"):
            if d < graph[i][j]:
                start = i
                end = j
                d = graph[i][j]

v = [[] for _ in range(d+1)]
for i in range(n):
    l = graph[start]
    v[l[i]].append(i)
#print(v)
#print(start,end)

for l in v:
    m = len(l)
    for i in range(m-1):
        for j in range(i+1,m):
            if s[l[i]][l[j]] == 1:
                print(-1)
                quit()
print(d+1)

Submission status: Time Limit Exceeded

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 j in l[i]:
        uf.unite(i,j+n)
        uf.unite(i+n,j)
f=0
for i in range(n):
    f|=uf.same(i,i+n)

if f:
    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: Time Limit Exceeded

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==-1:
  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)