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**6)
input = sys.stdin.readline

class LowLink:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.used = [0] * n
        self.ord = [0] * n
        self.low = [0] * n
        self.bridge = []
        self.articulation = []

    def dfs_lowlink(self, v, order, prev):
        order += 1
        self.used[v] = 1
        self.ord[v] = order
        self.low[v] = self.ord[v]

        is_articulation = False
        cnt = 0
        for to in self.adj[v]:
            if not self.used[to]:
                cnt += 1
                order = self.dfs_lowlink(to, order, v)
                self.low[v] = min(self.low[v], self.low[to])
                if prev != -1:
                    is_articulation |= self.low[to] >= self.ord[v]
                if(self.ord[v] < self.low[to]):
                    if v < to:
                        self.bridge.append((v, to))
                    else:
                        self.bridge.append((to, v))
            elif to != prev:
                self.low[v] = min(self.low[v], self.low[to])
        if prev == -1:
            is_articulation |= cnt > 1
        if is_articulation:
            self.articulation.append(v)
        return order

    def calc_lowlink(self):
        order = 0
        for i in range(self.n):
            if not self.used[i]:
                order = self.dfs_lowlink(i, order, -1)

    def dfs_decompose(self, v, label, prev):
        if prev != -1 and self.ord[prev] >= self.low[v]:
            self.comp[v] = self.comp[prev]
        else:
            label += 1
            self.comp[v] = label
        for to in self.adj[v]:
            if self.comp[to] == -1:
                label = self.dfs_decompose(to, label, v)
        return label

    def decompose(self):
        self.calc_lowlink()
        self.comp = [-1] * self.n

        label = -1
        for i in range(self.n):
            if self.comp[i] == -1:
                label = self.dfs_decompose(i, label, -1)
        edge = [[] for _ in range(label + 1)]
        for u, v in self.bridge:
            x = self.comp[u]; y = self.comp[v]
            edge[x].append(y)
            edge[y].append(x)
        return edge

n = int(input())
ab = []
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
                ab.append((i, j))
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

LL = LowLink(edge)
ans = 0
new_edge = LL.decompose()
if len(new_edge) == 1:
    print(-1)
    exit()
for index, edges in enumerate(new_edge):
    if len(edges) == 1:
        ans += 1
        continue
    vs = set()
    for i, v in enumerate(LL.comp):
        if v == index:
            vs.add(i)
    
    end = []
    for a, b in ab:
        if a in vs and b not in vs:
            end.append(a)
        if b in vs and a not in vs:
            end.append(b)
    ans += mat[end[0]-1][end[1]-1]
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra as di

n = int(input())
ad_lst = [list(map(int, input())) for _ in range(n)]
for i in range(n):
    for j in range(n):
        for k in range(n):
            if ad_lst[i][j] and ad_lst[i][k] and ad_lst[j][k]:
                print(-1)
                exit()

p_route = di(ad_lst)
ans = 0
print(int(max([max(i) for i in p_route])) + 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 += 1

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

Submission status: Wrong Answer

Solution code:
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 = int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
l=[]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            d[i][j] = 1
            l.append([i,j])
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
visited = [1]+[0 for i in range(n-1)]
while 0 in visited:
    for i in l:
        if visited[i[0]]!=0:
            if visited[i[0]]==1:
                if visited[i[1]]==1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=-1
            else:
                if visited[i[1]]==-1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=1
ans=0
for i in wf:
    ans=max(ans,max(i)+1)
print(ans)

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:
        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))

    #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())
ans = 0
g = []
for _ in range(n):
    row = input()
    tmp = []
    for i in row:
        tmp.append(int(i))
    g.append(tmp)
for i in range(n):
    cnt = 0
    for j in range(n):
        if g[j][i] == 1:
            cnt += 1
    if cnt % 2 == 1:
        ans += 1
