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())
l=[[] for i in range(n+1)]
for i in range(1,1+n):
  l1=list(input())
  for j in range(1,1+n):
    if l1[j-1]=="1":
      l[i].append(j)
color=[0 for i in range(n+1)]
b=True
def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(l[v])):
        if color[ l[v][i] ] == c:
            return False
        elif color[ l[v][i] ] == 0 and not f(l[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
b=f(1,1)
if not b:
  print(-1)
else:
  inf=10**10
  d=[[inf for i in range(n+1)] for j in range(n+1)]
  for i in range(n+1):
    for j in l[i]:
      d[i][j]=1
  for k in range(n+1):
    for j in range(1,n+1):
      for i in range(1,n+1):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  max=0
  for i in range(1,n+1):
    for j in range(1,n+1):
      if d[i][j]>max:
        max=d[i][j]
  print(max+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[] for i in range(n+1)]
for i in range(1,1+n):
  l1=list(input())
  for j in range(1,1+n):
    if l1[j-1]=="1":
      l[i].append(j)
color=[0 for i in range(n+1)]
b=True
def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(l[v])):
        if color[ l[v][i] ] == c:
            return False
        elif color[ l[v][i] ] == 0 and not f(l[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
b=f(1,1)
if not b:
  print(-1)
else:
  inf=10**10
  d=[[inf for i in range(n+1)] for j in range(n+1)]
  for i in range(n+1):
    for j in l[i]:
      d[i][j]=1
  for k in range(n+1):
    for j in range(1,n+1):
      for i in range(1,n+1):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  max=0
  for i in range(1,n+1):
    for j in range(1,n+1):
      if d[i][j]>max:
        max=d[i][j]
  print(max+1)

Submission status: Wrong Answer

Solution code:
#B-Graph Partition
n=int(input())
uselist=[[] for i in range(n+1)]
distancelist=[[10**5 for j in range(n)] for i in range(n)]
for i in range(n):
    s=input()
    for j in range(n):
        if int(s[j])!=0:
            distancelist[i][j]=1
            distancelist[j][i]=1
            uselist[i+1].append(j+1)
#各辺がどの点とつながっているかをuselistないに保存する
for i in range(n):
    distancelist[i][i]=0
visitedlist=[-1 for i in range(n)]
pointlist=[0 for j in range(n)]
flag=True
def search(i,string):
    visitedlist[i-1]=1
    if string==0:
        pointlist[i-1]="B"
    else:
        pointlist[i-1]=string
    flags=False 
    for node in uselist[i]:
        if visitedlist[node-1]==-1:
            #訪れていない点を発見した場合
            flags=True
            visitedlist[node-1]=1
            if string=="B"or string==0:
                pointlist[node-1]="R"
            elif string=="R":
                pointlist[node-1]="B"
        else:
            pass
    if flags:
        #一度でも訪れられた点がある時
        for j in uselist[i]:
            search(j,pointlist[j-1])
    if not flags:
        # 全ての点がすでにvisitedだった時
        pass    
search(1,0)
for j in range(1,n+1):
    for some in uselist[j]:
        if pointlist[j-1]==pointlist[some-1]:
            flag=False
            break
            
class Dijkstra():
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d
disdis=Dijkstra(n+1)
for i in range(1,n+1):
    for j in uselist[i]:
        disdis.add(i,j,1)
        disdis.add(j,i,1)
d = disdis.shortest_path(1)
del d[0]
farway=0
index=0
for i in range(n):
    if d[i]>farway:
        farway=d[i]
        index=i+1
ddr = disdis.shortest_path(index)
del ddr[0]
ans=max(ddr)
if flag:
    print(ans+1)
else:
     print(-1)

Submission status: Wrong Answer

Solution code:
#B-Graph Partition
n=int(input())
uselist=[[] for i in range(n+1)]
distancelist=[[10**5 for j in range(n)] for i in range(n)]
for i in range(n):
    s=input()
    for j in range(n):
        if int(s[j])!=0:
            distancelist[i][j]=1
            distancelist[j][i]=1
            uselist[i+1].append(j+1)
#各辺がどの点とつながっているかをuselistないに保存する
for i in range(n):
    distancelist[i][i]=0
visitedlist=[-1 for i in range(n)]
pointlist=[0 for j in range(n)]
flag=True
def search(i,string):
    visitedlist[i-1]=1
    if string==0:
        pointlist[i-1]="B"
    else:
        pointlist[i-1]=string
    flags=False 
    for node in uselist[i]:
        if visitedlist[node-1]==-1:
            #訪れていない点を発見した場合
            flags=True
            visitedlist[node-1]=1
            if string=="B"or string==0:
                pointlist[node-1]="R"
            elif string=="R":
                pointlist[node-1]="B"
        else:
            pass
    if flags:
        #一度でも訪れられた点がある時
        for j in uselist[i]:
            search(j,pointlist[j-1])
    if not flags:
        # 全ての点がすでにvisitedだった時
        pass    
search(1,0)
for j in range(1,n+1):
    for some in uselist[j]:
        if pointlist[j-1]==pointlist[some-1]:
            flag=False
            
class Dijkstra():
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d
disdis=Dijkstra(n+1)
for i in range(1,n+1):
    for j in uselist[i]:
        disdis.add(i,j,1)
        disdis.add(j,i,1)
d = disdis.shortest_path(1)
del d[0]
farway=0
index=0
for i in range(n):
  if d[i]>farway:
    farway=d[i]
    index=i
index=index+1
for i in range(1,n+1):
    for j in uselist[i]:
        disdis.add(i,j,1)
        disdis.add(j,i,1)
ddr = disdis.shortest_path(index)
del ddr[0]
ans=max(ddr)
if flag:
	print(ans+1)
else:
 	print(-1)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
mat = [[1 if c == "1" else float('inf')
        for c in input()[:-1]] for _ in range(N)]
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])
print(max([max(m) for m in mat])+1)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
mat = [[1 if c == "1" else float('inf')
        for c in input()[:-1]] for _ in range(N)]

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])
ans = 0
for i in range(N):
    for j in range(N):
        if mat[i][j] != float('inf'):
            ans = max(mat[i][j], ans)
