#include "coprobber.h"
#include "bits/stdc++.h"
using namespace std;
struct node
{
int move, police, thif;
node () {}
node (int move, int police, int thif) : move(move), police(police), thif(thif) {}
};
vector <node> g[2][505][505];
vector <node> t[2][505][505];
bool win[2][505][505];
int deg[2][505][505];
int cur;
node nxt[2][505][505];
int start(int N, bool A[MAX_N][MAX_N])
{
for(int mv = 0; mv <= 1; mv++) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(mv == 0) {
g[mv][i][j].push_back(node(mv ^ 1, i, j));
t[mv ^ 1][i][j].push_back(node(mv, i, j));
// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << i << "-" << j << endl;
}
for(int k = 0; k < N; k++) {
if(mv == 0 && A[i][k]) {
g[mv][i][j].push_back(node(mv ^ 1, k, j));
t[mv ^ 1][k][j].push_back(node(mv, i, j));
// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << k << "-" << j << endl;
} else if (mv == 1 && A[j][k]) {
g[mv][i][j].push_back(node(mv ^ 1, i, k));
t[mv ^ 1][i][k].push_back(node(mv, i, j));
// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << i << "-" << k << endl;
}
}
}
}
}
for(int mv = 0; mv <= 1; mv++) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
deg[mv][i][j] = g[mv][i][j].size();
}
}
}
queue <node> Q;
memset(win, 0, sizeof win);
for(int mv = 0; mv <= 1; mv++) {
for(int i = 0; i < N; i++) {
Q.push(node(mv, i, i));
win[mv][i][i] = 1;
}
}
while(!Q.empty()) {
node n = Q.front();
Q.pop();
for(auto i : t[n.move][n.police][n.thif]) {
if(win[i.move][i.police][i.thif]) continue;
deg[i.move][i.police][i.thif]--;
if(deg[i.move][i.police][i.thif] == 0) {
win[i.move][i.police][i.thif] = 1;
nxt[i.move][i.police][i.thif] = n;
Q.push(i);
// cerr << n.move << " " << n.police << " " << n.thif << " updates " << i.move << " " << i.police << " " << i.thif << endl;
}
else if(i.move == 0) {
win[i.move][i.police][i.thif] = 1;
nxt[i.move][i.police][i.thif] = n;
Q.push(i);
// cerr << n.move << " " << n.police << " " << n.thif << " updates " << i.move << " " << i.police << " " << i.thif << endl;
}
}
}
// cout << nxt[0][0][2].move << " " << nxt[0][0][2].police << " " << nxt[0][0][2].thif << endl;
for(int i = 0; i < N; i++) {
bool sure = true;
for(int j = 0; j < N; j++) {
if(win[0][i][j] == 0) {
sure = false;
}
}
if(sure) {
cur = i;
return i;
}
}
return -1;
}
int nextMove(int R)
{
// cout << "police at: " << cur << " " << " robber at: " << R << endl;
cur = nxt[0][cur][R].police;
return cur;
}
