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:
import sys
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)]
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()
 
x=0
connection=es
distance1=[-1 for i in range(n)]
distance1[x]=0
next=connection[x]
next2=[]
check=[-1 for i in range(n)]
check[x]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance1[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]
 
print(max(distance1)+1)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[list(S()) for _ in range(n)]

  stock=[]
  for i in range(n):
    for j in range(n):
      if i!=j:
        x=l[i]
        y=l[j]

        if y in stock:
          continue

        f=True
        for k in range(len(x)):
          if int(x[k])<int(y[k]):
            f=False
            break
        if f:
          stock.append(y)

  for x in stock:
    l.remove(x)

  if len(l)==n:
    if n!=2:
      return -1
    else:
      return 2
  return n-len(l)

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        G.append(S)
    
    visited = [False] * N
    start = -1
    for i in range(N):
        if sum(G[i]) == 1:
            start = i
            break
    
    if start == -1:
        return -1
    
    cnt = 0
    n = [start]
    visited[start] = True
    while len(n) > 0:
        cnt += 1
        n_ = []
        for s in n:
            for i, t in enumerate(G[s]):
                if visited[i]:
                    continue
                if t == 1:
                    n_.append(i)
                    visited[i] = True
        
        n = n_

    return cnt

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

Submission status: Wrong Answer

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

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)
if (output == 1)and(N!=2):
    print(-1)
else:
    print(output+1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

import sys

sys.setrecursionlimit(10 ** 7)


def solve():
    queue = []

    def find(root):
        INF = float('inf')
        best = [INF for _ in range(n)]
        best[root] = 0

        def find_next(cur):
            for u in e[cur]:
                dist = best[cur] + 1
                if dist < best[u]:
                    best[u] = dist
                    yield dist, u

        def dequeue():
            _, cur_v = heappop(queue)
            for nxt in find_next(cur_v):
                heappush(queue, nxt)

        while queue:
            dequeue()

        res = (0, root)
        for i in range(n):
            if best[i] > res[0]:
                res = (best[i], i)
        return res, best

    def run(root):
        heappush(queue, (0, root))
        return find(root)

    ret0, best0 = run(0)
    ret1, best1 = run(ret0[1])
    ret2, best2 = run(ret1[1])

    for i in range(n):
        yield max(best1[i], best2[i])


def dfs(v):
    for u in e[v]:
        if parity[u] == -1:
            parity[u] = parity[v] ^ 1
            if not dfs(u):
                return False
        else:
            if parity[v] == parity[u]:
                return False
    return True


n = int(input())
e = tuple(set() for _ in range(n))

for j in range(n):
    s = input()
    for ind, c in enumerate(s):
        if c == '1':
            e[j].add(ind)

# print(e)

parity = [-1] * n
parity[0] = 0

bg = dfs(0)
if not bg:
    print(-1)
else:
    print(max(solve()) + 1)

    # print(parity)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [list(map(int, list(input()))) for _ in range(N)]

graph = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j] == 1: graph[i].append(j)

from collections import deque

home = 0
ans_tmp = 0
possible = True
for i in range(3):
    iswhite = [None] * N
    q = deque([(home, False, 0)])
    iswhite[home] = False
    while len(q) > 0:
        src, white, depth = q.popleft()
        # print("##", src, white, depth)
        if depth > ans_tmp:
            home = src
            ans_tmp = depth
        #
        for dst in graph[src]:
            # print("###", dst, iswhite[dst])
            if iswhite[dst] == None:
                white_dst = (white != True)
                q.append((dst, white_dst, depth + 1))
                iswhite[dst] = white_dst
            elif white == iswhite[dst]:
                possible = False
                break
            else:
                continue
        #
        if possible == False:
            break
    
if possible:
    print(ans_tmp + 1)
else:
    # print("#", iswhite)
    print(-1)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[list(S()) for _ in range(n)]

  stock=[]
  for i in range(n):
    for j in range(n):
      if i!=j:
        x=l[i]
        y=l[j]

        if y in stock:
          continue

        f=True
        for k in range(len(x)):
          if int(x[k])<int(y[k]):
            f=False
            break
        if f:
          stock.append(y)

  for x in stock:
    l.remove(x)

  if len(l)==n and n!=2:
    return -1
  else:
    return 2
  return n-len(l)

