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:

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

import sys
import queue

def getVlist(x):
    reslist = []
    for i in range(N):
        if int(S[x][i]): reslist.append(i)
    return reslist

ans = 0
adj_list = [[]for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if int(S[i][j]):
            adj_list[i].append(j)
            adj_list[j].append(i)


for kk in range(N):
    q = queue.Queue()
    visited = [False] * N
    cnt = 1
    visited[kk] = True
    q.put(kk)
    VC = 1
    while VC < N:
        nextv = []
        while not(q.empty()):
            nextv.append(q.get())
        nextv = list(set(nextv))
        #子の要素同士の連結チェック
        L = len(nextv)
        for i in range(L):
            for j in range(i+1,L):
                if (int(S[nextv[i]][nextv[j]])):
                    print(-1)
                    sys.exit()
        
        for nv in nextv:
            for v in adj_list[nv]:
                if not(visited[v]):
                    visited[nextv[i]] = True
                    VC += 1
                    q.put(v)
        cnt += 1
        
    
    nextv = []
    while not(q.empty()):
        nextv.append(q.get())
    nextv = list(set(nextv))
    #子の要素同士の連結チェック
    L = len(nextv)
    for i in range(L):
        for j in range(i+1,L):
            if (int(S[nextv[i]][nextv[j]])):
                print(-1)
                sys.exit()
    
    ans = max(ans,cnt)
        
#
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(s):
    dist = [-1] * (N + 1)
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w] != -1:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d

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

# グラフの構築
g = [[] for i in range(N + 1)]
for i in range(N):
    for j in range(i + 1, N):
        if S[i][j] == "1":
            g[i + 1].append(j + 1)
            g[j + 1].append(i + 1)
#print(g)

# 三角loopが存在する場合は-1を出力（例外処理）
for i in range(1, len(g)):
    for v in g[i]:
        for v2 in g[v]:
            if i == v2:
                continue
            if i in g[v2]:
                print(-1)
                exit()

# 木の直径が答え（double-sweep）
u, _ = bfs(1)
v, d = bfs(u)
print(d + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
connect_matrix = [ list(input()) for i in range(n) ]

def bfs(x):
    node_set = [ None for i in range(n)]
    color_list = [ "White" for i in range(n) ]
    search_list = [x]
    d = 0
    node_set[x] = 0
    color_list[x] = "Black"
    ans = 0
    while search_list != []:
        d += 1
        new_search_list = []
        for i in search_list:
            for j, v in enumerate(connect_matrix[i]):
                if v == "1":
                    if color_list[j] == "White":
                        if node_set[j] is None:
                            node_set[j] = node_set[i] + 1

                        new_search_list.append(j)
                        color_list[j] = "Black"
                    else:
                        if (node_set[j] + node_set[i]) % 2 == 0:
                            ans = -1
        search_list = new_search_list
    return ans, d-1

first = bfs(0)

if first[0] == -1:
    print(-1)
else:
    second = bfs(first[1])
    print(second[1]+1)

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:
            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:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N = int(input())
S = [input().strip() for _ in range(N)]
C = [0]*N

flg = False
for sp, row in enumerate(S):
    if flg:
        break

    if row.count('1') == 1 or sp == len(S)-1:
        flg = True

        # start BFS
        C[sp] = 1
        q = deque([])
        for i, v in enumerate(row):
            if v == '1':
                q.append(int(i))

        cnt = 1 # length
        c = -1 # color
        while q:
            for i in range(len(q)):
                np_ind = q.popleft()
                if C[np_ind] == -c: # nutteru!
                    print(-1)
                    exit()
                elif C[np_ind] == c:
                    pass
                else:
                    C[np_ind] = c
                    for i, v in enumerate(S[np_ind]):
                        if v == '1' and C[i] == 0:
                            q.append(int(i))
            cnt += 1
            c *= -1

print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[[None,i] for i in range(N)]
g=[]
for i in range(N):
    S=input()
    r=[]
    for j in range(N):
        if S[j]=="1":
            r.append(j)
    g.append(r)
l[0][0]=0
a=-2
for _ in range(N-1):
    for i in range(1,N):
        for j in g[i]:
            if j!=0:
                l[i][1]=min(l[i][1],l[j][1])
            if l[i][0]==None:
                if l[j][0]==1:
                    l[i][0]=0
                elif l[j][0]==0:
                    l[i][0]=1
            else:
                if l[i][0]==l[j][0]:
                    a=-1
for _ in range(N+1):
    for i in range(1,N):
        for j in g[i]:
            if l[j][0]!=l[i][0]+1:
                break
        else:
            l[i][0]+=2
if a==-1:
    print(-1)
else:
    l.sort(reverse=1)
    a=l[0][0]+1
    for i in range(1,N):
        if l[i][1]!=l[0][1]:
            a+=l[i][0]
            break
    print(a)

Submission status: Wrong Answer

Solution code:
def f_b():
    from collections import deque
    n = int(input())
    s = [list(map(int, [i for i in input()])) for _ in range(n)]
    maxc = 0

    for i in range(n):
        q, next_q = [i], []
        c = 0
        layer = [0]*n

        while q:
            while q:
                node = q.pop()
                layer[node] = c+1
                for i, sij in enumerate(s[node]):
                    if sij==1:
                        if layer[i]>0 and layer[i]==c+1:
                            c, next_q = -1, []; break
                        if layer[i]==0:
                            next_q.append(i)
            q = next_q
            next_q = []
            c += 1

        maxc = max(maxc, c)

    print(c if maxc>0 else -1)

if __name__ == "__main__":
    f_b()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def dfs(graph: list, node: int, start: int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF] * node

    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    stack = [(0, start)]

    while stack:
        cost, cur_node = stack.pop()

        # 未探索のノードをstackに入れる
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node], nex_node))

    return dist

