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
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(list(map(int, input()[:-1])))

INF = float('inf')

def is_bipartite_graph():
    team = [0] * N
    valid = True
    q = deque()
    q.append(0)
    team[0] = 1
    while valid and len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if not team[v]:
                    team[v] = team[u]%2 + 1
                    q.append(v)
                else:
                    if (team[v] - team[u])%2 == 0:
                        valid = False
                        break
    return valid


def get_distances(s):
    Q = deque()
    Q.append(s)
    D = [INF] * N
    D[s] = 0
    while len(Q):
        u = Q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if D[v] > D[u] + 1:
                    D[v] = D[u] + 1
                    Q.append(v)
    return D


def get_diameter():
    d = get_distances(0)
    dmax = max(d)
    dindex = d.index(dmax)
    d = get_distances(dindex)
    return max(d)


if is_bipartite_graph():
    print(get_diameter()+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    que = deque([[0, 0]])
    f = 0
    while que:
        v, c = que.popleft()
        col[v] = c
        for ne in E[v]:
            if col[ne] == c:
                f = 1
                break
            if col[ne] < 0:
                que.append([ne, 1-c])

        if f:
            break
    return 1-f

def farthest(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in X[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    ma, mai = -1, -1
    for i in range(n):
        if D[i] > ma:
            mai = i
            ma = D[i]
    return (mai, ma)

if bipartite(N, X):
    print(farthest(N, X, farthest(N, X, 0)[0])[1]+1)
else:
    print(-1)

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:
        dist = dict()
        for i in range(N):
            dist[i] = dict()
            for j in range(N):
                if j in edge[i]: dist[i][j] = 1
                elif i == j: dist[i][j] = 0
                else: dist[i][j] = 1000000000
 
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
        ans = 0
        for i in range(N):
            for j in range(N):
                if dist[i][j] < 1000000000: ans = max(ans, dist[i][j])
        print(ans + 1)
 
    return 0
 
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import queue
import numpy as np
n = int(input())
class Node:
    def __init__(self):
        self.nextNode = []
        self.checkNgo = -1
        self.group = -1
        
Nodes = [Node() for i in range(n)]
for i in range(n):
    s = input()
    for j in range(len(s)):
        if s[j] == '1':
            Nodes[i].nextNode.append(j)
            
def check(node,ngo):
    if node.checkNgo == -1:
        node.checkNgo = ngo
    elif node.checkNgo != ngo:
        return False
    elif node.checkNgo == ngo:
        return True
    for i in node.nextNode:
        if not check(Nodes[i],(ngo+1)%2):
            return False
    return True
    
def ngoCheck():
    stack = [Nodes[0]]
    Nodes[0].checkNgo = 0
    while stack:
        node = stack.pop()
        for i in node.nextNode:
            if Nodes[i].checkNgo != -1 and Nodes[i].checkNgo == node.checkNgo:
                return False
            if Nodes[i].checkNgo == -1:
                Nodes[i].checkNgo = (node.checkNgo+1)%2
                stack.append(Nodes[i])
    return True
    
if not ngoCheck():
    print(-1)
    exit(0)
    
def solv():
    d = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if j in Nodes[i].nextNode:
                d[i][j] = 1
            else:
                d[i][j] = np.inf
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    return d
    
def saidai(d):
    maxi = 0
    for i in range(n):
        for j in range(n):
            maxi = max(maxi,d[i][j])
    return maxi
    
d = solv()
print(saidai(d)+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
E = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            E[i].append(j)

col = [-1] * N
que = deque([[0, 0]])
f = 0
while que:
    v, c = que.popleft()
    col[v] = c
    for ne in E[v]:
        if col[ne] == c:
            f = 1
            break
        if col[ne] < 0:
            que.append([ne, 1-c])
    
    if f:
        break

def farthest(i):
    L = [-1] * N
    L[i] = 0
    d = 0
    post = [i]
    while len(post) > 0:
        d += 1
        pre = post
        post = []
        for j in pre:
            for k in E[j]:
                if L[k] < 0:
                    L[k] = d
                    post.append(k)
        
    return (pre[0], d-1)

if f == 0:
    print(farthest(farthest(0)[0])[1]+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections
import sys
sys.setrecursionlimit(10**8)

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)

colors=[0]*n

def dfs(v,color):
  colors[v]=color
  for u in g[v]:
    if colors[u]==color:
      return False
    if colors[u]==0 and not dfs(u,-color):
      return False
  return True

def is_bipartite():
  dfs(0,1)
  
if is_bipartite()==False:
  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 sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(input())

INF = float('inf')

def is_bipartite_graph():
    team = [0] * N
    valid = True
    q = deque()
    q.append(0)
    team[0] = 1
    while valid and len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e == '1':
                if not team[v]:
                    team[v] = team[u]%2 + 1
                    q.append(v)
                else:
                    if (team[v] - team[u])%2 == 0:
                        valid = False
                        break
    return valid


def get_distances(s):
    D = [INF] * N
    D[s] = 0
    for i in range(N):
        i = (i+s) % N
        for j in range(N):
            if V[i][j] == '1':
                if D[j] > D[i] + 1:
                    D[j] = D[i] + 1
    return D


def get_diameter():
    d = get_distances(0)
    dmax = max(d)
    dindex = d.index(dmax)
    d = get_distances(dindex)
    return max(d)


if is_bipartite_graph():
    print(get_diameter()+1)
else:
    print(-1)

Submission status: Wrong Answer

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

n = int(input())
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)
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])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((i, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] <= -1:
        dist[v] = d
    elif dist[v] != d:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))
            dist[item] = -2

