#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 7;
int n;
vector<int> g[N];
int wn[N][N][2];
enum {COP, ROB};
/**
win[cop][rob][move] = if the cop can win
if cop == rob:
win[cop][rob][move] = 1
if move == C:
if at least one from {win[cop'][rob][R] == 1}:
win[cop][rob][C] = 1
if move == R:
if all moves {win[cop][rob'][C] == 1}:
win[cop][rob][R] = 1
**/
int cnt_bad;
int cnt_good;
void add(int x) {
assert(x == 0 || x == 1);
if (x == 0) cnt_bad++;
if (x == 1) cnt_good++;
}
int C;
int where[N][N];
int start(int nn, bool AE[MAX_N][MAX_N]) {
n = nn;
for (int i = 0; i < n; i++) {
assert(g[i].empty());
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (AE[i][j]) {
assert(AE[j][i]);
assert(i != j);
g[i].push_back(j);
}
}
assert(AE[i][i] == 0);
}
if (0) {
cout << "graph = \n";
for (int i = 0; i < n; i++) {
for (auto &j : g[i]) {
cout << "\t\t\t\t\t" << i << " --> " << j << "\n";
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
wn[i][j][COP] = wn[i][j][ROB] = 0; /// unsure
}
}
for (int i = 0; i < n; i++) {
wn[i][i][COP] = wn[i][i][ROB] = 1;
}
while (1) {
bool change = 0;
int sum = 0;
for (int cop = 0; cop < n; cop++) {
for (int rob = 0; rob < n; rob++) {
if (wn[cop][rob][COP] == 0) {
/// if it is unsure
cnt_good = cnt_bad = 0;
add(wn[cop][rob][ROB]);
for (auto &vecin : g[cop]) {
add(wn[vecin][rob][ROB]);
}
if (cnt_good >= 1) {
change = 1;
assert(wn[cop][rob][COP] == 0);
wn[cop][rob][COP] = 1;
int cine = -1;
if (wn[cop][rob][ROB] == 1) {
cine = cop;
}
for (auto &vecin : g[cop]) {
if (wn[vecin][rob][ROB] == 1) {
cine = vecin;
}
}
assert(cine != -1);
where[cop][rob] = cine;
}
} else {
sum++;
}
if (wn[cop][rob][ROB] == 0) {
/// if it is unsure
cnt_good = cnt_bad = 0;
for (auto &vecin : g[rob]) {
add(wn[cop][vecin][COP]);
}
if (cnt_bad == 0) {
change = 1;
wn[cop][rob][ROB] = 1;
}
} else {
sum++;
}
}
}
///cout << "sum = " << sum << ", " << change << "\n";
if (!change) {
break;
}
}
for (int cop = 0; cop < n; cop++) {
bool good = 1;
for (int rob = 0; rob < n; rob++) {
assert(wn[cop][rob][COP] == 0 || wn[cop][rob][COP] == 1);
assert(wn[cop][rob][ROB] == 0 || wn[cop][rob][ROB] == 1);
good &= (wn[cop][rob][COP] == 1);
}
if (good) {
return cop;
}
}
return -1;
}
int nextMove(int R) {
assert(wn[C][R][COP] == 1);
int new_cop = where[C][R];
assert(new_cop != -1);
C = new_cop;
return C;
}