def judge(graph, edges):
    node = len(graph)
    start = 0

    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF] * node
    visited = [False]*n
    visited[0] = True

    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    stack = [(0, start)]

    while stack:
        cost, cur_node = stack.pop()

        # 未探索のノードをstackに入れる
        for nex_cost, nex_node in graph[cur_node]:
            if visited[nex_node]:
                continue
            if dist[nex_node] != INF:
                if dist[nex_node] != dist[cur_node] + nex_cost:
                    return False
            else:
                visited[nex_node] = True
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node], nex_node))

    for i, j in edges:
        if abs(dist[i]-dist[j]) != 1:
            return False

    return True

import numpy as np

n = ni()
grid = [lc() for _ in range(n)]
graph = [[] for _ in range(n)]
numgraph = np.zeros((n, n))
edges = []
for row, si in enumerate(grid):
    for col, sij in enumerate(si):
        if sij == "1":
            edges.append((row, col))
            graph[row].append((1, col))
            numgraph[row][col] = 1

# 二部グラフ判定
is_nibu = judge(graph, edges)

if is_nibu:
    from scipy.sparse.csgraph import floyd_warshall
    dists = floyd_warshall(numgraph)
    ans = 0
    for i in range(n):
        ans = max(ans, max(dists[i,:]))

    print(int(ans) + 1)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(s):
    dist = [-1] * (N + 1)
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w] != -1:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d

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

# グラフの構築
g = [[] for i in range(N + 1)]
for i in range(N):
    for j in range(i + 1, N):
        if S[i][j] == "1":
            g[i + 1].append(j + 1)
            g[j + 1].append(i + 1)
#print(g)

# 三角形が存在する場合は-1を出力（例外処理）
for i in range(1, len(g)):
    for v in g[i]:
        for v2 in g[v]:
            if i == v2:
                continue
            if i in g[v2]:
                print(-1)
                exit()

# 木の直径が答え
u, _ = bfs(1)
v, d = bfs(u)
print(d + 1)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
S = [list(input()) for i in range(N)]
table = collections.defaultdict(list)
for i in range(N):
    table[i+1] = []
    S[i] = list(map(int, S[i]))
for i in range(N):
    for j in range(N):
        if S[i][j] == 1:
            if i+1 not in table[j+1]:
                table[i+1].append(j+1)

for x in table:
    for y in table[x]:
        for z in table[y]:
            if z != x and z in table[x]:
                print(-1)
                exit(0)
for i in range(1, N+1):
    for x in table[i]:
        for y in table[x]:
            for z in table[y]:
                if z in table[i]:
                    table[i].pop(table[i].index(z))
                    table[y].pop(table[y].index(z))
count = 1
table = list(table.values())
table.sort(key=lambda x: len(x), reverse=True)
for i in range(len(table)):
    if len(table[i]) != 0:
        if i != 0:
            count += 1
        else:
            count += len(table[i])
