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
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
sys.setrecursionlimit(10**7)


def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        T = []
        for i, e in enumerate(S):
            if e == 1:
                T.append(i)
        G.append(T)
    
    def is_binarygraph(v, color):
        colors = [-1] * N
        colors[v] = color
        for n in G[v]:
            if colors[n] == color:
                return False
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, (color+1)%2):
                return False
        return True
    
    if not is_binarygraph(0, 0):
        return -1

    fw = floyd_warshall(G)
    return max(fw)

if __name__ == '__main__':
    print(main())

import sys
sys.setrecursionlimit(10**7)

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

def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        T = []
        for i, e in enumerate(S):
            if e == 1:
                T.append(i)
        G.append(T)
    
    def is_binarygraph(v, color):
        colors = [-1] * N
        colors[v] = color
        for n in G[v]:
            if colors[n] == color:
                return False
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, (color+1)%2):
                return False
        return True
    
    if not is_binarygraph(0, 0):
        return -1

    inf = 10**3
    d = [[inf]*N for _ in range(N)]
    for i in range(N):
        for j in range(G[i]):
            d[i][j] = 1
    
    fw = warshall_floyd(d)
    return max(fw)

if __name__ == '__main__':
    print(main())

import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
sys.setrecursionlimit(10**7)


def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        T = []
        for i, e in enumerate(S):
            if e == 1:
                T.append(i)
        G.append(T)
    
    colors = [-1] * N
    visited = [False] * N
    def is_binarygraph(v, color):
        visited[v] = True
        for n in G[v]:
            if colors[n] == color:
                return False
            if visited[n]:
                continue
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, colors[n]):
                return False
        return True
    
    colors[0] = 0
    if not is_binarygraph(0, 0):
        return -1

    inf = 10**3
    d = [[inf]*N for _ 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
    
    fw = floyd_warshall(d)
    return np.max(fw) + 1

if __name__ == '__main__':
    print(int(main()))

Verdicts: Time Limit Exceeded

Runtime Error

Accepted