#include "coprobber.h"
#include<queue>
#include<tuple>
using namespace std;
typedef tuple<int, int, int> tiii;
const int INF=MAX_N*MAX_N;
bool adj[MAX_N][MAX_N];
bool chk[MAX_N][MAX_N];
int dp[MAX_N][MAX_N][2], deg[MAX_N][MAX_N];
queue<tiii> q;
int p;
int start(int N, bool A[MAX_N][MAX_N]){
for(int i=0; i<N; i++) for(int j=0; j<N; j++){
adj[i][j]=A[i][j];
dp[i][j][0]=dp[i][j][1]=-1;
if(A[i][j]) deg[0][i]++;
}
for(int i=0; i<N; i++) for(int j=1; j<N; j++) deg[j][i]=deg[0][i];
for(int i=0; i<N; i++){
q.push(make_tuple(i, i, 0));
q.push(make_tuple(i, i, 1));
dp[i][i][0]=dp[i][i][1]=0;
}
while(!q.empty()){
int c, r, t;
tie(c, r, t)=q.front();
q.pop();
//printf("[%d %d %d]\n", c, r, t);
if(t==0){
for(int i=0; i<N; i++) if(A[i][r]&&dp[c][i][1]==-1){
deg[c][i]--;
if(deg[c][i]==0){
//printf("(%d %d %d)\n", c, i, 1);
q.push(make_tuple(c, i, 1));
dp[c][i][1]=dp[c][r][t]+1;
}
}
}
else{
for(int i=0; i<N; i++) if((c==i||A[c][i])&&dp[i][r][0]==-1){
//printf("(%d %d %d)\n", i, r, 0);
q.push(make_tuple(i, r, 0));
dp[i][r][0]=dp[c][r][t]+1;
}
}
}
/*
for(int k=0; k<2; k++){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) printf("%d ", dp[i][j][0]);
printf("\n");
}
printf("****\n");
}
*/
for(int i=0; i<N; i++){
bool b=true;
for(int j=0; j<N; j++) if(dp[i][j][0]==-1) b=false;
if(b) return p=i;
}
return -1;
}
int nextMove(int R){
for(int i=0;; i++) if((adj[p][i]||i==p)&&dp[i][R][1]==dp[p][R][0]-1) return p=i;
//return -1;
}
