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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return [int(i) for i in input().rstrip()]
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    k = II()
    ans = 0
    lis = []
    i = 0
    tmp = 1
    while len(s) > i + 1:
        if s[i] == s[i + 1]:
            tmp += 1
        else:
            lis.append((s[i], tmp))
            tmp = 1
        i += 1
    lis.append((s[i], tmp))
    if lis[0][0] == lis[-1][0]:
        if len(lis) == 1:
            ans += k * lis[0][1] // 2
            print(ans)
            return
        ans -= (lis[0][1] // 2 + lis[-1][1] // 2) * (k - 1)
        ans += (lis[0][1] + lis[-1][1]) // 2 * (k - 1)
    for _, b in lis:
        ans += b // 2 * k
    print(ans)
    return

#B
def B():
    n = II()
    s = SR(n)
    edg = [[] for i in range(n)]
    check = [0] * n
    for i in range(n):
        for k in range(n):
            if i == k:
                continue
            if s[i][k]:
                edg[i].append(k)
                edg[k].append(i)
            else:
                s[i][k] = inf
    for i in range(n):
        q = deque([i])
        if check[i] == 0:
            check[i] += 1
        while q:
            p = q.pop()
            for k in edg[p]:
                if check[k]:
                    if (check[k] ^ check[p]) & 1:
                        continue
                    print(-1)
                    return
                else:
                    check[k] = check[p] + 1
                    q.appendleft(p)

    for x in range(n):
        for i in range(n):
            for k in range(n):
                s[i][k] = min(s[i][k], s[i][x] + s[x][k])
    ans = 0
    for i in range(n):
        for k in range(n):
            if s[i][k] == inf:
                continue
            ans = max(s[i][k], ans)
    print(ans+1)
# C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return [int(i) for i in input().rstrip()]
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    k = II()
    ans = 0
    lis = []
    i = 0
    tmp = 1
    while len(s) > i + 1:
        if s[i] == s[i + 1]:
            tmp += 1
        else:
            lis.append((s[i], tmp))
            tmp = 1
        i += 1
    lis.append((s[i], tmp))
    if lis[0][0] == lis[-1][0]:
        if len(lis) == 1:
            ans += k * lis[0][1] // 2
            print(ans)
            return
        ans -= (lis[0][1] // 2 + lis[-1][1] // 2) * (k - 1)
        ans += (lis[0][1] + lis[-1][1]) // 2 * (k - 1)
    for _, b in lis:
        ans += b // 2 * k
    print(ans)
    return

#B
def B():
    n = II()
    s = SR(n)
    edg = [[] for i in range(n)]
    check = [0] * n
    for i in range(n):
        for k in range(n):
            if i == k:
                continue
            if s[i][k]:
                edg[i].append(k)
                edg[k].append(i)
            else:
                s[i][k] = inf
    for i in range(n):
        q = deque([i])
        if check[i] == 0:
            check[i]
        while q:
            p = q.pop()
            for k in edg[p]:
                if check[k]:
                    if (check[k] ^ check[p]) & 1:
                        continue
                    print(-1)
                    return
                else:
                    check[k] = check[p] + 1
                    q.appendleft(p)
    for x in range(n):
        for i in range(n):
            for k in range(n):
                s[i][k] = min(s[i][k], s[i][x] + s[x][k])
    ans = 0
    for i in range(n):
        for k in range(n):
            if s[i][k] == inf:
                continue
            ans = max(s[i][k], ans)
    print(ans+1)
# C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    f = 0
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        while que:
            v, c = que.popleft()
            col[v] = c
            for ne in E[v]:
                if col[ne] == c:
                    f = 1
                    break
                if col[ne] < 0:
                    que.append([ne, 1-c])

            if f:
                break
        if f:
            break
    return 1-f

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(20000000)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        f = 0
        while que:
            v, c = que.popleft()
            col[v] = c
            for ne in E[v]:
                if col[ne] == c:
                    f = 1
                    break
                if col[ne] < 0:
                    que.append([ne, 1-c])

            if f:
                break
    return 1-f

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(max([max(BFS(N, X, i)) for i in range(N)])+1)
else:
    print(-1)
print("X =", X)
for i in range(N):
    print(i, BFS(N, X, i))

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque




def main():
    node_num = int(input())
    data = [list(map(int, list(input()))) for i in range(node_num)]

    graph_data = defaultdict(set)
    for i in range(node_num):
        for j in range(node_num):
            if data[i][j]:
                graph_data[i].add(j)

    ans = 0

    for i in range(node_num):
        flg_list = [0 for j in range(node_num)]

        now_set = set()
        pre_set = set()
        now_set.add(i)
        kari = 0

        while 1:
            if len(now_set) == 0:
                break
                # for j in range(node_num):
                #     if flg_list[j] == 0:
                #         now_set.add(j)
                #         pre_set = set()
                #         # print(now_set)
                #         break
            kari += 1
            next_set = set()

            for ele in now_set:
                next_set |= graph_data[ele]

            if len(now_set & next_set):
                break

            if pre_set & next_set != pre_set:
                break
            next_set -= pre_set


            fin_flg = 0
            for ele in now_set:
                if flg_list[ele] == 1:
                    fin_flg = 1
                    break
                flg_list[ele] = 1

            if fin_flg:
                break


            if min(flg_list):
                ans = max(ans, kari)
                break

            pre_set = now_set
            now_set = next_set


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









if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque




def main():
    node_num = int(input())
    data = [list(map(int, list(input()))) for i in range(node_num)]

    graph_data = defaultdict(set)
    for i in range(node_num):
        for j in range(node_num):
            if data[i][j]:
                graph_data[i].add(j)


    ans = 0

    for i in range(node_num):
        flg_list = [0 for i in range(node_num)]

        now_set = set()
        pre_set = set()
        now_set.add(i)
        kari = 0

        while 1:
            if len(now_set) == 0:
                break

            kari += 1
            next_set = set()

            for ele in now_set:
                next_set |= graph_data[ele]

            if len(now_set & next_set):
                break

            if len(pre_set & next_set) != len(pre_set):
                break
            next_set -= pre_set


            fin_flg = 0
            for ele in now_set:
                if flg_list[ele] == 1:
                    fin_flg = 1
                    break
                flg_list[ele] = 1

            if fin_flg:
                break


            if min(flg_list):
                ans = max(ans, kari)
                break

            pre_set = now_set
            now_set = next_set


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









if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque




def main():
    node_num = int(input())
    data = [list(map(int, list(input()))) for i in range(node_num)]

    graph_data = defaultdict(set)
    for i in range(node_num):
        for j in range(node_num):
            if data[i][j]:
                graph_data[i].add(j)


    ans = 0

    for i in range(node_num):
        flg_list = [0 for i in range(node_num)]

        now_set = set()
        pre_set = set()
        now_set.add(i)
        kari = 0

        while 1:
            if len(now_set) == 0:
                break

            kari += 1
            next_set = set()

            for ele in now_set:
                next_set |= graph_data[ele]

            if len(now_set & next_set):
                break

            if len(pre_set & next_set) != len(pre_set):
                break
            next_set -= pre_set


            fin_flg = 0
            for ele in now_set:
                if flg_list[ele] == 1:
                    fin_flg = 1
                    break
                flg_list[ele] = 1

            if fin_flg:
                break


            if min(flg_list):
                ans = max(ans, kari)
                break

            pre_set = now_set
            now_set = next_set


    if ans > 0:
        print(ans + 1)
    else:
        print(-1)









if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque




def main():
    node_num = int(input())
    data = [list(map(int, list(input()))) for i in range(node_num)]

    graph_data = defaultdict(set)
    for i in range(node_num):
        for j in range(node_num):
            if data[i][j]:
                graph_data[i].add(j)


    ans = 0

    for i in range(node_num):
        flg_list = [0 for i in range(node_num)]

        now_set = set()
        pre_set = set()
        now_set.add(i)
        kari = 0

        while 1:
            if len(now_set) == 0:
                break

            kari += 1
            next_set = set()

            for ele in now_set:
                next_set |= graph_data[ele]

            if len(now_set & next_set):
                break

            if len(pre_set & next_set) != len(pre_set):
                break
            next_set -= pre_set


            fin_flg = 0
            for ele in now_set:
                if flg_list[ele] == 1:
                    fin_flg = 1
                    break
                flg_list[ele] = 1

            if fin_flg:
                break


            if min(flg_list):
                ans = max(ans, kari)
                break

            pre_set = now_set
            now_set = next_set


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









if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def GraphPartition(N, Mtx):
	rslt = 0
	for i in range(N):
		for j in range(i+1, N):
			connect = 0
			if Mtx[i][j] == 0:
				continue
			if i < N-1:
				connect += Mtx[i+1][j]
			if j < N-1:
				connect += Mtx[i][j+1]
			if i < N-1 and j < N-1:
				connect += Mtx[i+1][j+1]
			if connect > 1:
				rslt = -1
				break
			parent = 0
			parent += Mtx[i][j-1]
			if i > 0:
				parent = Mtx[i-1][j-1] + Mtx[i-1][j]
			if parent == 0:
				rslt += 1
		if rslt == -1:
			break
	if rslt == -1:
		print(-1)
	else:
		print(rslt * 2)

N = int(input())
Mtx = []
for i in range(N):
	tmp = [int(x) for x in str(input())]
	Mtx.append(tmp)
GraphPartition(N, Mtx)

Submission status: Wrong Answer

Solution code:
import sys, collections

def dfs(i, c, col, edge):
    col[i] = c
    for next_node in edge[i]:
        if col[next_node] == c: return False
        if col[next_node] == 0 and dfs(next_node, -c, col, edge) == False: return False

    return True

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = 0
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    is_bipartite = dfs(0, 1, col, edge)
    if not is_bipartite: print(-1)
    else:
        q = collections.deque()
        farest = [-1, -1]
        dist_to, dist_back = dict(), dict()
        for i in range(N):
            dist_to[i] = -1
            dist_back[i] = -1

        q.append((0, 0))
        while q:
            now_node, now_dist = q.popleft()
            if dist_to[now_node] == -1:
                dist_to[now_node] = now_dist
                if now_dist > farest[0]: farest = [now_dist, now_node] 
                for next_node in edge[now_node]:
                    if dist_to[next_node] == -1: q.append((next_node, now_dist + 1))

        diameter = 0
        q.append((farest[1], 1))
        while q:
            now_node, now_dist = q.popleft()
            if dist_back[now_node] == -1:
                dist_back[now_node] = now_dist
                if now_dist > diameter: diameter = now_dist
                for next_node in edge[now_node]:
                    if dist_back[next_node] == -1: q.append((next_node, now_dist + 1))
        print(diameter)
        #print(dist_back)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as wf
from collections import deque
input = sys.stdin.readline

def main():
    N = int(input())
    link = [[0 if c == "0" else 1 for c in list(input().strip())] for i in range(N)]
    # print(link)

    
    ok = True
    last = 0
    ans = 0
    for _ in range(2):
        check = [False] * N
        colors = [True] * N
        check[last] = True
        q = deque()
        q.append((last, True, 1))
        while len(q) > 0:
            i, color, step = q.popleft()
            last = i
            ans = max(ans, step)
            # print(i, color, step)
            for nex, c in enumerate(link[i]):
                if c == 1:
                    if check[nex]:
                        if colors[nex] == color:
                            ok = False
                            break
                    else:
                        check[nex] = True
                        colors[nex] = not(color)
                        q.append((nex, not(color), step+1))
            if not ok:
                break
        if not ok:
            break
    
    if ok:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

# import sys
# input = sys.stdin.readline
# from collections import Counter
# import string
from collections import deque

INF = float('inf')


def main():
    N = int(input())
    # N = map(int, input().split())
    graph = [[] for i in range(N)]
    # ans = [0] * (N+1)
    # visit = [False]*(N+1)

    def get_distances(s):
        q = deque()
        q.append(s)
        d = [INF] * N
        d[s] = 0
        while len(q):
            u = q.popleft()
            for v, e in enumerate(graph[u]):
                if e:
                    if d[v] > d[u] + 1:
                        d[v] = d[u] + 1
                        q.append(v)
        return d

    def get_diameter():
        dmax = 0
        for i in range(N):
            d = get_distances(i)
            print(i, d)
            dmax = max(max(d), dmax)
        return dmax

    for i in range(N):
        edges = input()
        for s in range(len(edges)):
            e = int(edges[s])
            graph[i].append(e)

    q = deque()
    q.append(0)
    color = [0] * N
    vaild = True
    color[0] = 1
    d = [INF] * N
    d[0] = 0

    while vaild and len(q) != 0:
        u = q.popleft()
        # print(u+1, [i + 1 for i in q])
        for v, e in enumerate(graph[u]):
            # print(v, e)
            if e == 1:
                # print(v)
                if not color[v]:
                    color[v] = -color[u]
                    q.append(v)
                    # print(v+1, color)
                elif color[v] == color[u]:
                    vaild = False
                    # print('invalid')
                    break

                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
    if vaild:
        print(get_diameter() + 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
s = []
for _ in range(n):
    s.append(input())


def graph(i, n, s):
    flag = [-2 for _ in range(n)]
    flag[i] = 1
    que = collections.deque([i])
    while que:
        target = que.popleft()
        for j in range(n):
            if s[target][j] == "1":
                if flag[j] == -2:
                    flag[j] = flag[target] + 1
                    que.append(j)
                elif flag[j] != flag[target] + 1 and flag[j] != flag[target] - 1:
                    return [-1, -1]
    mf = max(flag)
    return [flag.index(mf), mf]


r1 = graph(0, n, s)
if r1[0] == -1:
    print(-1)
else:
    r2 = graph(r1[0], n, s)
    print(r2[1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(list(map(int, input()[:-1])))

INF = float('inf')

def is_bipartite_graph():
    team = [0] * N
    valid = True
    q = deque()
    q.append(0)
    team[0] = 1
    while valid and len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if not team[v]:
                    team[v] = team[u]%2 + 1
                    q.append(v)
                else:
                    if (team[v] - team[u])%2 == 0:
                        valid = False
                        break
    return valid


def get_distances(s):
    q = deque()
    q.append(s)
    d = [INF] * N
    d[s] = 0
    state = [0] * N
    while len(q):
        u = q.popleft()
        state[u] = 1
        for v, e in enumerate(V[u]):
            if state[v] > 0:
                continue
            if e:
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                q.append(v)
                state[v] = 1
        state[u] = 2
    return d


def get_diameter():
    d = get_distances(0)
    dmax = max(d)
    dindex = d.index(dmax)
    d = get_distances(dindex)
    return max(d)


if is_bipartite_graph():
    print(get_diameter()+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for _ in range(n):
    s.append(input())


def graph(i, n, s):
    flag = [-2 for _ in range(n)]

    flag[i] = 1
    que = [i]
    while que:
        target = que.pop()
        for j in range(n):
            if s[target][j] == "1":
                if flag[j] == -2:
                    flag[j] = flag[target] + 1
                    que.append(j)
                elif flag[j] != flag[target] + 1 and flag[j] != flag[target] - 1:
                    return [-1, -1]
    mf = max(flag)
    return [flag.index(mf), mf]


r1 = graph(0, n, s)
if r1[0] == -1:
    print(-1)
else:
    r2 = graph(r1[0], n, s)
    print(r2[1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(list(map(int, input()[:-1])))

INF = float('inf')

def is_bipartite_graph():
    team = [0] * N
    valid = True
    q = deque()
    q.append(0)
    team[0] = 1
    while valid and len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if not team[v]:
                    team[v] = team[u]%2 + 1
                    q.append(v)
                else:
                    if (team[v] - team[u])%2 == 0:
                        valid = False
                        break
    return valid


def get_distances(s):
    q = deque()
    q.append(s)
    d = [INF] * N
    d[s] = 0
    f = [False] * N
    while len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if f[v]:
                continue
            if e:
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                q.append(v)
        f[u] = True        
    return d


def get_diameter():
    d = get_distances(0)
    dmax = max(d)
    dindex = d.index(dmax)
    d = get_distances(dindex)
    return max(d)


if is_bipartite_graph():
    print(get_diameter()+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n = len(d)
    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 solve():
    N = II()
    edge_list = {}
    # i, j は 0 origin で入れる
    for i in range(N):
        edge_list[i] = []
        ei = SI()
        for j, e in enumerate(ei):
            if e == '1':
                edge_list[i].append(j)

    # 二部グラフチェック
    # -1, 1 をアサインしていく
    bip = [0 for i in range(N)]

    # キュー
    from collections import deque
    qu = deque()
    qu.append((-1, 0)) # 親のbip, nodeid。0はおやを-1と仮定する

    # 既読
    seen = set()
    is_bip = True


    while qu:
        parent_bip, n = qu.popleft()

        # 親と同じ側にアサインされているなら、bipではないので終了
        if parent_bip * bip[n] == 1:
            is_bip = False
            print(-1)
            return

        # 親と反対側にアサイン
        bip[n] = parent_bip * -1

        if n not in seen:
            for neib in edge_list[n]:
                qu.append((bip[n], neib))
        dprint('parent_bip:',parent_bip, 'n:', n, 'edge:', edge_list[n], 'q:', qu, seen)
        seen.add(n)

    dprint(bip)

    # bipなら直径
    mx = N + 1
    d = [[mx for i in range(N)] for i in range(N)]
    for i in range(N):
        for e in edge_list[i]:
            d[i][e] = 1
    d = warshall_floyd(d)

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

    print(ans+1)

solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append([])
    for j in input():
        A[-1].append(int(j))


def confirm(index):
    R = [ind for ind in range(N)]
    R.remove(index)
    res = dict()
    depth = 1
    res[index] = depth
    box = [index]
    flag = False
    while True:
        depth += 1
        app = []
        for l in box:
            for k in range(N):
                if A[l][k] == 1:

                    if k in res.keys() and abs(res[k] - depth) >= 2:
                        return False
                    elif k not in res.keys():
                        R.remove(k)
                        res[k] = depth
                        app.append(k)
        box = app

        if flag:
            return depth
        if len(R) == 0:
            flag = True


result = -1
for i in range(len(A)):
    J = confirm(i)
    if not J:
        continue
    if result < J:
        result = J
print(result)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() 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)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



def main():
    n = I()
    graph = SR(n)
    cost = [INF] * n
    cost[0] = 0
    que = deque([0])
    while que:
        cur = que.popleft()
        for nxt in range(n):
            if int(graph[cur][nxt]):
                c1 = cost[cur]
                if cost[nxt] != INF and cost[nxt] % 2 != (c1 + 1) % 2:
                    return -1
                else:
                    if cost[nxt] > c1 + 1:
                        cost[nxt] = c1 + 1
                        que += [nxt]


    ret = -INF
    for i in range(n):
        if cost[i] > ret:
            ret = cost[i]
            max_ind = i


    cost = [INF] * n
    cost[max_ind] = 0
    que2 = deque([max_ind])
    while que2:
        cur = que2.popleft()
        for nxt in range(n):
            if int(graph[cur][nxt]):
                c1 = cost[cur]
                if cost[nxt] > c1 + 1:
                    cost[nxt] = c1 + 1
                    que2 += [nxt]



    return max(cost) + 1


print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append([])
    for j in input():
        A[-1].append(int(j))


def confirm(index):
    R = [ind for ind in range(N)]
    R.remove(index)
    res = dict()
    depth = 1
    res[index] = depth
    box = [index]
    while True:
        depth += 1
        app = []
        for l in box:
            for k in range(N):
                if A[l][k] == 1:

                    if k in res.keys() and not(abs(res[k] - depth) != 1 or abs(res[k] - depth) != 0):
                        return False
                    elif k not in res.keys():
                        R.remove(k)
                        res[k] = depth
                        app.append(k)
        box = app

        if len(R) == 0:
            return depth


result = -1
for i in range(len(A)):
    J = confirm(i)
    if not J:
        continue
    if result < J:
        result = J
print(result)