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: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,(v).size())
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define bit(n)(1ll<<(n))
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
void _print(ostream&){}template<class T,class...U>void _print(ostream&s,const T&t,const U&...u){s<<t<<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(const T&...t){_print(cout,t...);}template<class...T>void dprint(const T&...t){_print(cerr,t...);}
#ifndef LOCAL
struct osd{template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;
#define dprint(...)
#define cerr cer_
#endif
template<class T>bool chmax(T&a,const T&b){bool x=a<b;x?a=b:b;return x;}template<class T>bool chmin(T&a,const T&b){bool x=a>b;x?a=b:b;return x;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>class iterable{static false_type c(string v);template<class U>static auto c(U v)->decltype(all(v),true_type());static false_type c(...);public:const static bool value=decltype(c(declval<T>()))::value;};
template<class T,typename=enable_if_t<iterable<T>::value>>ostream&operator<<(ostream&o,const T&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>set<T>&operator<<(set<T>&v,const T&t){v.insert(t);return v;}
template<class T>multiset<T>&operator<<(multiset<T>&v,const T&t){v.insert(t);return v;}

// 解説を読んだ.がんばってとけなかったのになんでレートが落ちたのか考えると悔しさのようなものを感じている
// いや天才解法じゃん?なんでRecommendationsでProabilityが58%なんですか,キレている
// 凡ミスで1ペナ生やしてキレている(575)

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    cout<<setprecision(10);
    int n;
    cin>>n;
    vector<set<int>> es(n);
    vvi g(n, vi(n,INF));
    REP(i,n){
        g[i][i]=0;
        string s;
        cin>>s;
        REP(j,n){
            if(s[j]=='1'){
                g[i][j]=1;
                es[i].insert(j);
            }
        }
    }
    REP(i,n)dprint(es[i]);
    vi c(n, -1);
    queue<int> q;
    q.push(0);
    c[0]=0;
    while(q.size()){
        const int x=q.front();
        q.pop();
        for(int a:es[x]){
            dprint(c);
            dprint(x,'-',a);
            if(c[a]!=-1){
                if(c[a]==c[x]){
                    cout<<-1<<endl;
                    return 0;
                }
                continue;
            }
            c[a]=1-c[x];
            q.push(a);
        }
    }
    int ma=0;
    REP(i,n)dprint(g[i]);
    REP(k,n){
        REP(i,n){
            REP(j,n){
                chmin(g[i][j], g[i][k]+g[k][j]);
            }
        }
    }
    REP(i,n){
        dprint(g[i]);
        REP(j,n)if(g[i][j]!=INF)chmax(ma, g[i][j]);
    }
    cout<<ma+1<<endl;
}

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,(v).size())
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define bit(n)(1ll<<(n))
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
void _print(ostream&){}template<class T,class...U>void _print(ostream&s,const T&t,const U&...u){s<<t<<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(const T&...t){_print(cout,t...);}template<class...T>void dprint(const T&...t){_print(cerr,t...);}
#ifndef LOCAL
struct osd{template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;
#define dprint(...)
#define cerr cer_
#endif
template<class T>bool chmax(T&a,const T&b){bool x=a<b;x?a=b:b;return x;}template<class T>bool chmin(T&a,const T&b){bool x=a>b;x?a=b:b;return x;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>class iterable{static false_type c(string v);template<class U>static auto c(U v)->decltype(all(v),true_type());static false_type c(...);public:const static bool value=decltype(c(declval<T>()))::value;};
template<class T,typename=enable_if_t<iterable<T>::value>>ostream&operator<<(ostream&o,const T&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>set<T>&operator<<(set<T>&v,const T&t){v.insert(t);return v;}
template<class T>multiset<T>&operator<<(multiset<T>&v,const T&t){v.insert(t);return v;}

// 解説を読んだ.がんばってとけなかったのになんでレートが落ちたのか考えると悔しさのようなものを感じている
// いや天才解法じゃん?なんでRecommendationsでProabilityが58%なんですか,キレている

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    cout<<setprecision(10);
    int n;
    cin>>n;
    vector<set<int>> es(n);
    vvi g(n, vi(n,INF));
    REP(i,n){
        string s;
        cin>>s;
        REP(j,n){
            g[i][j]=s[j]-'0';
            if(s[j]=='1'){
                es[i].insert(j);
            }
        }
    }
    REP(i,n)dprint(es[i]);
    vi c(n, -1);
    queue<int> q;
    q.push(0);
    c[0]=0;
    while(q.size()){
        dprint(c);
        const int x=q.front();
        q.pop();
        for(int a:es[x]){
            if(c[a]!=-1){
                if(c[a]==c[x]){
                    cout<<-1<<endl;
                    return 0;
                }
                continue;
            }
            c[a]=1-c[x];
            q.push(a);
        }
    }
    int ma=0;
    REP(k,n){
        REP(i,n){
            REP(j,n){
                chmin(g[i][j], g[i][k]+g[k][j]);
            }
        }
    }
    REP(i,n){
        dprint(g[i]);
        REP(j,n)if(g[i][j]!=INF)chmax(ma, g[i][j]);
    }
    cout<<ma+1<<endl;
}

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
N = int(input())
S = np.frombuffer(sys.stdin.buffer.read(),
                  dtype='S1').reshape(N, -1)[:, :N].astype(int)
G = csgraph_from_dense(S)
F = floyd_warshall(G).astype(int)
F2 = F % 2
I0 = np.where(F2[0] == 0)
I1 = np.where(F2[0] == 1)
if (S[I0][:, I0] == 0).all() and (S[I1][:, I1] == 0).all():
    print(F.max() + 1)
    exit()
print(-1)

Submission status: Runtime Error

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: Runtime Error

Solution code:
#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, dijkstra
# G = csgraph_from_dense(edge, null_value=10**9)
# f = floyd_warshall(G)
# d = dijkstra(G, indices=1)
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[(xs,ys,0),(xt,yt,0)]
data=[[-1]*(n+2) for i in range(n+2)]
for i in range(n):
    xyr.append(tuple(map(int,input().split())))
# print(xyr)

for i in range(n+1):
    for j in range(i+1,n+2):
        x0 = xyr[i][0]
        y0 = xyr[i][1]
        r0 = xyr[i][2]
        x1 = xyr[j][0]
        y1 = xyr[j][1]
        r1 = xyr[j][2]
        data[i][j]=max(((x0-x1)**2+(y0-y1)**2)**.5-r0-r1,0)

G = csgraph_from_dense(data, null_value=-1)
# for i in G:
#     print(i)
d = dijkstra(G, indices=0, directed=False)
print(d[1])

Submission status: Runtime Error

Solution code:
# AGC039B - Graph Partition
def is_bipartite() -> bool:
    stack = deque([(1, 1)])
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [-1] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 0
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if dist[u] == -1:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1)) + 1
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
def solve():
    n=int(input())
    data=[list(map(int,list(input()))) for i in range(n)]
    fordfs=[[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if data[i][j]==1:
                fordfs[i].append(j)

    def dfs():
        V=[-1]*n
        V[0]=0
        que=deque()
        que.append(0)
        while que:
            now=que.popleft()
            nowv=V[now]
            for ne in fordfs[now]:
                if nowv==V[ne]:
                    print(-1)
                    exit()
                elif V[ne]==-1:
                    V[ne]=(nowv+1)%2
                    que.append(ne)
    
    dfs()
    # print(data)
    G=csgraph_from_dense(data)
    d = floyd_warshall(G)
    d.tolist()
    M=0
    for i in d:
        M=max(M,max(i))
    M=int(M)
    print(M+1)
    return



def main():

    solve()
    return
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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:
    # Warshall-Floyd法で直径を求める
    d = [[10**4 for j in range(N)] for i in range(N)]
    # initialize
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                d[i][j] = 1
    
    # DP
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i != j:
                    d[i][j] = min(d[i][j], d[i][k]+d[k][j])

                
    ans = 0
    for i in range(N):
        for j in range(N):
            if d[i][j] < 10**4:
                ans = max(ans, d[i][j])
                
    print(ans+1)

Submission status: Runtime Error

Solution code:
N = int(input())
S = [None] * N

for i in range(0, N):
    S[i] = [int(s) for s in list(input())]

m = 0
n_partite = True

for n in range(0, N):  # try starting with every vertex
    levels = [None] * N
    levels[n] = 0

    for l in range(0, N): # max possible levels
        for i in range(0, N): # look at every vertex
            if levels[i] == l: # vertex i is at level l
                # scan column S[i]
                for j in range(0, N): # scan all vertices and look for adjacent vertex to i
                    if S[i][j] == 1: # vertex j is adjacent to i
                        if levels[j] == None:
                            levels[j] = l + 1
                        elif levels[j] == l - 1: continue
                        elif levels[j] == l + 1: continue
                        else:
                            n_partite = False
                            break
    m = max( max(levels), m)

if n_partite:
    print(m + 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
s = [input() for _ in range(n)]

# 二部グラフ判定
memo = [-1] * n
memo[0] = 0
q = deque((0, -1))
while q:
    v, p = q.popleft()
    for nv in range(n):
        if s[v][nv] == '1':
            if nv == p:
                continue
            if memo[nv] == -1:
                memo[nv] = (memo[v] + 1) % 2
                q.append((nv, v))
            else:
                if memo[nv] == memo[v]:
                    print(-1)
                    exit()

# ワーシャルフロイドでグラフの直径を求めてもよし
INF = float('inf')
dp = [[1 if c == '1' else INF for c in row] for row in s]

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

dist = 0
for i in range(n):
    d = 0
    for j in range(n):
        d = max(d, dp[i][j])
    dist = max(d, dist)

print(dist+1)

Submission status: Runtime Error

Solution code:
import collections
from scipy.sparse.csgraph import floyd_warshall
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():
  return 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
  anss=[]
  while len(q)!=0:
    tmp,depth=q.popleft()
    anss.append(depth)
    checked[tmp]=1
    for v in g[tmp]:
      if checked[v]==0:
        q.append((v,depth+1))
  ans=max(ans,max(anss))
print(ans)

Submission status: Runtime Error

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
                    dist[j][i] = 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: Runtime Error

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
                    dist[j][i] = 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: Runtime Error

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
                dist[j][i] = 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: Runtime Error

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] = dist[j][i] = 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: Runtime Error

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:
                stack.append(Nodes[i])
    return True
    
if not cngoCheck():
    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: Runtime Error

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.copy()
        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: Runtime Error

Solution code:
import copy
N = int(input())
MAP = [input() for _ in range(N)]

G = []
for zos in MAP:
    tmp = []
    for i, zo in enumerate(zos):
        if zo == '1':
            tmp.append(i)
    G.append(tmp)

# print(G)

pattern = {tuple(None for i in range(N))}
for i in range(N):
    ptn = copy.copy(pattern)
    pattern.clear()
    # print(i)
    for p in ptn:
        # print('p:',p)
        p = list(p)
        seiyaku = set(p[o] for o in G[i] if p[o] != None)
        # print('seiyaku:', seiyaku)
        if len(seiyaku) == 2 and max(seiyaku) - min(seiyaku) == 2:
            p[i] = min(seiyaku) + 1
            pattern.add(tuple(p))
        elif len(seiyaku) == 1:
            t = list(seiyaku)[0]
            p[i] = t + 1
            pattern.add(tuple(p))
            p[i] = t - 1
            pattern.add(tuple(p))
        elif len(seiyaku) == 0:
            margin = N - i + 1
            tmp = list(n for n in p if n)
            if tmp:
                minp = min(tmp)
                maxp = max(tmp)
                for j in range(minp - margin, maxp + margin + 1):
                    p[i] = j
                    pattern.add(tuple(p))
            else:
                p[i] = 0
                pattern.add(tuple(p))
                
    # print(pattern)

# pattern = set()
# for ptn in pattern:
#     minp = min(ptn)
#     tmp = tuple(p - minp for p in ptn)
#     ans.add(tmp)

# print(ans)

if len(pattern) == 0:
    print('-1')
else:
    if N == 2:
        print(len(pattern) // 2)
    else:
        print(len(pattern) // ((N - 2)*(N - 3)//2))

Submission status: Runtime Error

Solution code:
n=int(input())

zerowset = set()
dic = {}

for i in range(n):
    s = str(input())
    ssum = 0
    dic[i] = set()
    for j in range(n):
        if int(s[j])==1:
            ssum += 1 
            dic[i].add(j)
            
    if ssum == 1:
        zerowset.add(i)
        
def search(sta,gol,step,root):
    tmpset = dic[sta]
    if gol in tmpset:
        root.append()
        return step+1
    
    for tmpsta in tmpset:
        return search(tmpsta,gol,step+1)
        
#print(zerowset)
if len(zerowset) != 2:
    print(-1)
else:
    listz = list(zerowset)
    sta = listz[0]
    gol = listz[1]
    vlen =  search(sta,gol,0)+1
    print(vlen)

Submission status: Runtime Error

Solution code:
n=int(input())

zerowset = set()
dic = {}

for i in range(n):
    s = str(input())
    ssum = 0
    dic[i] = set()
    for j in range(n):
        if int(s[j])==1:
            ssum += 1 
            dic[i].add(j)
            
    if ssum == 1:
        zerowset.add(i)
        
def search(sta,gol,step,root):
    tmpset = dic[sta]
    if gol in tmpset:
        return step+1
    
    for tmpsta in tmpset:
        return search(tmpsta,gol,step+1)
        
print(zerowset)
if len(zerowset) != 2:
    print(-1)
else:
    listz = list(zerowset)
    sta = listz[0]
    gol = listz[1]
    vlen =  search(sta,gol,0)+1
    print(vlen)

Submission status: Runtime Error

Solution code:
import collections, itertools, sys
sys.setrecursionlimit(10**6)


class UnionFind():
    def __init__(self, size):
        self.dat = list(range(size))
        self.SIZE = [1] * size  # 0-indexed

    def find(self, x):
        dat = self.dat
        stack = [x]
        while True:
            y = stack[-1]
            if dat[y] != y:
                stack += [dat[y]]
            else:
                break
        for s in stack:
            dat[s] = y
        return y

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        dat = self.dat
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = dat[X] = Y
            else:
                m = dat[Y] = X
            SIZE[m] = SX + SY
            SIZE[X + Y - m] = 0

    def is_same(self, x, y):
        find = self.find
        return find(x) == find(y)

    def scan_uf(self):
        find = self.find
        length = len(self.dat)
        for i in range(length):
            find(i)

    def size(self, x):
        return self.SIZE[self.find(x)]


N = int(input())
S = [[int(_) for _ in input()] for _ in range(N)]
G = collections.defaultdict(set)
for i, j in itertools.product(range(N), repeat=2):
    if S[i][j]:
        G[i].add(j)
P = [-1] * N
P[0] = -2
D = [-10] * N
D[0] = 0
Q = collections.deque([0])
UF = UnionFind(N)
while Q:
    x = Q.popleft()
    Gx = list(G[x])
    for y in Gx:
        if P[x] == y:
            continue
        if D[y] == -10:
            D[y] = D[x] + 1
            P[y] = x
            Q += [y]
        else:
            G[x].remove(y)
            if D[x] > D[y]:
                x, y = y, x
            cy1 = [y]
            cy2 = [x]
            for _ in range(D[y] - D[x]):
                cy1 += [P[cy1[-1]]]
            while True:
                cy1 += [P[cy1[-1]]]
                cy2 += [P[cy2[-1]]]
                if cy1[-1] == cy2[-1]:
                    break
            cy = cy1[-2::-1] + cy2
            if len(cy) % 2:
                print(-1)
                exit()
            c1 = cy[0]
            c2 = cy[1]
            for ca, cb in zip(cy[::2], cy[1::2]):
                UF.unite(c1, ca)
                UF.unite(c2, cb)
UF.scan_uf()
print(len(set(UF.dat)))