#include "coprobber.h"
#include <queue>
#include <array>
#include <iostream>
using namespace std;
int Win[2][MAX_N][MAX_N], deg[2][MAX_N][MAX_N], seen[2][MAX_N][MAX_N], Nxt[MAX_N][MAX_N];
int cop, s;
int start(int n, bool A[MAX_N][MAX_N]){
s = n;
for (int t : {0, 1}){
for (int c=0;c<n;c++){
for (int r=0;r<n;r++){
Win[t][c][r] = t;
for (int k=0, x = 0;k<n;k++){
if (t == 1 and A[r][k])
x = 1;
else if (t == 0 and (A[c][k] or k == c))
x = 1;
deg[t][c][r] += x, x = 0;
}
}
}
}
queue<array<int, 3>> Q;
for (int t : {0, 1}){
for (int i=0;i<n;i++){
Q.push({t, i, i});
Win[t][i][i] = seen[t][i][i] = 1;
}
}
while (Q.size() > 0){
auto [t, c, r] = Q.front(); Q.pop();
if (t == 0){
for (int R = 0; R < n; R++){
if (!A[R][r])
continue;
deg[1][c][R]--;
Win[1][c][R] &= Win[0][c][r];
if (!seen[1][c][R] and (deg[1][c][R] == 0 or Win[1][c][R] == 0))
seen[1][c][R] = 1, Q.push({1, c, R});
}
}
else{
for (int C=0;C<n;C++){
if (C != c and !A[C][c])
continue;
deg[0][C][r]--;
Win[0][C][r] |= Win[1][c][r];
if (!seen[0][C][r] and (deg[0][C][r] == 0 or Win[0][C][r] == 1))
seen[0][C][r] = 1, Q.push({0, C, r}), Nxt[C][r] = c;
}
}
}
for (int c=0;c<n;c++){
int t = 1;
for (int r=0;r<n;r++)
t &= Win[0][c][r];
if (t)
return cop = c;
}
return -1;
}
int nextMove(int R){
return cop = Nxt[cop][R];
}