print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
mat = [[1 if c == "1" else float('inf')
        for c in input()[:-1]] for _ in range(N)]

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])
print(max([max(m) for m in mat])+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    A=[list(map(int,list(input()))) for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==0): A[i][j]=INF
    B=[a[:] for a in A] # deep copy
    E=[[] for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==1): E[i].append(j)

    # bipartile check
    d=[-1]*n # -1: unvisited
    def dfs(v,p=-1)->bool:
        # initialize
        if(p==-1):
            if(d[v]!=-1): return True
            else: d[v]=0
        # iterate
        res=True
        for nv in E[v]:
            if(nv==p): continue
            if(d[nv]==-1):
                d[nv]=d[v]^1
                dfs(nv,v)
            else:
                res=min(res,d[nv]^d[v])
        return res

    for v in range(n):
        if(not dfs(v)):
            print(-1)
            return

    # Warshall-Floyd
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])

    # output
    diam=0
    for i,j in product(range(n),repeat=2):
        if(B[i][j]==INF): continue # connectedなのｄ必要ない
        diam=max(diam,B[i][j])
    print(diam+1)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
S = [list(map(int, list(i))) for i in read().split()]

distance = floyd_warshall(S, directed=False)
distance = [list(map(int, i)) for i in distance]

if S == distance:
    print(-1)
else:
    print(max([max(i) for i in distance]) + 1)

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
S = [list(map(int, list(i))) for i in read().split()]

print(S)
distance = floyd_warshall(S, directed=False)
distance = [list(map(int, i)) for i in distance]

if S == distance:
    print(-1)
else:
    print(max([max(i) for i in distance]) + 1)

Submission status: Wrong Answer

Solution code:
def bfs(dp, arr, i,  visited):
	q = []
	q.append(i)
	visited[i] = True
	while q:
		i = q.pop(0)
		visited[i] = True
		for j in arr[i]:
			if dp[j] == -1:
				dp[j] = dp[i] + 1
			elif dp[i] == dp[j]:
				return -1
			
			if visited[j] == False:
				visited[j] = True
				q.append(j)
	return 0

n=int(input())
i=0
arr=[]
degree = [0]*n
while i<n:
	s=input()
	a=[]
	for j,e in enumerate(s):
		if e=='1':
			a.append(j)
			degree[i]+=1
	arr.append(a)	
	i+=1

res = -1
ans = -1
for i in range(n):
	dp = [-1]*n
	visited=[False for x in range(n)]
	if degree[i] == 1:
		dp[i] = 1
		res=bfs(dp, arr, i, visited)
		if res  == 0:
			ans = max(ans , max(dp))