# main()
print(main())

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[input() for _ in range(N)]
min_v=200
start=-1
for i in range(N):
  v=S[i].count('1')
  if v<min_v:
    min_v=v
    start=i
visited=[False for _ in range(N)]
visited[start]=True
current=[start]
ans=1
while True:
  flag=True
  candidates=[]
  for i in current:
    for j in range(N):
      if not visited[j] and S[i][j]=='1':
        candidates.append(j)
        visited[j]=True
  if not candidates:
    break
  #1 candidatesの中に辺を持つ頂点対があるとout
  for a in candidates:
    for b in candidates:
      if S[a][b]=='1':
        ans=-1
        flag=False
        break
    if not flag:
      break
  if not flag:
    break
  #1 end
  ans+=1
  current=candidates
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

n = int(input())
nex = [[] for _ in range(n)]
for i in range(n):
    ni = list(sys.stdin.readline().rstrip())
    for j in range(n):
        if ni[j] == '1':
            nex[i].append(j)

maxi = 0
maxii = 0
vr = [set() for _ in range(n)]
nexcache = deque()
di = 2
dil = [-1] * n
dil[0] = 0
vr[0].add(0)
for i in range(len(nex[0])):
        vr[nex[0][i]].add(1)
        vr[nex[0][i]].add(-1)
        nexcache.append(nex[0][i])
        maxi = 1
        maxii = nex[0][i]
        dil[i] = 1
error = False

while len(nexcache) > 0:
    nnx = []
    for ne in nexcache:
        couho = set()
        for i in vr[ne]:
            couho.add(i+1)
            couho.add(i-1)
        for i in nex[ne]:
            if dil[i] == -1:
                vr[i] = vr[i].union(couho)
                nnx.append(i)
                dil[i] = di
                if maxi < di:
                    maxi = di
                    maxii = i
            else:
                if dil[i] != di-1:
                    error = True
                    break
        if error:
            break
    di+=1
    nexcache = nnx

if error:
    print(-1)
    exit()
nexcache = [maxii]
minc = maxi
idl = [-500] * n
idl[maxii] = maxi
while len(nexcache) > 0:
    ne = nexcache.pop()
    gnum = idl[ne]
    if minc > gnum:
        minc = gnum
    for i in nex[ne]:
        if gnum -1 in vr[i] and idl[i] == -500:
            idl[i] = gnum-1
            nexcache.append(i)
print(maxi - minc+1)

Submission status: Wrong Answer

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
 
 
class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True

def main():
    d=defaultdict(list)
    n=int(input())
    for i in range(n):
        for k,j in enumerate(input()):
            if j=="1":
                d[i].append(k)
    #print(d)


    ans=-1
    for j in range(n):
        for r in range(j,n):
            u=UNION_FIND(n)
            for i in d[r]:
                u.union(r,i)
            x=[u.root(i) for i in range(j,r+1)]
            if len(Counter(x))<3:
                ans=max(len(x),ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#AGC39 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        weight[x] += weight[par[x]]
        par[x] = r
        return r

def union(x,y,w):
    rx = root(x)
    ry = root(y)
    if rank[rx] < rank[ry]:
        par[rx] = ry
        weight[rx] = w - weight[x] + weight[y]
    else:
        par[ry] = rx
        weight[ry] = - w - weight[y] + weight[x]
        if rank[rx] == rank[ry]:
            rank[rx] += 1
def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight[x] - weight[y]

def warshall_floyd(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

n = I()
S = [input() for _ in range(n)]
dist = [[inf]*n for _ in range(n)]
par = [i for i in range(n)]
weight = [0]*n
rank = [0]*n
for i in range(n):
    s = S[i]
    for j in range(i+1,n):
        if s[j] == '1':
            dist[i][j] = 1
            dist[j][i] = 1
            if not same(i,j):
                union(i,j,1)
            else:
                if diff(i,j) == 0:
                    print(-1)
                    quit()

for i in range(n):
    dist[i][i] = 0
d = warshall_floyd(dist)
ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans,d[i][j])
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[list(S()) for _ in range(n)]

  stock=[]
  for i in range(n):
    for j in range(n):
      if i!=j:
        x=l[i]
        y=l[j]

        if y in stock:
          continue

        f=True
        for k in range(len(x)):
          if int(x[k])<int(y[k]):
            f=False
            break
        if f:
          stock.append(y)

  for x in stock:
    l.remove(x)

  if len(l)==n and n!=2:
    return -1
  return n-len(l)

# main()
print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [list(map(int, list(input()))) for _ in range(N)]

graph = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j] == 1: graph[i].append(j)

