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:
import sys
from collections import deque

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


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for _ in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = [None] * self.N
        self.level[s] = 0
        que = deque([s])
        G = self.G
        while que:
            v = que.popleft()
            next_level = self.level[v] + 1
            for w, cap, _ in G[v]:
                if cap and self.level[w] is None:
                    self.level[w] = next_level
                    que.append(w)
        return self.level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10 ** 9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


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

    n = int(input())
    tree = [[] for _ in range(n)]
    edge = []
    for i in range(n):
        s = input()
        for j in range(n):
            if s[j] == "1":
                tree[i].append(j)
                tree[j].append(i)
                edge.append([i, j, 1])
                edge.append([j, i, 1])

    color = [None] * n
    dfs(0, 0)
    start, end = n, n + 1
    for i in range(n):
        edge.append([start, i, 1]) if color[i] else edge.append([i, end, 1])

    mf = Dinic(n + 2)
    for to, fr, cap in edge:
        mf.add_edge(to, fr, cap)
    res = mf.flow(start, end)
    print(res + 1)
    

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush

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


def dijkstra_heap(v, start, edge):
    """
    ダイクストラ法
    :param v: 走査するグラフの頂点数
    :param start: 始点
    :param edge: 重み付き隣接リスト。[cost, node]の形で渡す
    :return: 始点から各頂点への最短距離
    """
    res = [f_inf] * v
    res[start] = 0
    checked = [False] * v
    checked[start] = True
    edge_list = []
    for u in edge[start]:
        heappush(edge_list, u)
    while len(edge_list):
        min_edge = heappop(edge_list)
        cost, node = min_edge
        if not checked[node]:
            res[node] = cost
            checked[node] = True
            for next_cost, next_node in edge[node]:
                if not checked[next_node]:
                    heappush(edge_list, [next_cost + cost, next_node])
    return res


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

    color = [None] * n
    dfs(0, 0)
    dist = dijkstra_heap(n, 0, edge)
    res = dijkstra_heap(n, dist.index(max(dist)), edge)
    print(max(res) + 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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, 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()

    def bfs(v):
        dist = [f_inf] * n
        dist[v] = 0
        q = deque([v])
        while q:
            u = q.popleft()
            for v in edge[u]:
                if dist[v] == f_inf:
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist

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

    color = [None] * n
    dfs(0, 0)
    dist = bfs(0)
    res = bfs(dist.index(max(dist)))
    print(max(res) + 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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


N = int(input())
A = [[int(a) for a in input()] for _ in range(N)]
graph = csgraph_from_dense(np.array(A))
dist_mat = floyd_warshall(graph).astype(np.int64)
max_d = dist_mat.max()

B = np.where(dist_mat[0]%2 == 0)
C = np.where(dist_mat[0]%2 == 1)

bl = (dist_mat[B, B] % 2 == 0).all() and (dist_mat[C, C] % 2 == 0).all()



if bl:
    print(max_d + 1)
else:
    print(-1)

Submission status: Wrong Answer

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


N = int(input())
A = [[int(a) for a in input()] for _ in range(N)]
graph = np.array(A)

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

max_d = dist_mat.max()

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

if bl:
    print(max_d + 1)
else:
    print(-1)

Submission status: Wrong Answer

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


N = int(input())
A = [[int(a) for a in input()] for _ in range(N)]
graph = np.array(A)

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

max_d = dist_mat.max()

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

if bl:
    print(max_d + 1)
else:
    print(-1)

Submission status: Wrong Answer

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


N = int(input())
A = [[int(a) for a in input()] for _ in range(N)]
graph = np.array(A)

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

max_d = dist_mat.max()

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

if bl:
    print(max_d + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [list(input()) for i in range(n)]
e = [[] for i in range(n)]
count = [0]*n
for i in range(n):
    count[i] = S[i].count("1")
    for j in range(i+1,n):
        if S[i][j] == "1":
            e[i].append(j)
            e[j].append(i)

m = min(count)
ans = 0
for i in range(n):
    if count[i] != m:
        continue
    dis = [float("INF")]*n
    dis[i] = 0
    check = True
    l = [i]
    d = 0
    while check:
        nl = []
        for j in l:
            for nex in e[j]:
                if dis[nex] < d-1 or dis[nex] == d:
                    check = False
                    break
                if dis[nex] == float("INF"):
                    nl.append(nex)
                    dis[nex] = d+1
            if check == False:
                break
        if check == False:
            d = float("INF")
            break
        if nl:
            l = nl
            d += 1
        else:
            break
    if d != float("INF"):
        ans = max(ans,d+1)
print(ans if ans != 0 else -1)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [list(input()) for i in range(n)]
e = [[] for i in range(n)]
count = [0]*n
for i in range(n):
    count[i] = S[i].count("1")
    for j in range(i+1,n):
        if S[i][j] == "1":
            e[i].append(j)
            e[j].append(i)

m = min(count)
ans = float("INF")
for i in range(n):
    if count[i] != m:
        continue
    dis = [float("INF")]*n
    dis[i] = 0
    check = True
    l = [i]
    d = 0
    while check:
        nl = []
        for j in l:
            for nex in e[j]:
                if dis[nex] < d-1 or dis[nex] == d:
                    check = False
                    break
                if dis[nex] == float("INF"):
                    nl.append(nex)
                    dis[nex] = d+1
            if check == False:
                break
        if check == False:
            d = float("INF")
            break
        if nl:
            l = nl
            d += 1
        else:
            break
    if d != float("INF"):
        ans = max(ans,d+1)
print(ans if ans < float("INF") else -1)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [list(input()) for i in range(n)]
e = [[] for i in range(n)]
count = [0]*n
for i in range(n):
    count[i] = S[i].count("1")
    for j in range(i+1,n):
        if S[i][j] == "1":
            e[i].append(j)
            e[j].append(i)

m = min(count)
ans = float("INF")
for i in range(n):
    if count[i] != m:
        continue
    dis = [float("INF")]*n
    dis[i] = 0
    check = True
    l = [i]
    d = 0
    while check:
        nl = []
        for j in l:
            for nex in e[j]:
                if dis[nex] < d-1 or dis[nex] == d:
                    check = False
                    break
                if dis[nex] == float("INF"):
                    nl.append(nex)
                    dis[nex] = d+1
            if check == False:
                break
        if check == False:
            d = float("INF")
            break
        if nl:
            l = nl
            d += 1
        else:
            break
    ans = min(ans,d+1)
print(ans if ans < float("INF") else -1)

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def judge(g):
    n = len(g)
    bi = [-1] * n
    bi[0] = 0
    for i, row in enumerate(g):
        for j, column in enumerate(row):
            if column == "1":
                if bi[i] == -1:
                    bi[i] = bi[j] ^ 1
                elif bi[j] == -1:
                    bi[j] = bi[i] ^ 1
                else:
                    if bi[i] == bi[j]:
                        print(-1)
                        sys.exit()




def solve():
    n = getN()
    g = []
    for i in range(n):
        g.append([c for c in getS()])

    judge(g)

    costs = [[INF for i in range(n)] for j in range(n)]
    for i in range(n):
        costs[i][i] = 0

    for i, row in enumerate(g):
        for j, column in enumerate(row):
            if column == "1":
                costs[i][j] = 1

    V = n
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if costs[i][k] != INF and costs[k][j] != INF:
                    costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

    ans = max([max(x) for x in costs])
    print(ans + 1)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
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=[i]
  d[i]=1
  while q:
    now=q.pop()
    for to in e[now]:
      if d[to]==INF:
        q+=[to]
        d[to]=d[now]+1
      elif d[to]!=d[now]+1 and d[to]!=d[now]-1:
        print(-1)
        exit()
  ans=max(max(d),ans)
print(ans)

Submission status: Wrong Answer

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

    def bfs(v):
        dist = [f_inf] * n
        dist[v] = 0
        q = deque()
        q.append(v)
        while q:
            u = q.popleft()
            for nv in edge[u]:
                if dist[nv] == f_inf:
                    dist[nv] = dist[u] + 1
                    q.append(nv)
        return dist

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

    dist1 = bfs(0)
    start = dist1.index(max(dist1))
    dist2 = bfs(start)
    res = max(dist2) + 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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


def resolve():
    def bfs(v):
        dist = [f_inf] * n
        dist[v] = 0
        q = deque()
        q.append(v)
        while q:
            u = q.popleft()
            for nv in edge[u]:
                if dist[nv] == f_inf:
                    dist[nv] = dist[u] + 1
                    q.append(nv)
        return dist

    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)

    dist1 = bfs(0)
    start = dist1.index(max(dist1))
    dist2 = bfs(start)
    res = max(dist2)
    ends = [idx for idx, d in enumerate(dist2) if d == res]
    for end in ends:
        if end in edge[start] and n > 2:
            print(-1)
            break
    else:
        print(res + 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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


def resolve():
    def bfs(v):
        dist = [f_inf] * n
        dist[v] = 0
        q = deque()
        q.append(v)
        while q:
            u = q.popleft()
            for nv in edge[u]:
                if dist[nv] == f_inf:
                    dist[nv] = dist[u] + 1
                    q.append(nv)
        return dist

    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)

    d = bfs(0)
    start = d.index(max(d))
    d2 = bfs(start)
    end = d2.index(max(d2))
    if end in edge[start] and n > 2:
        print(-1)
    else:
        print(max(d2) + 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
route = [[] for i in range(n)]
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == "1":
            route[i].append(j)
            route[j].append(i)
visit = [-1 for i in range(n)]
visit[0] = 1
d = deque()
d.append(0)
while d:
    now = d.popleft()
    for i in route[now]:
        if visit[i] == -1:
            visit[i] = visit[now] + 1
            d.append(i)
        elif abs(visit[i] - visit[now]) != 1:
            print(-1)
            exit()
nex = visit.index(max(visit))
visit = [-1 for i in range(n)]
visit[nex] = 1
d = deque()
d.append(nex)
while d:
    now = d.popleft()
    for i in route[now]:
        if visit[i] == -1:
            visit[i] = visit[now] + 1
            d.append(i)
        elif abs(visit[i] - visit[now]) != 1:
            print(-1)
            exit()
print(max(visit))

Submission status: Wrong Answer

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

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

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for i in range(n):
        if s[v][i] == 1:
            #同じ色が隣接してしまったらFalse
            if colors[i] == color:
                return False
            #未着色の頂点があったら反転した色を指定し、再帰的に調べる
            if colors[i] == 0 and not dfs(i, -color):
                return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

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

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

##############################
d = [[float("inf")]*n for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        if s[i][j] == 1:
            d[i][j] = s[i][j]
            d[j][i] = s[j][i]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

print(max(warshall_floyd(d)))
if is_bipartite():
    print(max(max(warshall_floyd(d)))+1)
else:
    print(-1)

Submission status: Wrong Answer

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

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

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for i in range(n):
        if s[v][i] == 1:
            #同じ色が隣接してしまったらFalse
            if colors[i] == color:
                return False
            #未着色の頂点があったら反転した色を指定し、再帰的に調べる
            if colors[i] == 0 and not dfs(i, -color):
                return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

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

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

##############################
d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    for j in range(n):
        if s[i][j] != 0:
            d[i][j] = s[i][j]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
    
if is_bipartite():
    print(max(max(warshall_floyd(d)))+1)
else:
    print(-1)

Submission status: Wrong Answer

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
  visited=set()
  while q:
    l,r=q.popleft()
    a[l]=r
    for j in range(n):
      if m[l][j]=='1':
        if a[j]==-1 and not j in visited:
          q.append((j,r+1))
          visited.add(j)
  for i in range(n):
    for j in range(i+1,n):
      if m[i][j]=='1':
        if a[i]!=a[j]-1 and a[i]!=a[j]!=1:
          failflag=1
  if failflag==1:
    ans.append(-1)
  else:
    ans.append((max(a)))
print(max(ans))

Submission status: Wrong Answer

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
  visited=set()
  while q:
    l,r=q.popleft()
    a[l]=r
    for j in range(n):
      if m[l][j]=='1':
        if a[j]==-1 and not j in visited:
          q.append((j,r+1))
          visited.add(j)
        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: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

N = int(input())
m = list(input() for _ in range(N))

edge = [[0]*N for _ in range(N)]

ones = 0
for i in m:
    ones += i.count("1")
if ones == N**2 - N:
    print(-1)
    exit()

for i in range(N):
    for j in range(N):
        edge[i][j] = int(m[i][j])

d = dijkstra(edge)
m = 0
for i in d:
    m = max(m,int(max(i)))

print(m+1)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

N = int(input())
m = list(input() for _ in range(N))

edge = [[0]*N for _ in range(N)]

for i in range(N):
    for j in range(N):
        edge[i][j] = int(m[i][j])

d = dijkstra(edge)
m = 0
for i in d:
    m = max(m,int(max(i)))

print(m+1)

Submission status: Wrong Answer

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:
        ans = max(i)
    print(ans+1)

Submission status: Wrong Answer

Solution code:
#AGC039-B
"""
連結無向重みなしグラフが与えられる。
辺情報はバイナリの隣接行列として与えられる。

辺がある2頂点に張られている場合、必ず隣り合う集合に存在するように、
集合に辺を割り振った時の、集合の個数の最大値を出力せよ。

つまり、ある頂点と接続されている頂点は、集合で、その頂点の+1もしくは-1の場所に
配置され、他の頂点に関しても同様の処理が行えなければならない。

まず大前提として、つながっている辺が1つである頂点が2つ以上無いと解は存在しない。

そうでない場合、辺を1つしか持たない2つの頂点について、その距離の最小値が最大であるものが
答えとなる。

計算量はFWでO(N^3)
"""
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)]
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    for j in range(n):
        if s[j] == "1":
            g[i][j] = 1
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

lst1 = []
for i in range(n):
    if g[i].count(1) == 1:
        lst1.append(i)

if len(lst1) < 2:
    print(-1)
    exit()

FW = warshall_floyd(g)

ans = 0
import itertools
for i,j in itertools.combinations(lst1,2):
    ans = max(ans,FW[i][j])
for i,j,k in itertools.combinations([i for i in range(n)],3):
    if g[i][j] == g[j][k] == g[i][k] == 1:
        print("NO")
        exit()
print(ans+1)

Submission status: Wrong Answer

Solution code:
#AGC039-B
"""
連結無向重みなしグラフが与えられる。
辺情報はバイナリの隣接行列として与えられる。

辺がある2頂点に張られている場合、必ず隣り合う集合に存在するように、
集合に辺を割り振った時の、集合の個数の最大値を出力せよ。

つまり、ある頂点と接続されている頂点は、集合で、その頂点の+1もしくは-1の場所に
配置され、他の頂点に関しても同様の処理が行えなければならない。

まず大前提として、つながっている辺が1つである頂点が2つ以上無いと解は存在しない。

そうでない場合、辺を1つしか持たない2つの頂点について、その距離の最小値が最大であるものが
答えとなる。

計算量はFWでO(N^3)
"""
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)]
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    for j in range(n):
        if s[j] == "1":
            g[i][j] = 1
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

lst1 = []
for i in range(n):
    if g[i].count(1) == 1:
        lst1.append(i)

if len(lst1) < 2:
    print(-1)
    exit()

FW = warshall_floyd(g)

ans = 0
import itertools
for i,j in itertools.combinations(lst1,2):
    ans = max(ans,FW[i][j])

print(ans+1)

Submission status: Wrong Answer

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):
            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])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

color = [0] * N

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

ans = 0

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

Submission status: Wrong Answer

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

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):
            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: Wrong Answer

Solution code:
from collections import *
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()
D=deque()
S=set()
def init():
  global D,S
  D=deque()
  S=set()

def qao(x):
  global S,D
  if x in S:
    return False
  S.add(x)
  D.append(x)
  return True

def bfs():
  global VE,D
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(len(VE[v])):
      qao(VE[v][j])
  return len(D)==0

C=0
qao(0)
while True:
  if bfs():
    break
  C=D[0]
init()
qao(C)
for i in range(10**4):
  if bfs():
    print(i+1)
    exit()

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):
    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(cos+1)
else:
    print(-1)