#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
#define pii pair <int , int>
#define F first
#define S second
#define num(i, j) i * n + j
int deg[MAX_N], Win[MAX_N][MAX_N][2], Cnt[MAX_N][MAX_N], Par[MAX_N][MAX_N], curPos;
int start(int n, bool A[MAX_N][MAX_N]) {
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (A[i][j]) deg[i]++;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) Cnt[i][j] = deg[j];
queue <pii> q;
for (int i = 0; i < n; i++) for (int t = 0; t < 2; t++) q.push({num(i, i), t}), Win[i][i][t] = 1, Par[i][i] = i;
while (!q.empty()) {
pii p = q.front(); q.pop();
int cop = p.F / n, rob = p.F % n;
if (p.S == 0) {
// Robber turn
for (int u = 0; u < n; u++)
if ((u == cop || A[u][cop]) && !Win[u][rob][1])
Win[u][rob][1] = 1, Par[u][rob] = cop, q.push({num(u, rob), 1});
} else {
// Cop turn
for (int u = 0; u < n; u++) if (A[u][rob]) {
Cnt[cop][u]--;
if (Cnt[cop][u] == 0 && !Win[cop][u][0]) Win[cop][u][0] = 1, q.push({num(cop, u), 0});
}
}
}
for (int i = 0; i < n; i++) {
bool Can = 1;
for (int j = 0; j < n; j++) Can &= Win[i][j][1];
if (Can) return curPos = i;
}
return -1;
}
int nextMove(int robber) {
return curPos = Par[curPos][robber];
}