from collections import deque

home = 0
ans_tmp = 0
possible = True
for i in range(2):
    iswhite = [None] * N
    q = deque([(home, False, 0)])
    while len(q) > 0:
        src, white, depth = q.popleft()
        # print("##", src, white, depth)
        iswhite[src] = white
        if depth > ans_tmp:
            home = src
            ans_tmp = depth
        #
        for dst in graph[src]:
            # print("###", dst, iswhite[dst])
            if iswhite[dst] == None:
                q.append((dst, (white != True), depth + 1))
            elif white == iswhite[dst]:
                possible = False
                break
            else:
                continue
        #
        if possible == False:
            break
    
if possible:
    print(ans_tmp + 1)
else:
    # print("#", iswhite)
    print(-1)

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


n = ni()
grid = [lc() for _ in range(n)]
graph = [[] for _ in range(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))

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

if is_nibu:
    # 0からdfs
    dist = dfs(graph, n, 0)

    # 0から最も遠い点からdfs
    dist2 = dfs(graph, n, dist.index(max(dist)))

    print(max(dist2)+1)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def is_int(x):
  return x == int(x)

def rec(statels,index,val):
  statels[index] = val
  if index == n-1:
    return len(set(statels))
  else:
    row = ls[index]
    for i in range(index+1,n):
      pass

n = int(input())
ls = [list(input().split()) for i in range(n)]

one = "1"
ans =[0.5+i for i in range(n)]

print(rec(ans,0,0))

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [list(map(int,input())) for i in range(n)]
Graph = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j]==1:
            Graph[i]+=[j]
colors = [0 for i in range(n)]

def is_bipartite(es):
    stack = [(0,1)]
    while stack:
        v,color = stack.pop()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.append((to, -color))
    return True

if not is_bipartite(Graph):
    print(-1)
    exit()

S2 = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j]==1:
            S2[i][j]=1
        elif i==j:
            S2[i][j]=0