print(ans)

Submission status: Wrong Answer

Solution code:
def bfs(dp, arr, i,  visited):
	q = []
	q.append(i)
	visited[i] = True
	while q:
		i = q.pop(0)
		visited[i] = True
		for j in arr[i]:
			if dp[j] == -1:
				dp[j] = dp[i] + 1
			elif dp[i] == dp[j]:
				return -1
			if visited[j] == False:
				visited[j] = True
				q.append(j)
	return 0

n=int(input())
i=0
arr=[]
degree = [0]*n
while i<n:
	s=input()
	a=[]
	for j,e in enumerate(s):
		if e=='1':
			a.append(j)
			degree[i]+=1
	arr.append(a)	
	i+=1
#print(arr)
dp = [-1]*n
res=-1
visited=[False for x in range(n)]
for i in range(n):
	if degree[i] == 1:
		dp[i] = 1
		res=bfs(dp, arr, i, visited)
		break;
#print(dp)
if res == 0:
	print(max(dp))
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
import sys
# import networkx as nx
import numpy as np
from scipy.sparse.csgraph import dijkstra
# import matplotlib.pyplot as plt

n = int(input())
s = np.array([list(input()) for _ in range(n)]).astype(np.int64)

# print(s)

# g = nx.Graph()

# g.add_nodes_from(range(n))
# for i in range(s.shape[0]):
#     for j in range(s.shape[1]):
#         if s[i, j] == 1:
#             g.add_edge(i, j)

shotest = dijkstra(s)
#print(shotest)
print(int(np.max(shotest)+1))

# nx.draw_networkx(g)
# plt.show()

Submission status: Wrong Answer

Solution code:
import sys
# import networkx as nx
import numpy as np
from scipy.sparse.csgraph import dijkstra
# import matplotlib.pyplot as plt

n = int(input())
s = np.array([list(input()) for _ in range(n)]).astype(np.int64)

# print(s)

# g = nx.Graph()

# g.add_nodes_from(range(n))
# for i in range(s.shape[0]):
#     for j in range(s.shape[1]):
#         if s[i, j] == 1:
#             g.add_edge(i, j)

shotest = dijkstra(s)
#print(shotest)
print(np.max(shotest)+1)

# nx.draw_networkx(g)
# plt.show()

Submission status: Wrong Answer

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

# for s in S:
#     print (s)

lst = [0] * N
lst[0] = 1

stack = [0]
flag = True
while len(stack) != 0:
    tmp = stack.pop()
    for index, x in enumerate(S[tmp]):
        if x == 0:
            continue
        if lst[index] == 0:
            lst[index] = -lst[tmp]
            stack.append(index)
        else:
            if lst[tmp] == -lst[index]:
                pass
            else:
                flag = False
                break
    if not flag:
        print (-1)
        exit()

from collections import deque
def bfs(x):
    memo = [-1] * N
    memo[x] = 0
    que = deque()
    que.append(x)
    ans = 0
    while len(que) != 0:
        tmp = que.popleft()
        for index, x in enumerate(S[tmp]):
            if x == 0:
                continue
            if memo[index] == -1:
                memo[index] = memo[tmp] + 1
                if ans < memo[index]:
                    ans = memo[index]
                    goal = index
                que.append(index)
    return goal, ans
    

start, ans = bfs(0)
goal, ans = bfs(start)
print (ans + 1)

Submission status: Wrong Answer

Solution code:
# 二部グラフかどうかの判定法
#二個だけTLEだった泣
import sys
n=int(input())
s=[list(input()) for _ in range(n)]
g=[[] for _ in range(n+1)]
for i in range(n):
    for j in range(i+1,n):
        if s[i][j]=="1":
            g[i+1].append(j+1)
            g[j+1].append(i+1)
#二部グラフかどうかの判定
flag=[-1]*(n+1)
forest=[]
for i in range(1,n+1):
    U=[]
    if flag[i]==-1:
        que=[[i]]
        j=1
        flag[i]=1
        while que:
            h=que.pop()
            H=[]
            for u in h:
                flag[u]=j%2
                U.append(u)
                for v in g[u]:
                    if flag[v]==-1:
                        H.append(v)
                        flag[v]=(j+1)%2
                    elif flag[v]==j%2:
                        print(-1)
                        sys.exit()
            if H:
                que.append(H)
            j+=1
    if U:
        forest.append(U)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [list(map(int, input())) for i in range(N)]
