#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
int dis[501][501][2],dis2[501],parent[501][501][2];
int a[501][501],flag;
vector <int> v[501];
queue <int> qu1,qu2;
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 bfs2(int bg){
for(int i=0;i<n;i++) dis2[i]=1e9;
queue <int> qu;
qu.push(bg);
dis2[bg]=0;
while(!qu.empty()){
int i=qu.front();
qu.pop();
for(int j=0;j<n;j++){
if(a[i][j]==0) continue;
if(dis2[j]==1e9){
dis2[j]=dis2[i]+1;
qu.push(j);
}
}
}
return;
}
int start(int N, bool A[MAX_N][MAX_N])
{
n=N;
pos=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(A[i][j]==1) v[i].push_back(j);
a[i][j]=A[i][j];
}
if(v[i].size()==n-1) pos=i;
}
int mx=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i][j]==1){
a[i][j]=a[j][i]=0;
bfs2(i);
if(dis2[j]!=1e9) mx=max(dis2[j]+1,mx);
a[i][j]=a[j][i]=1;
}
}
}
for(int i=0;i<n;i++) bfs(i);
if(mx>4) return -1;
return 0;
}
int nextMove(int R)
{
if(a[R][pos]==1) return R;
if(dis[R][pos][1]==1e9||R==pos) return pos;
if(qu1.size()==0&&qu2.size()==0){
int bg=pos,u=1;
while(bg!=R){
bg=parent[R][bg][u];
if(bg!=R) qu1.push(bg);
u^=1;
}
}
qu2.push(R);
if(qu1.size()!=0){
pos=qu1.front();
qu1.pop();
return pos;
}
else{
pos=qu2.front();
qu2.pop();
return pos;
}
}