if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print(ans + 1)
else:
    print(-1)

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:
        dist = dict()
        for i in range(N):
            dist[i] = dict()
            for j in range(N):
                if j in edge[i]: dist[i][j] = 1
                elif i == j: dist[i][i] = 0
                else: dist[i][j] = 1000000000

        for k in range(N):
            for i in range(N):
                for j in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        ans = 0
        for i in range(N):
            for j in range(N):
                if dist[i][j] < 1000000000: ans = max(ans, dist[i][j])
        print(ans + 1)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

n = int(input())
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)
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])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((i, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == -1:
        dist[v] = d
    elif dist[v] != d:
        print(dist[v], d)
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))

if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print(ans + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:

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

import sys
import queue
import random

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


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

        q.append((0, 0))
        while q:
            now_node, now_dist = q.popleft()
            if dist_to[now_node] == -1:
                dist_to[now_node] = now_dist
                order.append(now_node)
                for next_node in edge[now_node]:
                    if dist_to[next_node] == -1: q.append((next_node, now_dist + 1))

        dist_back = [-1] * N
        q.append((order[N-1], 1))
        while q:
            now_node, now_dist = q.popleft()
            if dist_back[now_node] == -1:
                dist_back[now_node] = now_dist
                for next_node in edge[now_node]:
                    if dist_back[next_node] == -1: q.append((next_node, now_dist + 1))
        print(max(dist_back))
        #print(dist_back)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import queue
import numpy as np
n = int(input())
class Node:
    def __init__(self):
        self.nextNode = []
        self.checkNgo = -1
        self.group = -1
        
Nodes = [Node() for i in range(n)]
for i in range(n):
    s = input()
    for j in range(len(s)):
        if s[j] == '1':
            Nodes[i].nextNode.append(j)
            
def check(node,ngo):
    if node.checkNgo == -1:
        node.checkNgo = ngo
    elif node.checkNgo != ngo:
        return False
    elif node.checkNgo == ngo:
        return True
    for i in node.nextNode:
        if not check(Nodes[i],(ngo+1)%2):
            return False
    return True
    
if not check(Nodes[0],0):
    print(-1)
    exit(0)
    
def solv():
    d = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if j in Nodes[i].nextNode:
                d[i][j] = 1
            else:
                d[i][j] = np.inf
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    return d
    
def saidai(d):
    maxi = 0
    for i in range(n):
        for j in range(n):
            maxi = max(maxi,d[i][j])
    return maxi
    
d = solv()
print(saidai(d)+1)

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 + 1)
        #print(dist_back)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    N = II()
    edge_list = {}
    # i, j は 0 origin で入れる
    for i in range(N):
        edge_list[i] = []
        ei = SI()
        for j, e in enumerate(ei):
            if e == '1':
                edge_list[i].append(j)

    # node 1 は k = N-1 に入れる
    # 左と右に伸ばすと考えると、0～2N-2まで考えると足りる
    startk = N-1
    maxk = 2*N - 1

    # 可能性があるなら1、ないなら-1、見てないなら0
    ass = [[0 for k in range(maxk)] for i in range(N)]

    from collections import deque
    q = deque()
    start_i = 0
    for k in range(maxk):
        ass[start_i][k] = -1
    ass[start_i][N-1] = 1
    for e in edge_list[start_i]:
        q.append((start_i, e))
    seen = set()
    seen.add(0)

    dprint(edge_list)
    dprint(ass)
    dprint(q, seen)
    cnt = 0

    while q:
        parent, n = q.popleft()

        # nのアサイン変更
        for k in range(maxk):
            is_parentnext = False
            if k == 0:
                is_parentnext = ass[parent][k+1] == 1
            elif k == maxk-1:
                is_parentnext = ass[parent][k-1] == 1
            else:
                is_parentnext = (ass[parent][k-1]==1) or (ass[parent][k+1]==1)

            if is_parentnext == False:
                # 親の隣以外は-1にする
                ass[n][k] = -1
            else:
                # となりの場合
                if ass[n][k] == -1:
                    # -1なら変更しない
                    pass
                else:
                    # そうでないなら、OK状態に変更
                    ass[n][k] = 1

        # nの隣接
        node_neib = edge_list[n]

        # nのneibを追加したことがなければキューに追加
        if n not in seen:
            for neib in node_neib:
                q.append((n, neib))

        # nをseenに追加
        seen.add(n)

        cnt += 1
        dprint(cnt, 'parent:', parent, 'n:', n, ass[n], seen)

    if debug:
        for i in range(N):
            print(ass[i])

    # all -1 の行があれば失敗
    k_list = []
    for i in range(N):
        if sum(ass[i]) == -1 * maxk:
            print(-1)
            return


    # ここまでで作ったassについて、左はじから順に選んで一番長くなるようにしたらいい
    # つながるように選べば成立することは保証されている

    mink_i, mink = 0, 0
    for k in range(maxk):
        for i in range(N):
            if ass[i][k] == 1:
                mink_i = i
                mink = k
                break

    # miniからスタートして、隣接を決定していく。+1していく決め方が必ず実現できる
    fixed_ass = [[-1] for i in range(N)]
    fixed_ass[mink_i] = mink

    qu = deque()
    qu.append((mink, mink_i))
    seen = set()
    maxk = 0
    while len(seen) < N:
        k, n = qu.popleft()
        seen.add(n)
        fixed_ass[n] = k+1

        for neib in edge_list[n]:
            if neib not in seen:
                qu.append((k+1, neib))

        maxk = k+1

    print(maxk - mink)