G = [[float('inf')] * N for i in range(N)]

for i in range(N):
    for j in range(N):
        if S[i][j]:
            G[i][j] = 1

for i in range(N):
    G[i][i] = float('inf')

for k in range(N):
    for i in range(N):
        for j in range(N):
            if (G[i][j] == 1) and (G[i][k] == 1) and (G[j][k] == 1):
                print(-1)
                exit()
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])

for i in range(N):
    G[i][i] = 1

ans = max([max(g) for g in G])
print(ans + 1)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[input() for i in range(N)]
l=[None]*N
l[0]=0
a=0
while None in l:
    for i in range(1,N):
        for j in range(N):
            if S[i][j]=="1":
                if l[i]==None:
                    if l[j]==1:
                        l[i]=0
                    elif l[j]==0:
                        l[i]=1
                elif l[i]==l[j]:
                    a=-1
                    break
print(a)

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

D=[]
for i in range(1,N+1):
  seen=[-1]*N
  seen[i-1]=0
  unseen=[i]
  d=0
  while unseen:
    u=unseen.pop(0)
    for j in l[u-1]:
      if seen[j-1]==-1 and j not in unseen:
        unseen.append(j)
        seen[j-1]=seen[u-1]+1
        
  D.append(max(seen))

print(max(D)+1)

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

D=[]
for i in range(1,N+1):
  seen=[]
  unseen=[i]
  d=0
  while unseen:
    u=unseen.pop(0)
    seen.append(u)
    d_=0
    for j in l[u-1]:
      if j not in seen and j not in unseen:
        unseen.append(j)
        d_+=1
    if d_>0:
      d+=1
  D.append(d)
print(max(D)+1)

Submission status: Wrong Answer

