#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
int dis[501][501][2],parent[501][501][2];
int arr[501][501],flag,disc[501];
vector <int> v[501];
int n,pos;
void bfs(int bg){
for(int i=0;i<n;i++) dis[bg][i][0]=dis[bg][i][1]=1e9;
queue <array<int,2>> qu;
qu.push({bg,0});
dis[bg][bg][0]=0;
while(!qu.empty()){
auto [i,u]=qu.front();
qu.pop();
for(int j:v[i]){
if(dis[bg][j][u^1]==1e9){
parent[bg][j][u^1]=i;
dis[bg][j][u^1]=dis[bg][i][u]+1;
qu.push({j,u^1});
}
}
}
}
void dfs(int i,int cnt){
disc[i]=cnt;
for(int j:v[i]){
if(disc[i]-disc[j]+1>4&&disc[j]!=0) flag=-1;
if(disc[j]==0) dfs(j,cnt+1);
}
return;
}
int start(int N, bool A[MAX_N][MAX_N])
{
n=N;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) if(A[i][j]==1) v[i].push_back(j);
}
for(int i=0;i<n;i++){
bfs(i);
if(disc[i]==0) dfs(i,1);
}
if(flag==-1) return -1;
pos=1;
return 1;
}
int nextMove(int R)
{
if(dis[R][pos][0]==1e9) return pos;
pos=parent[R][pos][0];
return pos;
}
