#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];
int n,pos;
void bfs(int bg){
for(int i=0;i<n;i++) dis[bg][i][0]=dis[bg][i][1]=1e9;
priority_queue <array<int,3>> qu;
qu.push({0,bg,0});
dis[bg][bg][0]=0;
while(!qu.empty()){
auto [mydis,i,u]=qu.top();
mydis*=-1;
qu.pop();
if(dis[bg][i][u]<mydis) continue;
for(int j:v[i]){
if(dis[bg][j][u^1]>mydis+1){
parent[bg][j][u^1]=i;
dis[bg][j][u^1]=mydis+1;
qu.push({dis[bg][j][u^1]*-1,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][0]==1e9) return pos;
pos=parent[R][pos][0];
return pos;
}