print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque

import sys
import math
from collections import defaultdict, deque
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]
        pass

    def add_edge(self, from_, to_):
        """必ず0インデックスで入力すること。
        """
        self.E[from_].append((to_, 1))
        pass


def solve(N: int, S: "List[str]"):

    g = Graph(N)
    for i, s in enumerate(S):
        for j, c in enumerate(s):
            if c == "1":
                g.add_edge(i, j)

    visited = [False]*N
    q = deque()
    q.append(0)
    while len(q) > 0:
        node = q.popleft()
        if visited[node] == True:
            continue
        visited[node] = True
        for i, w in g.E[node]:
            if visited[i] is False:
                q.append(i)

    depth = [-2]*N
    q.append((node, 1))
    while len(q) > 0:
        node, d = q.popleft()
        if depth[node] != -2:
            continue
        depth[node] = d
        for i, w in g.E[node]:
            if depth[i] == -2:
                q.append((i, d+1))
            elif abs(d-depth[i]) != 1:
                print(-1)
                return
    print(d)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
m = []
import collections
for i in range(n):
    m.append(input())
line = []
for i in range(n + 1):
    line.append(collections.deque([]))

for i in range(n):
    for j in range(i,n):
        if m[j][i] == "1":
            line[i+1].append(j+1)

# 各点が所属する位置
group = [0] * (n+1)
group_min = 0
group_max = 0
group[1] = 0
#print(group)

can = True
for i in range(1, n + 1):
    #print("見るのは{0}です".format(i))
    lineto = []
    for j in range(i, 0, -1):
        #print("seek:{0}".format(j))
        usecount = 0
        for k in range( len(line[j]) ):
            #print("k = {0}, data = {1}".format(k, line[j]))
            if i < line[j][k]:
                #print(" no see [{0}] = {1}".format(k, line[j][k]))
                break
            usecount += 1
            item = line[j][k]
            #print("★pop = {0}".format(item))
            lineto.append(j)
        for k in range(usecount):
            item = line[j].popleft()
    #print("行くべきは{0}".format(lineto))
    groupto = list(map(lambda x: group[x], lineto))
    if len(groupto) == 0:
        #print("つながる先はないのでスキップ")
        continue
    #print("つながるべきグループは{0}".format(groupto))
    if (max(groupto) - min(groupto)) > 2:
        #print("繋がれません")
        can = False
        break
    elif (max(groupto) - min(groupto)) == 1:
        #print("繋がれません")
        can = False
        break
    elif (max(groupto) - min(groupto)) == 2:
        target = (max(groupto) + min(groupto)) // 2
        #print("間に存在しないといけません。 {1} = {0}".format(target, i))
        group[i] = target
    else:
        # なるべく差が開いている方がに送る
        if (max(groupto) + 1) > group_max:
            target = max(groupto) + 1
            #print("maxを更新できるのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_max += 1
        elif (min(groupto) + 1) > group_min:
            target = min(groupto) - 1
            #print("minを後進できるのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_min -= 1
        elif abs(max(groupto)) >= abs(min(groupto)):
            target = max(groupto) + 1
            #print("正のほうがおおきいか一緒なのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_max += 1
        else:
            target = min(groupto) - 1
            #print("負のほうが遠いのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_min -= 1
group = group[1:]
if can:
    print(1 + max(group) - min(group))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n=int(input())
l=[list(input()) for i in range(n)]
colors = [0 for i in range(n)]
es=[[] for i in range(n)]
Edges=es
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      es[i].append(j)
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()


def bfs(v):
    Visited=[False]*n
    q=deque()
    q.append((v,0))
    Visited[v]=True
    ret=(v,0)
    while q:
        fr,dist=q.popleft()
        if ret[1]<dist:
            ret=(fr,dist)
        for to in Edges[fr]:
            if not Visited[to]:
                Visited[to]=True
                q.append((to,dist+1))
    return ret

(v,dist)=bfs(0)
(v,dist)=bfs(v)
if dist==1 and n>=3:
  print(-1)
  sys.exit()