solve()

Submission status: Wrong Answer

Solution code:
import queue
n = int(input())
class Node:
    def __init__(self):
        self.nextNode = []
        self.checkNgo = -1
        self.group = -1
        
Nodes = [Node() for i in range(n)]
for i in range(n):
    s = input()
    for j in range(len(s)):
        if s[j] == '1':
            Nodes[i].nextNode.append(j)
            
def check(node,ngo):
    if node.checkNgo == -1:
        node.checkNgo = ngo
    elif node.checkNgo != ngo:
        return False
    elif node.checkNgo == ngo:
        return True
    for i in node.nextNode:
        if not check(Nodes[i],(ngo+1)%2):
            return False
    return True
    
if not check(Nodes[0],0):
    print(-1)
    exit(0)
    
def solv(nn):
    d = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if j in Nodes[i].nextNode:
                d[i][j] = 1
            else:
                d[i][j] = 1e7
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    return d
    
def saidai(d):
    maxi = 0
    for i in range(n):
        for j in range(n):
            maxi = max(maxi,d[i][j])
    return maxi
    
kai = 0
d = solv(i)
print(saidai(d)+1)

Submission status: Wrong Answer

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


def confirm(index):
    R = [ind for ind in range(N)]
    R.remove(index)
    res = [index]
    box = [index]
    while True:
        app = []
        for l in box:
            for k in range(N):
                if A[l][k] == 1:
                    if k not in R:
                        if k in box:
                            return False
                        continue
                    app.append(k)
                    R.remove(k)
        res.append(app)
        box = app

        if len(R) == 0:
            return len(res)


result = 0
for i in range(len(A)):
    if A[i].count(1) == 1:
        J = confirm(i)
        if not J:
            continue
        if result < J:
            result = J

if result == 0:
    print(-1)
else:

    print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import combinations

def bipartite(V, A):
    color = {v: None for v in V}
    part = []
    for v in V:
        if color[v] is not None: continue
        stack = [(v, 0)] # color v with 0
        parts = {0: [], 1: []}
        while stack:
            v, c = stack.pop()
            if color[v] is not None: # consistent
                continue
            color[v] = c
            parts[c].append(v)
            for u, a in enumerate(A[v]):
                if a == '1':
                    if color[u] is None: # not visited yet
                        stack.append((u, c^1)) # paint u with different color from v's one
                    elif color[u] != c: # consistent
                        continue
                    else: # inconsistent
                        return None
        part.append(parts)
    return part

N = int(input())
S = [input() for _ in range(N)]
if bipartite(list(range(N)), S) is None:
    print(-1)
