#include "coprobber.h"
#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
int state[MAX_N][MAX_N][2];
int pos[MAX_N][MAX_N];
vector<int> adj[MAX_N];
int f(int a, int b, int c) {
if (state[a][b][c] != -1) return state[a][b][c];
if (a == b)
return state[a][b][c] = (c == 0 ? 1 : 0);
state[a][b][c] = 2;
int w = 0;
if (c == 0) { // cop
int v = f(a, b, !c);
if (v == 0) {
w = 1;
pos[a][b] = a;
}
for (int k : adj[a]) {
int v = f(k, b, !c);
if (v == 0) {
w = 1;
pos[a][b] = k;
}
}
} else { // robber
for (int k : adj[b]) {
int v = f(a, k, !c);
if (v == 0 || v == 2)
w = 1;
}
}
return state[a][b][c] = w;
}
int P;
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])
adj[i].push_back(j);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < 2; k++)
state[i][j][k] = -1;
for (int i = 0; i < N; i++) {
int cnt = 0;
for (int j = 0; j < N; j++)
if (f(i, j, 0) == 1)
cnt++;
if (cnt == N)
return P = i;
}
return -1;
}
int nextMove(int R) {
return P = pos[P][R];
}