print(dist+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = []
for i in range(N):
    S.append(list(input()))

flag = 0



memo1 = [50000]*N
nows = set([0])
t = -1
visited = set([])

while True:
    t += 1
    next = set([])
    for now in nows:
        if t < memo1[now]:
            memo1[now]=t
            visited.add(now)
        temp = []
        for j in range(N):
            if (S[now][j]=='1')and(j not in visited):
                temp.append(j)
        next |= set(temp)
    nows = next
    if len(nows)==0:
        break

far1 = memo1.index(max(memo1))

memo2 = [50000]*N
nows = set([far1])
t = -1
visited = set([])

while True:
    t += 1
    next = set([])
    for now in nows:
        if t < memo2[now]:
            memo2[now]=t
            visited.add(now)
        temp = []
        for j in range(N):
            if (S[now][j]=='1')and(j not in visited):
                temp.append(j)
        next |= set(temp)
    nows = next
    if len(nows)==0:
        break
far2 = memo2.index(max(memo2))
output = max(memo2)

for i in range(N):
    for j in range(N):
        if (memo2[i]==memo2[j])and(S[i][j]=='1'):
            flag = 1
        if flag == 1:
            break
    if flag == 1:
        break

if flag == 0:
    print(output+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys, collections

def longest(i, edge, N):
    q = collections.deque()
    q.append((i, 1))
    dist = dict()
    ans = 1
    for j in range(N): dist[j] = -1
    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:
                    ans = -1
                    break
        if ans < 0: break

    #print(i, dist)
    return ans

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
d = {}
visited = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j, b  in enumerate(input()):
        if int(b):
            if j in d:
                d[j].append(i)
            else:
                d[j] = [i]
ans = 1

def dfs(cur, pre, c):
    if pre > 0 and not cur:
        return
    # print(c, cur)
    global ans
    ans = max(ans, c)
    for nex in d[cur]:
        if nex != pre and not visited[cur][nex]:
            visited[cur][nex] = 1
            dfs(nex, cur, c + 1)

dfs(0, -1, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[[None,i] for i in range(N)]
g=[]
for i in range(N):
    S=input()
    r=[]
    for j in range(N):
        if S[j]=="1":
            r.append(j)
    g.append(r)
l[0][0]=0
a=-2
for _ in range(N-1):
    for i in range(1,N):
        for j in g[i]:
            if j!=0:
                l[i][1]=min(l[i][1],l[j][1])
            if l[i][0]==None:
                if l[j][0]==1:
                    l[i][0]=0
                elif l[j][0]==0:
                    l[i][0]=1
            else:
                if l[i][0]==l[j][0]:
                    a=-1
                    break
for _ in range(N+1):
    for i in range(1,N):
        for j in g[i]:
            if l[j][0]!=l[i][0]+1:
                break
        else:
            l[i][0]+=2
if a==-1:
    print(-1)
else:
    l.sort(reverse=1)
    a=l[0][0]+1
    for i in range(1,N):
        if l[i][1]!=l[0][1]:
            a+=l[i][0]
            break
    print(a)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

s = np.empty((0,N), np.int8)

for _ in range(N):
    s = np.append(s, np.array([[int(c) for c in input()]], np.uint8), axis=0)


def get_gen(start):
    used = np.zeros(N, np.uint8)
    count = 1
    qlast = np.zeros(N, np.uint8)
    q = np.zeros(N, np.uint8)
    q[start] = 1
    used[start] = 1
    gen = 1

    while count != N and np.count_nonzero(q) != 0:
        nextset = np.zeros(N, np.uint8)
        for i in np.argwhere(q):
            nextset = np.logical_or(nextset, s[i])

        qfilter = np.logical_not(qlast)
        nextset = np.logical_and(qfilter, nextset)
        nextset = np.reshape(nextset, N)
        for i in np.argwhere(nextset):
            i = i[0]
            if used[i] != 0 and q[i] != 0:
                return -1
            used[i] = 1
            count += 1

        qlast = q
        q = nextset
        gen += 1

    if count != N:
        return -1
    return gen


ans = -1

for startIndex in range(N):
    ans = max(ans, get_gen(startIndex))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(s):
    dist = [-1] * (N + 1)
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w] != -1:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d

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

# グラフの構築
p = []
for i in range(N):
    for j in range(i + 1, N):
        if S[i][j] == "1":
            p.append([i + 1, j + 1])
#print(p)

g = [[] for i in range(N + 1)]
for pi in p:
    g[pi[0]].append(pi[1])
    g[pi[1]].append(pi[0])
#print(g)

# 三角形が存在する場合は-1を出力（例外処理）
for i in range(1, len(g)):
    for v in g[i]:
        for v2 in g[v]:
            if i == v2:
                continue
            if i in g[v2]:
                print(-1)
                exit()

# 木の直径が答え
u, _ = bfs(1)
v, d = bfs(u)
print(d + 1)

Submission status: Wrong Answer

Solution code:
N=int(input())

graph=[]
for i in range(N):
  graph.append([])

for i in range(N):
  S=list(map(int,input()))
  for j in range(N):
    if S[j]==1:
      graph[i].append(j)

mindeg=1000
for i in range(N):
  if mindeg>len(graph[i]):
    mindeg=len(graph[i])

mindeg_list=[]
for i in range(N):
  if mindeg==len(graph[i]):
    mindeg_list.append(i)

#print(mindeg_list,mindeg)
#print(graph)
max_set=-1
for i in mindeg_list:
  node_list=[-1]*N
  #bfs
  d=1
  queue=[i]
  illegal=False
  while(True):
    new_queue=[]
    for q in queue:
      node_list[q]=d
      for qq in graph[q]:
        if node_list[qq]==-1:
          new_queue.append(qq)
        elif node_list[qq]!=d-1:
          illegal=True
          break
      
    if illegal:
      break
    elif len(new_queue)==0:
      #print(node_list,d)
      max_set=max(max_set,d)
      break
    else:
      queue=new_queue
      d+=1
      
print(max_set)

Submission status: Wrong Answer

Solution code:
import copy

def f1(l1, li):
    ret = []
    for i in l1:
      for n,j in enumerate(li[i]):
        if j == 1:
            if j in used:
                return False
            elif n in tree[nest-1]:
            	pass
            else:
                ret.append(n)
    return list(set(ret))


N = int(input())
li = []
for _ in range(N):
    li.append(list(map(int,list(input()))))
    
max_nest = 0
for i in range(N):
    tree = [[]]
    used = []
    tree.append([i])
    nest = 1
    while True:
        ret = f1(tree[nest], li)
        nest += 1

        if ret == False:
            break
        elif ret != []:
            tree.append(ret)
            used.extend(tree[nest-2])
        else:
            if max_nest < nest:
                max_nest = nest
            break
        
print(max_nest-1)

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])
    D = defaultdict(int)
    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 D[c1 + 1]:
                        if abs(cost[nxt]) > abs(c1 - 1):
                            cost[nxt] = c1 - 1
                            que += [nxt]
                            D[c1 - 1] = 1
                    else:
                        if abs(cost[nxt]) > abs(c1 + 1):
                            cost[nxt] = c1 + 1
                            que += [nxt]
                            D[c1 + 1] = 1


    return len(set(cost))