else:
    dist = [-1] * N
    q = deque([(0, 0)])
    max_d = 0
    while q:
        v, d = q.popleft()
        if dist[v] != -1: continue
        dist[v] = d
        max_d = max(max_d, d)
        for u, s in enumerate(S[v]):
            if s == '1' and dist[u] == -1:
                q.append((u, d+1))
    x = dist.index(max_d)
    diameter = 0
    dist = [-1] * N
    q = deque([(x, -1, 0)])
    while q:
        v, p, d = q.popleft()
        if dist[v] != -1: continue
        dist[v] = d
        diameter = max(diameter, d)
        for u, s in enumerate(S[v]):
            if u == p: continue
            elif s == '1' and dist[u] == -1:
                q.append((u, v, d+1))
    print(diameter + 1)

Submission status: Wrong Answer

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

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

E = []
for i in range(N):
  for j in range(i,N):
    if S[i][j] == '1':
      E.append([i,j])
#print(E)

ans = -1
V = [N**2 for _ in range(N)]
def dfs(i):
  global ans
  #print(V)
  if i == len(E):
    ans = max(ans,max(V))
    return
  else:
    e = E[i]
    if V[e[0]] == N**2 and V[e[1]] == N**2:
      V[e[0]] = max(V)+1
      V[e[1]] = V[e[0]]+1
      dfs(i+1)
      V[e[0]] = N**2
      V[e[1]] = N**2
      V[e[1]] = max(V)+1
      V[e[0]] = V[e[1]]+1
      dfs(i+1)
      V[e[0]] = N**2
      V[e[1]] = N**2
      return
    elif V[e[0]] != N**2 and V[e[1]] == N**2:
      V[e[1]] = V[e[0]]+1
      dfs(i+1)
      V[e[1]] = V[e[0]]-1
      dfs(i+1)
      V[e[1]] = N**2
      return
    elif V[e[0]] == N**2 and V[e[1]] != N**2:
      V[e[0]] = V[e[1]]+1
      dfs(i+1)
      V[e[0]] = V[e[1]]-1
      dfs(i+1)
      V[e[0]] = N**2
      return
    else:
      if abs(V[e[0]] - V[e[1]]) != 1:
        return
      else:
        dfs(i+1)
      
dfs(0)
#print(V)
print(ans-(N**2) if ans > -1 else ans)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
s = [[int(c) for c in l.strip()] for l in sys.stdin]
dp = [ [False]*(i+1) for i in range(n) ]
count = -1
if s[0][1] == 1:
  dp[1][0], dp[1][1] = True, True
  count = 2
for i in range(2, n):
  for j in range(i):
    if dp[i-1][j] and s[i][j] == 1:
      dp[i][j] = True
      if count < i+1:
        count = i+1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque




def main():
    node_num = int(input())
    data = [list(map(int, list(input()))) for i in range(node_num)]

    graph_data = defaultdict(set)
    for i in range(node_num):
        for j in range(node_num):
            if data[i][j]:
                graph_data[i].add(j)

    ans = 0

    for i in range(node_num):
        flg_list = [0 for i in range(node_num)]

        now_set = set()
        pre_set = set()
        now_set.add(i)
        kari = 0

        while 1:
            if len(now_set) == 0:
                break
                # for j in range(node_num):
                #     if flg_list[j] == 0:
                #         now_set.add(j)
                #         pre_set = set()
                #         # print(now_set)
                #         break
            kari += 1
            next_set = set()

            for ele in now_set:
                next_set |= graph_data[ele]

            if len(now_set & next_set):
                break

            if pre_set & next_set != pre_set:
                break
            next_set -= pre_set


            fin_flg = 0
            for ele in now_set:
                if flg_list[ele] == 1:
                    fin_flg = 1
                    break
                flg_list[ele] = 1

            if fin_flg:
                break


            if min(flg_list):
                ans = max(ans, kari)
                break

            pre_set = now_set
            now_set = next_set


    if ans > 0:
        print(ans)
    else:
        print(-1)









if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

answer = 1
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()
for i in range(N):
    answer += max(0, min(1, sum(graph[i][i+1:])))
    
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(input())

INF = float('inf')
def get_farest_bf(s):
    D = [INF] * N
    D[s] = 0
    for i in range(N):
        i = (i+s) % N
        for j in range(N):
            if V[i][j] == '1':
                if D[j] > D[i] + 1:
                    D[j] = D[i] + 1
                if D[i] > D[j] + 1:
                    D[i] = D[j] + 1

    invalid = False
    for i in range(N):
        for j in range(i+1, N):
            if D[i] == D[j] and V[i][j] == '1':
                invalid = True
                break
        if invalid:
            break
    if invalid:
        return -1, None
    distmax = max(D)
    t = D.index(distmax)
    return distmax, t

dist, f = get_farest_bf(0)
if dist < 0:
    print(-1)
else:

    diameter, _ = get_farest_bf(f)
    print(diameter+1)