Solution code:
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int32([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print(-(s[i][:,i].any()|s[j][:,j].any()or~int(m.max())))

Submission status: Wrong Answer

Solution code:
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int32([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print(s[i][:,i].any()|s[j][:,j].any()and-1or m.max()+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
l=[list(input()) for _ in range(n)]
es = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if l[i][j]=="1":
            es[i].append(j)
colors = [0 for _ in range(n)]

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_nibu():
    return dfs(0,1)

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



d = [[float("inf") for i in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        if l[i][j]=="1":
            d[i][j]=1

for i in range(n):
    d[i][i] = 0

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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

ans=0
dd=warshall_floyd(d)
for i in range(n):
    ans=max(dd[i])

print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
l=[list(input()) for _ in range(n)]
es = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if l[i][j]=="1":
            es[i].append(j)
colors = [0 for _ in range(n)]

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_nibu():
    return dfs(0,1)

if is_nibu():
    print(1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import bisect

sys.setrecursionlimit(10 ** 6)

def main():
    def dfs1(u, ou=-1):
        res = [-1]
        for ku in range(n):
            if dead[ku]: continue
            if not to[u][ku]: continue
            if ku == ou: continue
            if vis[ku]: return [ku, u]
            vis[ku] = True
            cur = dfs1(ku, u)
            vis[ku] = False
            if cur[0] != -1:
                if cur[0] == cur[-1]:
                    return cur
                else:
                    return cur + [u]
        return res

    def rest(cur):
        if 0 in cur:
            i = bisect.bisect_left(cur, 0)
            cur[i], cur[i % 2] = cur[i % 2], cur[i]
        for i, u in enumerate(cur[:2]):
            for j in range(i + 2, len(cur), 2):
                v = cur[j]
                dead[v] = True
                for k in range(n):
                    to[u][k] |= to[v][k]
                    to[k][u] |= to[k][v]

    def dfs2(u):
        res = 1
        for ku in range(n):
            if not to[u][ku]: continue
            if vis[ku] or dead[ku]: continue
            vis[ku] = True
            res = max(res, dfs2(ku) + 1)
            vis[ku] = False
        return res

    n = int(input())
    to = [[c == "1" for c in input()] for _ in range(n)]
    dead = [False] * n
    #print(to)
    while 1:
        vis = [False] * n
        vis[0] = True
        cur = dfs1(0)
        #print(cur)
        if cur[0] == -1: break
        if len(cur) % 2 == 0:
            print(-1)
            exit()
        else:
            rest(cur[:-1])
            #print(to)
            #print(dead)
    ans = 0
    for u in range(n):
        if dead[u]: continue
        vis = [False] * n
        vis[u] = True
        ans = max(ans, dfs2(u))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:

import numpy as np

###################################
def arrmax(list):
    array = np.array(list)
#    print(np.argmax(array, axis=1)) ##座標
#    print(np.amax(array,axis=None)) ##値
    return np.amax(array,axis=None)
#################################
##ワーシャルフロイド法
#################################
def warshall_floyd(d,n):
    #d[i][j]: iからjへの最短距離
    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())
S = [[0 for j in range(N)] for i in range(N)]
d = [[float("inf") for i in range(N)] for i in range(N)]
g = [[] for i in range(N)] #g[i]:点iに隣接している点のリスト
for i in range(N):
    S[i] = str(input())
    for j in range(N):
        if S[i][j]=="1":
            d[i][j]=1
            d[j][i]=1
            g[i].append(j)
            g[j].append(i)


for i in range(N):
    d[i][i] = 0 #自身のところに行くコストは０


print(arrmax(warshall_floyd(d,N))+1) ##直径出力+1

Submission status: Wrong Answer

Solution code:
N = int(input())
G = [[int(x) for x in input()] for k in range(N)]
es = [[] for k in range(N)]

for k in range(N):
    for l in range(N):
        if G[k][l] == 1:
            es[k].append(l)

#
# 二部グラフ判定by prdさん
#

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

if is_bipartite() == False:
    print(-1)
    exit(0)

# ワーシャルフロイドで距離を求める
D = [[1000 for k in range(N)] for l in range(N)]
for k in range(N):
    for l in range(N):
        if k == l:
            D[k][l] = 0
        elif G[k][l] == 1:
            D[k][l] = 1

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[p][q] = min(D[p][q],D[p][r]+D[r][q])
ans = 0
for k in range(N):
    for l in range(N):
        ans = max(ans, D[k][l]+1)

print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        # S = [list(map(int, list(input().rstrip())))for _ in range(N)]

        edge = defaultdict(set)
        for i in range(N):
            for j, flag in enumerate(list(input().rstrip())):
                if int(flag):
                    edge[i + 1].add(j + 1)

        ans = -1
        for i in range(N):
            q = queue.Queue()
            flood_fill = set()
            q.put((i + 1, 0))
            flood_fill.add(i + 1)
            is_bipartite_graph = True
            distance = 0
            while not q.empty():
                node = q.get()

                next_nodes = edge[node[0]]

                # 2部グラフ判定
                for next_node in next_nodes:
                    if not edge[next_node].isdisjoint(next_nodes):
                        is_bipartite_graph = False
                        break
                    elif next_node not in flood_fill:
                        q.put((next_node, node[1] + 1))
                        flood_fill.add(next_node)
                        distance = max(distance, node[1] + 1)
                if not is_bipartite_graph:
                    break

            if is_bipartite_graph:
                ans = max(ans, distance + 1)

        print(ans)


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

Submission status: Wrong Answer

Solution code:
import queue
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        # S = [list(map(int, list(input().rstrip())))for _ in range(N)]

        edge = defaultdict(set)
        for i in range(N):
            for j, flag in enumerate(list(input().rstrip())):
                if int(flag):
                    edge[i + 1].add(j + 1)

        ans = -1
        for i in range(N):
            q = queue.Queue()
            flood_fill = set()
            q.put((i + 1, 0))
            is_bipartite_graph = True
            distance = 0
            while not q.empty():
                node = q.get()
                flood_fill.add(node[0])
                next_nodes = edge[node[0]]

                # 2部グラフ判定
                for next_node in next_nodes:
                    if not edge[next_node].isdisjoint(next_nodes):
                        is_bipartite_graph = False
                        break
                    elif next_node not in flood_fill:
                        q.put((next_node, node[1] + 1))
                        distance = max(distance, node[1] + 1)
                if not is_bipartite_graph:
                    break

            if is_bipartite_graph:
                ans = max(ans, distance + 1)

        print(ans)


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#二部グラフ判定
L = [0 for i in range(N)]
L[0] = 1
q = [0]
res = 0

while len(q) > 0:
    idx = q.pop(-1)
    c = L[idx]*(-1)
    for i in range(N):
        if S[idx][i] == "1":
            if L[i] == 0:
                L[i] = c
                q.append(i)
            elif L[i] == c*(-1):
                res = 1
                q.clear()
                break
            

if res == 1:
    print(-1)
else:
    print(1)