#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
struct State {
short cop, robber;
bool turn; // 1 = cop
State(short c = -1, short r = -1, bool t = -1) : cop(c), robber(r), turn(t) {}
operator short() const { return 2 * (MAX_N * cop + robber) + turn; }
};
vector<State> graph[3 * MAX_N * MAX_N];
bool win[3 * MAX_N * MAX_N];
short deg_in[3 * MAX_N * MAX_N];
State here, nxt[3 * MAX_N * MAX_N], states[3 * MAX_N * MAX_N];
void add_edge(short a, short b, short c, short d, bool cop) {
graph[State(c, d, !cop)].push_back(State(a, b, cop));
deg_in[State(a, b, cop)]++;
}
int start(int N, bool A[MAX_N][MAX_N]) {
for (short i = 0; i < N; i++) for (short j = 0; j < N; j++) {
if (i == j) continue;
add_edge(i, j, i, j, 1);
for (short k = 0; k < N; k++) if (A[i][k]) {
add_edge(i, j, k, j, 1);
add_edge(j, i, j, k, 0);
}
}
queue<State> q; // Reverse BFS
for (short i = 0; i < N; i++) for (short j = 0; j < N; j++) for (short k = 0; k < 2; k++) {
if (!deg_in[State(i, j, k)]) {
q.push(State(i, j, k));
win[State(i, j, k)] = true;
}
}
while (q.size()) {
State curr = q.front();
q.pop();
for (State i : graph[curr]) {
deg_in[i]--;
if (!win[i] && (i.turn || !deg_in[i])) {
nxt[i] = curr;
win[i] = true;
q.push(i);
}
}
}
for (short i = 0; i < N; i++) {
bool guarantee = true;
for (short j = 0; j < N; j++) guarantee &= win[State(i, j, 1)];
if (guarantee) {
here = {i, i, 1};
return (int)i;
}
}
return -1;
}
int nextMove(int R) {
here.robber = R;
here.turn = 1;
here = nxt[here];
return (int)here.cop;
}
