Problem: 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.

Submission attempts (in order):
import sys, collections

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

    colq = collections.deque()
    colq.append((0, 0))
    while colq:
        now_node, now_col = colq.popleft()
        if col[now_node] == -1:
            col[now_node] = now_col
            for next_node in edge[now_col]: colq.append((next_node, 1 ^ now_col))
        else:
            if col[now_node] != now_col: 
                print(-1)
                break
    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 + 1)
        #print(dist_back)

    return 0

if __name__ == "__main__":
    solve()


import sys, collections

def solve():
    print(-1)
    return 0

if __name__ == "__main__":
    solve()

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 longest(i, edge, N):
    q = collections.deque()
    q.append((i, 1))
    dist = dict()
    ans = 1
    for j in range(N): dist[j] = -1
    flag = True
    while q:
        nn, nd = q.popleft()
        if dist[nn] == -1:
            ans = max(nd, ans)
            dist[nn] = nd
            for next_node in edge[nn]:
                if dist[next_node] == -1: q.append((next_node, nd + 1))
                elif abs(dist[next_node] - nd) != 1: flag = False
        elif dist[nn] != nd:
            ans = -1
            break
    #print(i, dist)
    return (ans if flag else -1)

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:
        ans = -1
        for i in range(N):
            ans = max(ans, longest(i, edge, N))
        print(ans)

    return 0

if __name__ == "__main__":
    solve()


Verdicts: Wrong Answer

Wrong Answer

Accepted