def warshall_floyd(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

warshall_floyd(S2)

diam = 0
for i in range(n):
    for j in range(n):
        diam = max(diam,S2[i][j])
print(diam)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall 

n = int(input())
s = list()
for i in range(n):
    s.append([int(x) for x in list(input())])
d=floyd_warshall(csr_matrix(s))
print(int(np.amax(d)+1))

Submission status: Wrong Answer

Solution code:
import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
g = [0] * 201
a = 0
for i in range(n):
    s = ns()
    for si in s:
        if si == "1":
            g[i] += 1
for i in g:
    if i != 0 and i % 2 == 0:
        a += i // 2
if a > 2:
    print(-1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys, collections

def longest(i, edge, N):
    q = collections.deque()
    q.append(({i}, 1))
    dist = dict()
    ans = 0
    for i in range(N): dist[i] = -1
    flag = True
    while q:
        ns, nd = q.popleft()
        next_set = set()
        for nn in ns:
            if dist[nn] != -1:
                flag = False
                break
            ans = max(nd, ans)
            dist[nn] = nd
            for next_node in edge[nn]:
                if dist[next_node] == -1: next_set |= {next_node}
        if flag and len(next_set) > 0: q.append((next_set, nd + 1))

    #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] = -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:
        ans = 0
        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:
'''
二部グラフ判定
'''
def dfs(v, c, d):
    color[v] = c
    for i in G[v]:
        if color[i] == c:
            return False
        if color[i] == 0 and not dfs(i, -c, d+1):
            return False
    ds[v] += d
    return True
def solve():
    for i in range(N):
        if color[i] == 0:
            if not dfs(i, 1, 0):
                return False
    return True
N = int(input())
G = [[]for i in range(N)]
color = [0 for i in range(N)]
ds = [1 for i in range(N)]
for i in range(N):
    S = input()
    for j, s in enumerate(S):
        if s == '1':
            G[i].append(j)
ans = solve()
if ans:
    print(max(ds))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = {i: [] for i in range(1,N+1)}
for i in range(N):
    row = input()
    for j in range(i+1, N):
        if row[j] == '1':
            V[i+1].append(j+1)
            V[j+1].append(i+1)

pass
INF = float('inf')
def get_farest(s):
    H = deque()
    visited = {i: False for i in range(1,N+1)}
    dist = {i: INF for i in range(1,N+1)}
    dist[s] = 0
    distmax = 0
    invalid = False
    H.append(s)
    t = s
    while len(H):
        u = H.popleft()
        visited[u] = True
        for v in V[u]:
            if visited[v]:
                continue
            if dist[v] == INF:
                dist[v] = dist[u] + 1
                if distmax < dist[v]:
                    distmax = dist[v]
                    t = v
            else:
                if dist[v] - dist[u] != 1:
                    invalid = True
                    break
            H.append(v)
    
    if invalid:
        return -1, None
    return distmax, t

dist, f = get_farest(1)
if dist < 0:
    print(dist)
else:
    diameter, _ = get_farest(f)
    print(diameter+1)

Submission status: Wrong Answer

Solution code:
import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
g = [0] * 201
a = 0
for i in range(n):
    s = ns()
    for si in s:
        if si == "1":
            g[i] += 1
for i in g:
    if i != 0 and i % 2 == 0:
        a += i // 2

if a > 2:
    print(-1)
else:
    print(n - a)

Submission status: Wrong Answer

Solution code:
import collections
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        S = input().rstrip()
        K = int(input())

        if len(S) == 1:
            print(K // 2)
            exit()

        ans = 0
        start = 0
        end = len(S)
        cnt_1 = 1
        cnt_2 = 1

        if len(collections.Counter(S)) == 1:
            print((len(S) * K) // 2)
            exit()

        if S[0] == S[-1]:
            for i in range(1, len(S) - 1):
                if S[i] != S[0]:
                    start = i
                    break
                else:
                    cnt_1 += 1

            for i in range(1, len(S) - 1)[::-1]:
                if S[i] != S[0]:
                    end = i + 1
                    break
                else:
                    cnt_2 += 1

            ans += (cnt_1 // 2) + ((cnt_1 + cnt_2) // 2) * (K - 1) + (cnt_2 // 2)

        before = S[start]
        length = 1
        changes = 0
        for i in range(start + 1, end):
            if S[i] == before:
                length += 1
            else:
                changes += length // 2
                length = 1
                before = S[i]

        changes += length // 2
        ans += changes * K
        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
import sys, collections

def longest(i, edge, N):
    q = collections.deque()
    q.append(({i}, 1))
    dist = dict()
    ans = 0
    for i in range(N): dist[i] = -1
    while q:
        ns, nd = q.popleft()
        next_set = set()
        for nn in ns:
            ans = max(nd, ans)
            dist[nn] = nd
            for next_node in edge[nn]:
                if dist[next_node] == -1: next_set |= {next_node}
        if len(next_set) > 0: q.append((next_set, nd + 1))

    #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(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 = 0
        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:
n = int(input())
s = []
for _ in range(n):
    s.append(input())
check = []
testc = 1000
for i in range(n):
    test = 0
    for c in s[i]:
        test += int(c)
    if test == testc:
        check.append(i)
    elif test < testc:
        check.clear()
        testc = test


res = -1
for i in check:
    tres = 1
    flag = [-2 for i 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:
                    tres = -1
                    break

    if tres == -1:
        continue
    else:
        res = max(tres, max(flag))

print(res)