if ans != 0:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
'''
二部グラフ判定
'''
max_d = 0
def dfs(v, c, d):
    global max_d
    max_d = max(max_d, 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
    return True
def solve():
    for i in range(N):
        if color[i] == 0:
            if not dfs(i, 1, 1):
                return False
    return True
N = int(input())
G = [[]for i in range(N)]
color = [0 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_d)
else:
    print(-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 += 1

if a % 2 != 0:
    print(-1)
else:
    print(n - a)

Submission status: Wrong Answer

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


# class Graph(object):
#     def __init__(self, N):
#         self.N = N
#         self.V = list(range(N))
#         self.E = [[] for _ in range(N)]

#     def add_edge(self, from_, to_):
#         self.E[from_].append(to_)
#         self.E[to_].append(from_)

#         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()
        visited[node] = True
        for i, c in enumerate(S[node]):
            if c == "1" and visited[i] is False:
                q.append(i)

    depth = [-2]*N
    q.append((node, 1))
    while len(q) > 0:
        node, d = q.popleft()
        depth[node] = d
        for i, c in enumerate(S[node]):
            if c == "0":
                continue
            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:
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()
print(n)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())

count = 0
i=0
join_flag =0
join_n = 0

if len(s)==1:
  print(k//2)
    
elif len(s)==2:
  if s[0]==s[1]:
    print(k)
  else:
    print(0)
  
elif len(set(s))==1:
  print(len(s)*k //2)
  
else:
  while i<len(s)-1:
    if s[i] == s[i+1]:
      count+=1
      i+=2
    else:
      i+=1
  
  if (s[-1] == s[0]) :
    join_flag =1
    
  if join_flag:  
    
    left_len = 1
    right_len = 1

    for i in range(len(s)-1):
      if s[i] == s[i+1]:
        left_len +=1
      else:
        break

    for i in range(len(s)-1):    
      if s[-1-i]==s[-2-i]:
        right_len +=1
      else:
        break            
    
    if (left_len + right_len) %2 ==0:        
      join_n = k-1
    else:
      join_n = k//2

  print(count*k + join_n)

Submission status: Wrong Answer

Solution code:
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 = int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
l=[[] for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            d[i][j] = 1
            l[i].append([i,j])
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
visited = [1]+[0 for i in range(n-1)]
"""
while 0 in visited:
    for i in l:
        if visited[i[0]]!=0:
            if visited[i[0]]==1:
                if visited[i[1]]==1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=-1
            else:
                if visited[i[1]]==-1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=1
"""
ans=0
for i in wf:
    ans=max(ans,max(i)+1)
print(ans)

Submission status: Wrong Answer

Solution code:
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)
        #print(dist_back)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

from collections import deque
from collections import defaultdict

g = defaultdict(set)

for i in range(N):
    for j in range(N):
        if s[i][j] == 1:
            g[i+1].add(j+1)
            g[j+1].add(i+1)

ans = -1
for i in range(N):
    q = []
    q.append(i+1)
    visit = [-1]*(N+1)
    visit[i+1] = 1
    temp = 0
    while q:
        now = q.pop()
        nextq = []
        for next in g[now]:
            if visit[next] == -1:
                visit[next] = visit[now] + 1
                nextq.append(next)
            else:
                if abs(visit[next] - visit[now]) == 1:
                    continue
                else:
                    temp = -1
        if temp == -1:
            break
        q = nextq[:]
    if temp != -1:
        ans = max(max(visit), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#  --*-coding:utf-8-*--


def f(N, S, st):
    R = [0]*(N)

    Q = set([st])
    R[st] = 1
    idx = 1
    cnt = 0

    while(len(Q) > 0):
        Q2 = set()
        cnt += 1
        idx += 1
        
        for i in Q:
            for j, s in enumerate(S[i]):
                if s == '1':
                    if R[j] == idx - 1:
                        return -1
                    elif R[j] == 0:
                        R[j] = idx
                        Q2.add(j)
                    
        Q = Q2
        
    return cnt
        


def g(N, S):
    m = 0

    for i in range(N):
        k = f(N, S, i)
        if k == -1:
            return -1

        m = max(m, k)

    return m



def main():
    N = int(input())
    S = list(input() for _ in range(N))

    print(g(N, S))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

class LowLink:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.used = [0] * n
        self.ord = [0] * n
        self.low = [0] * n
        self.bridge = []
        self.articulation = []

    def dfs_lowlink(self, v, order, prev):
        order += 1
        self.used[v] = 1
        self.ord[v] = order
        self.low[v] = self.ord[v]

        is_articulation = False
        cnt = 0
        for to in self.adj[v]:
            if not self.used[to]:
                cnt += 1
                order = self.dfs_lowlink(to, order, v)
                self.low[v] = min(self.low[v], self.low[to])
                if prev != -1:
                    is_articulation |= self.low[to] >= self.ord[v]
                if(self.ord[v] < self.low[to]):
                    if v < to:
                        self.bridge.append((v, to))
                    else:
                        self.bridge.append((to, v))
            elif to != prev:
                self.low[v] = min(self.low[v], self.low[to])
        if prev == -1:
            is_articulation |= cnt > 1
        if is_articulation:
            self.articulation.append(v)
        return order

    def calc_lowlink(self):
        order = 0
        for i in range(self.n):
            if not self.used[i]:
                order = self.dfs_lowlink(i, order, -1)

    def dfs_decompose(self, v, label, prev):
        if prev != -1 and self.ord[prev] >= self.low[v]:
            self.comp[v] = self.comp[prev]
        else:
            label += 1
            self.comp[v] = label
        for to in self.adj[v]:
            if self.comp[to] == -1:
                label = self.dfs_decompose(to, label, v)
        return label

    def decompose(self):
        self.calc_lowlink()
        self.comp = [-1] * self.n

        label = -1
        for i in range(self.n):
            if self.comp[i] == -1:
                label = self.dfs_decompose(i, label, -1)
        edge = [[] for _ in range(label + 1)]
        for u, v in self.bridge:
            x = self.comp[u]; y = self.comp[v]
            edge[x].append(y)
            edge[y].append(x)
        return edge

n = int(input())
ab = []
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
                ab.append((i, j))
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

LL = LowLink(edge)
ans = 0
new_edge = LL.decompose()
if len(new_edge) == 1:
    print(-1)
    exit()
for index, edges in enumerate(new_edge):
    if len(edges) == 1:
        ans += 1
        continue
    vs = set()
    for i, v in enumerate(LL.comp):
        if v == index:
            vs.add(i)
    
    end = []
    for a, b in ab:
        if a in vs and b not in vs:
            end.append(a)
        if b in vs and a not in vs:
            end.append(b)
    ans += mat[end[0]][end[1]] + 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for _ in range(n):
    s.append(input())
res = -1
flag = [-1 for i in range(n)]
for i in range(0, n):
    tres = 1
    flag = [-2 for i in range(n)]

    flag[i] = tres
    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)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int( input())
    S = [ list( map( int, list( input())[:-1])) for _ in range(N)]
    E = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == 1:
                E[i].append(j)
    
    d = deque([0])
    V = [-1]*N
    V[0] = 1
    
    while d:
        v = d.pop()
        now = V[v]
        for w in E[v]:
            if V[w] == -1:
                V[w] = now+1
                d.append(w)
                continue

            if (now + V[w])%2 == 1:
                continue
            print(-1)
            return
    ans = 2
    for i in range(N):
        d = deque([i])
        V = [-1]*N
        V[i] = 1
        while d:
            v = d.pop()
            now = V[v]
            for w in E[v]:
                if V[w] == -1:
                    V[w] = now+1
                    d.append(w)
        if max(V) > ans:
            ans = max(V)
    print(ans)
    
            
                
if __name__ == '__main__':
    main()

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()
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]
error = False
while len(nexcache) > 0:
    ne = nexcache.popleft()
    couho = set()
    maxc = 0
    for i in vr[ne]:
        couho.add(i+1)
        couho.add(i-1)
        if maxc < i+1:
            maxc = i
    for i in nex[ne]:
        if len(vr[i]) == 0:
            vr[i] = vr[i].union(couho)
            nexcache.append(i)
            if maxi < maxc:
                maxi = maxc
                maxii = i
        else:
            if len(couho & vr[i]) == 0:
                error = True
                break
    if error:
        break

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:
s = input()
n = len(s)
K = int(input())
L = 2
t = list(s*L)
s = list(s)
m = len(t)
cnt = 0
c = 0
for i in range(1, m):
    if t[i] == t[i-1]:
        t[i] = 'A'
        cnt+=1
for i in range(1, n):
    if s[i] == s[i-1]:
        s[i] = 'A'
        c+=1
res = c+(cnt-c)//L*(K-1)
if n == 1:
    res = K//2
print(res)

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())

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(col)

numbers = [-1]*n
ok = True

stack = [(0, 1)]
visited = [False]*n
visited[0] = True
while stack:
    curnode, curset = stack.pop()
    if numbers[curnode] != -1:
        if numbers[curnode] != curset:
            ok = False
            break
    else:
        numbers[curnode] = curset

    for nex in graph[curnode]:
        if visited[nex]:
            continue
        else:
            visited[nex] = True
            stack.append((nex, curset+1))

for i, j in edges:
    if abs(numbers[i]-numbers[j]) != 1:
        ok = False
        break

if not ok:
    print(-1)
else:
    maxidx = numbers.index(max(numbers))
    stack = [(maxidx, 1)]
    visited = [False]*n
    visited[maxidx] = True
    numbers = [-1]*n
    while stack:
        curnode, curset = stack.pop()
        numbers[curnode] = curset
        for nex in graph[curnode]:
            if visited[nex]:
                continue
            else:
                visited[nex] = True
                stack.append((nex, curset+1))

    print(max(numbers))

Submission status: Wrong Answer

Solution code:
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 = int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
l=[[] for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            d[i][j] = 1
            l[i].append([i,j])
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
ans=0
for i in wf:
    ans=max(ans,max(i)+1)
print(ans)

Submission status: Wrong Answer

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

from collections import deque
from collections import defaultdict

g = defaultdict(set)

for i in range(N):
    for j in range(N):
        if s[i][j] == 1:
            g[i+1].add(j+1)
            g[j+1].add(i+1)

color = [0 for i in range(N+1)]


color[1] = 1
que = deque([1])#始点を追加
bipartite = True

while len(que):
    p = que.popleft()#直近で追加したグラフの頂点を取得
    for q in list(g[p]):#結合しているグラフの頂点を参照
        if color[q] == 0:#塗られていないなら別の色で塗る
            color[q] = -color[p]
            que.append(q)
        elif color[q] == color[p]:#同じ色だったら2部グラフではないと返し終了させる
            bipartite = False
            break

if bipartite:
    ans = 0
    for i in range(N):
        q = []
        q.append(i+1)
        visit = [-1]*(N+1)
        visit[i+1] = 1
        temp = 0
        while q:
            now = q.pop()
            nextq = []
            for next in g[now]:
                if visit[next] == -1:
                    visit[next] = visit[now] + 1
                    temp = visit[next]
                    nextq.append(next)
                else:
                    if abs(visit[next] - visit[now]) == 1:
                        temp = visit[next]
                        continue
                    else:
                        temp = -1
            if temp == -1:
                break
            q = nextq[:]
        ans = max(temp, ans)
    print(ans+1)

else:
    print(-1)

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

possible = True
for home in range(N):
    used = [False] * N
    q = deque([(home, 0)])
    while len(q) > 0:
        src, dist = q.popleft()
        used[src] = True
        for dst in graph[src]:
            if dst == home and dist > 0:
                if dist % 2 == 0:
                    possible = False
                    break
            elif used[dst]:
                continue
            else:
                q.append((dst, dist + 1))
    #
    if possible == False:
        break
    
if possible:
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall
    #
    S = csr_matrix(S)
    dist = floyd_warshall(csgraph=S, directed=False)
    ans_tmp = int(np.max(dist)) + 1
    print(ans_tmp)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
'''
二部グラフ判定
'''

def dfs(v, c):
    color[v] = c
    for i in G[v]:
        if color[i] == c:
            return False
        if color[i] == 0 and not dfs(i, -c):
            return False
    return True
def solve():
    for i in range(N):
        if color[i] == 0:
            if not dfs(i, 1):
                return False
    return True
N = int(input())
G = [[]for i in range(N)]
color = [0 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(map(len, G))+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
s = [input() for i in range(n)]
q = deque([0])
d = [float('inf')] * n
d[0] = 0
while q:
    p = q.popleft()
    for i, c in enumerate(s[p]):
        if c == '1' and d[i] == float('inf'):
            d[i] = d[p] + 1
            q.append(i)
m = 0
for i in range(n):
    if d[m] < d[i]:
        m = i
q = deque([m])
d = [float('inf')] * n
d[m] = 0
while q:
    p = q.popleft()
    for i, c in enumerate(s[p]):
        if c == '1':
            if d[i] == float('inf'):
                d[i] = d[p] + 1
                q.append(i)
            elif d[i] != d[p] + 1 and d[i] != d[p] - 1:
                print(-1)
                exit(0)
m = 0
for i in range(n):
    m = max(m, d[i])
print(m + 1)

Submission status: Wrong Answer

Solution code:
import sys, collections

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

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
S = input()
K = int(input())

if len(S) == 1:
    print(K // 2)
    exit()
res, flag = 0, False
for i in range(1, len(S)):
    if i > 1 and S[i] == S[i-1] == S[i-2] and flag:
        flag = False
    elif S[i] == S[i-1]:
        res += 1
        flag = True
res *= K
if len(S) > 1 and (S[-1] == S[-2] or S[0] == S[1]):
    print(res)
    exit()
if S[0] == S[-1]:
    res += K - 1
print(res)