print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[0] * N for i in range(N)]

for i in range(N):
    S = list(input())
    for j in range(N):
        graph[i][j] = int(S[j])
group = [-300] * N
group[0] = 1

answer = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if graph[i][j]:
            if group[j] == -300:
                group[j] = (group[i] + 1) % 2
            elif group[j] % 2 == group[i] % 2:
                print(-1)
                exit()
print(len(set(group)))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n=int(input())
l=[list(input()) for i in range(n)]
colors = [0 for i in range(n)]
es=[[] for i in range(n)]
Edges=es
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      es[i].append(j)
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()


def bfs(v):
    Visited=[False]*n
    q=deque()
    q.append((v,0))
    Visited[v]=True
    ret=(v,0)
    while q:
        fr,dist=q.popleft()
        if ret[1]<dist:
            ret=(fr,dist)
        for to in Edges[fr]:
            if not Visited[to]:
                Visited[to]=True
                q.append((to,dist+1))
    return ret

(v,dist)=bfs(0)
(v,dist)=bfs(v)
if n>=3 and dist==1:
  print(3)
else:
  print(dist+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[]
a=[1];b=[]
for i in range(n):
    x=list(map(str,input()))
    s.append(x)
    for j in range(n):
        if x[j]=='1':
            if i+1 in b:a.append(j+1)
            elif i+1 in a:b.append(j+1)
a=a[1:]
#print(a,b)
if set(a)&set(b):
    print(-1)
else:
    ans=0
    for i in range(1,n+1):
        if max(a.count(int(i)),b.count(int(i)))<=2:
            ans+=1
    print(ans)