Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque


def main():
        
    N = int(input())
    es = [[] for _ in range(N)]

    for i in range(N):
        s = input()
        for j in range(N):
            if i == j:
                continue
            if s[j] == "1":
                es[i-1].append(j-1)
                es[j-1].append(i-1)


    """
    あるノードを始点として、幅優先的に色塗りをしていく。
    これを、全ノードを始点にして試す
    """
    ans = -1
    for i in range(N):
        color = [0] * N
        
        q = deque()
        q.append((i, 1))
        tmp = 1
        flag = True
        while q and flag:
            node, c = q.popleft()
            color[node] = c
            
            for nxt in es[node]:
                if color[nxt] != 0:
                    if abs(color[node] - color[nxt]) != 1:
                        flag = False
                        break
                else:
                    q.append((nxt, c+1))
                    tmp = max(c+1, tmp)


        if flag:
            ans = max(ans, tmp)

    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
"""
AtCoder Grand Contest 039  B - Graph Partition / 


（１）ある集合V_iに含まれるノードから伸びる辺について、その先の集合がV_i-1かV_i+1になるように分ける
（２）その時の集合の個数の最大値を求める

（１）を言い換えると、あるノードが偶数番の集合に属しているとき、それと繋がっているノードが奇数番号の集合かつ差が１である
　→二部グラフ
（２）V_1とV_kがあるとき、少なくともそれらはk本の辺をたどらなければ繋がれないはずなので、最も距離の長い辺（直径）を探す
"""

from collections import deque

N = int(input())
es = [[] for _ in range(N)]

for i in range(N):
    S = input()
    for j in range(N):
        if S[j] == "1":
            es[i].append(j)


q = deque()
q.append(0)
checked = [0] * N
checked[0] = 1
while q:
    curr = q.popleft()
    for nxt in es[curr]:
        # 未探索なので、currと別の集合に設定
        if checked[nxt] == 0:
            checked[nxt] = checked[curr] * -1
            q.append(nxt)
        else:
            # 探索済みなので、別の集合に属しているか確認し、同じであれば条件を満たさない
            if checked[nxt] == checked[curr]:
                print(-1)
                exit()



# グラフの直径を求める。それぞれのノードをスタート地点として、全ノード間の距離を求めたときの最大距離が直径
ans = 0
for i in range(N):
    q = deque()
    q.append(i)
    dist = [0] * N
    # 距離＋１が答えなので、起点を１としておく
    dist[i] = 1
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[nxt] == 0:
                dist[nxt] = dist[curr] + 1
                q.append(nxt)

    ans = max(ans, max(dist))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque

N = int(input())
es = [[] for _ in range(N)]

for i in range(N):
    s = input()
    for j in range(N):
        if i == j:
            continue
        if s[j] == "1":
            es[i-1].append(j-1)
            es[j-1].append(i-1)


"""
あるノードを始点として、幅優先的に色塗りをしていく。
これを、全ノードを始点にして試す
"""
ans = -1
for i in range(N):
    color = [0] * N
    
    q = deque()
    q.append((i, 1))
    flag = True
    while q and flag:
        node, c = q.popleft()
        color[node] = c
        for nxt in es[node]:
            if color[nxt] != 0:
                if abs(color[node] - color[nxt]) != 1:
                    flag = False
                    break
            else:
                q.append((nxt, c+1))


    if flag:
        ans = max(ans, max(color))

print(ans)

Fixed submission:
"""
AtCoder Grand Contest 039  B - Graph Partition / 


（１）ある集合V_iに含まれるノードから伸びる辺について、その先の集合がV_i-1かV_i+1になるように分ける
（２）その時の集合の個数の最大値を求める

（１）を言い換えると、あるノードが偶数番の集合に属しているとき、それと繋がっているノードが奇数番号の集合かつ差が１である
　→二部グラフ
（２）V_1とV_kがあるとき、少なくともそれらはk本の辺をたどらなければ繋がれないはずなので、最も距離の長い辺（直径）を探す
"""

from collections import deque

N = int(input())
es = [[] for _ in range(N)]

for i in range(N):
    S = input()
    for j in range(N):
        if S[j] == "1":
            es[i].append(j)


q = deque()
q.append(0)
checked = [0] * N
checked[0] = 1
while q:
    curr = q.popleft()
    for nxt in es[curr]:
        # 未探索なので、currと別の集合に設定
        if checked[nxt] == 0:
            checked[nxt] = checked[curr] * -1
            q.append(nxt)
        else:
            # 探索済みなので、別の集合に属しているか確認し、同じであれば条件を満たさない
            if checked[nxt] == checked[curr]:
                print(-1)
                exit()



# グラフの直径を求める。それぞれのノードをスタート地点として、全ノード間の距離を求めたときの最大距離が直径
ans = 0
for i in range(N):
    q = deque()
    q.append(i)
    dist = [0] * N
    # 距離＋１が答えなので、起点を１としておく
    dist[i] = 1
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[nxt] == 0:
                dist[nxt] = dist[curr] + 1
                q.append(nxt)

    ans = max(ans, max(dist))

print(ans)