#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
static bool states[500005]; //police * 1000 + robber * 2 + (IF POLICE TURN)
static int degree[500005];
static int to[500005];
//static vector<int> rev[500005];
static queue<int> can;
inline int g(int police, int robber, int turn){
return police * 1000 + robber * 2 + turn;
}
int pos;
int start(int N, bool A[MAX_N][MAX_N])
{
int n = N;
for(int u = 0;u < n;u++){
for(int v = 0;v < n;v++){
int s = g(u,v,0);
//rev[s+1].push_back(s); //Wait
degree[s]++;
for(int i = 0;i < n;i++){
if(A[u][i] == 1){
//rev[g(i,v,1)].push_back(s);
degree[s]++;
}
if(A[v][i] == 1){
//rev[g(u,i,0)].push_back(s+1);
degree[s+1]++;
}
}
if(u == v){
states[s] = 1;
states[s+1] = 1;
}
}
}
for(int i = 0;i < 500005;i++){
if(states[i] == 1){
can.push(i);
degree[i] = 0;
}
}
int work[n];
fill(work,work+n,n);
while(!can.empty()){
int t = can.front();
//cout << t << "\n";
if(!(t&1)){
int u = t/1000;
work[u]--;
if(work[u] == 0){
pos = u;
return u;
}
}
can.pop();
int u = t / 1000;
int v = (t / 2) % 500;
int tu = t & 1;
for(int i = 0;i < N;i++){
int s;
if(tu == 1){
if((A[u][i] == 0 && i != u))continue;
s = g(i,v,0);
}
if(tu == 0){
if(A[v][i] == 0) continue;
s = g(u,i,1);
}
if(states[s] == 0){
degree[s]--;
if(!(s & 1)){
can.push(s);
states[s] = 1;
degree[s] = 0;
to[s] = t;
}
else if(degree[s] == 0){
can.push(s);
states[s] = 1;
}
}
}
}
return -1;
}
int nextMove(int R)
{
int cur = g(pos,R,0);
int t = to[cur];
t /= 1000;
//cout << t << " " << R << "\n";
pos = t;
return t;
}
