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

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_node=-1
mindeg=1000
for i in range(N):
  if mindeg>len(graph[i]):
    mindeg=len(graph[i])
    mindeg_node=i

#print(mindeg_node,mindeg)
#print(graph)
max_set=-1
for i in range(mindeg_node,mindeg_node+1):
  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:
N=int(input())
l=[[] for _ in range(N)]
for j in range(N):
  s=list(str(input()))
  for i in range(N):
    if s[i]=="1":
      l[j].append(i+1)
      
gk=[-1]*N
gk[0]=0
for i in range(N):
  for j in l[i]:
    if gk[j-1]==-1:
      gk[j-1]=1-gk[i]
    elif gk[j-1]!=1-gk[i]:
      print(-1)
      exit()

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#=True

inf=float('inf')
n=I()
s=[[inf]*n for _ in range(n)]
g=[[] for i in range(n)]
for r in range(n):
    ri=list(input())
    for c in range(n):
        if ri[c]=='1':
            s[r][c]=1
            g[r].append(c)  

def wf(d):
    n=len(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

d=wf(s)
diam=-1
bg=0
ed=n-1
for r in range(n):
    for i,dist in enumerate(d[r]):
        if i==r:
            continue
        if diam<dist:
            diam=dist
            bg=r
            ed=i

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append((x,0))
    while p:
        c,depth=p.popleft()
        v[c]=depth
        for i in g[c]:
            if v[i]==-1:
                p.append((i,depth+1))
    return

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(i, j)
                print(-1)
                exit()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

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)
    
    starts = []
    for i in range(N):
        if sum(G[i]) == 1:
            starts.append(i)
    
    if len(starts) == 0:
        return -1
    
    ans = []
    for start in starts:
        ans.append(f(start, N, G))
    
    return max(ans)
    
def f(start, N, G):
    cnt = 0
    n = [start]
    visited = [False] * N
    visited[start] = True
    while len(n) > 0:
        for (a, b) in combinations(n, 2):
            if G[a][b] == 1:
                return -1
        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:
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:
  print(3)
else:
  print(dist+1)

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

for i in range(n):
    dist[i][i] = 0
d = warshall_floyd(dist)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            for k in range(n):
                if i == k:
                    continue
                if S[j][k] == '1' and S[k][i] == '1':
                    print(-1)
                    quit()
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 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 dist[nn] != nd:
            ans = -1
            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(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:
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:
    flg = True
    zeros = tuple(ind for ind, p in enumerate(parity) if p == 0)

    for z1 in zeros:
        if any(z in e[z1] for z in zeros):
            flg = False
            break
    if not flg:
        print(-1)
        exit()

    ones = tuple(ind for ind, p in enumerate(parity) if p == 1)
    for o1 in ones:
        if any(one in e[o1] for one in ones):
            flg = False
            break

    if not flg:
        print(-1)
        exit()

    print(max(solve()) + 1)

    # print(zeros, ones)
    # print(parity)

Submission status: Wrong Answer

Solution code:
import collections

n=int(input())
arr=[input() for _ in range(n)]
g=[[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if arr[i][j]=='1':
      g[i].append(j)
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if arr[i][j]=='1' and arr[j][k]=='1' and arr[k][i]=='1':
        print(-1)
        exit()
ans=0
for v in range(n):
  q=collections.deque()
  q.append((v,1))
  checked=[0]*n
  while len(q)!=0:
    tmp,depth=q.popleft()
    ans=max(ans,depth)
    checked[tmp]=1
    for v in g[tmp]:
      if checked[v]==0:
        q.append((v,depth+1))
print(ans)

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)

  return len(l)

# main()
print(main())

Submission status: Wrong Answer

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

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



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 flag == 0:
    print(output+1)
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)
print(dist+1)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

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:
        for (a, b) in combinations(n, 2):
            if G[a][b] == 1:
                return -1
        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:
#!/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 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

for i in range(n):
    dist[i][i] = 0
d = warshall_floyd(dist)
for i in range(n):
    for j in range(n):
        if d[i][j] == 1:
            for k in range(n):
                if i == k:
                    continue
                if d[j][k] == 1 and d[k][i] == 1:
                    print(-1)
                    quit()
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:
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
        check.append(i)


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(res, max(flag))

print(res)

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=n
    e=0
    for i in range(1,n+1):
        if max(a.count(int(i)),b.count(int(i)))>1:
            ans-=1
            e=1
    print(ans+2 if e==1 else ans)

Submission status: Wrong Answer

Solution code:

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

import sys
import queue
q = queue.Queue()

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


visited = [False] * N


for i in range(N):
    a = getVlist(i)
    if len(a) == 1:
        break
    
    
cnt = 1
visited[i] = True
q.put(i)

while sum(visited) < N:
    nextv = []
    while not(q.empty()):
        nextv.append(q.get())
    nextv = list(set(nextv))
    #子の要素同士の連結チェック
    L = len(nextv)
    for i in range(L):
        visited[nextv[i]] = True
        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 getVlist(nv):
            if not(visited[v]):
                q.put(v)

    cnt += 1
    
#

print(cnt-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))
count = 0
for x in table:
    if len(table[x]) != 0:
        count += 1

print(count+1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

V = ni()
g = []
for i in range(V):
    k = ns()
    g.append([int(j) for j in list(k)])

import queue 

def containsOdd(G, src): 
    global V 
    colorArr = [-1] * V 
    
    colorArr[src] = 1
    q = queue.Queue() 
    q.put(src) 
    while (not q.empty()): 
        
        u = q.get() 
        if (G[u][u] == 1): 
            return True
        for v in range(V): 
            if (G[u][v] and colorArr[v] == -1): 
                colorArr[v] = 1 - colorArr[u] 
                q.put(v) 
            elif (G[u][v] and
                colorArr[v] == colorArr[u]): 
                return True
    return False


def f(G,v,p,seen):
    global V

    oq = (p,v)
    ss = seen[:]
    h = []

    for t in range(V):
        if G[v][t] == 1 and t not in seen:
            ss.append(t)
            h.append(t)

    for t in h:
        r = f(G,t,p+1,ss)
        if r[0] > oq[0]:
            oq = r

    return oq
    

if containsOdd(g, 0): 
    print(-1)
else: 
    a = [0]*V
    b = f(g,0,0,[0])
    c = f(g,b[1],0,[b[1]])
    print(c[0]+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)-2

# main()
print(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()
di = 1
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[nex[0][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+1
                if maxi < di+1:
                    maxi = di+1
                    maxii = i
            else:
                if dil[i] != di-1 and 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:
N=int(input())
S=[input() for _ in range(N)]
min_v=200
for i in range(N):
  v=S[i].count('1')
  if v<min_v:
    min_v=v
start_candidates=[]
for i in range(N):
  v=S[i].count('1')
  if v==min_v:
    start_candidates.append(i)
ans_lst=[]
for start in start_candidates:
  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
  ans_lst.append(ans)
print(max(ans_lst))

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

# main()
print(main())

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
        check.append(i)


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)

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))
r=int(np.amax(d)+1)
if np.any((np.sum(d == 1, axis=0) >= r)):
    print(-1)
else:
    print(r)

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:
    ans = 0
    for i in range(n):
        ans = max(ans, max(dfs(graph, n, i)) + 1)

    print(ans)

else:
    print(-1)