#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 deg[MAX_N][MAX_N][2];
int win[MAX_N][MAX_N][2];
int los[MAX_N][MAX_N][2];
int nxt[MAX_N][MAX_N];
int P;
int start(int N, bool A[MAX_N][MAX_N]) {
for (int i = 0; i < N; i++) {
int cnt = 0;
for (int j = 0; j < N; j++)
cnt += A[i][j];
for (int j = 0; j < N; j++) {
deg[i][j][0] = cnt;
deg[j][i][1] = cnt;
}
}
queue<tuple<int, int, int>> q;
for (int i = 0; i < N; i++) {
win[i][i][0] = true;
los[i][i][1] = true;
q.push({i, i, 0});
q.push({i, i, 1});
}
while (!q.empty()) {
auto [a, b, c] = q.front(); q.pop();
if (c == 0) {
for (int k = 0; k < N; k++)
if (A[b][k] && !win[a][k][!c] && !los[a][k][!c]) {
if (los[a][b][c]) {
win[a][k][!c] = true;
q.push({a, k, !c});
} else if (--deg[a][k][!c] == 0) {
los[a][k][!c] = true;
q.push({a, k, !c});
}
}
} else if (c == 1) {
for (int k = 0; k < N; k++)
if ((A[a][k] || a == k) && !win[k][b][!c] && !los[k][b][!c]) {
if (los[a][b][c]) {
win[k][b][!c] = true;
nxt[k][b] = a;
q.push({k, b, !c});
} else if (--deg[k][b][!c] == 0) {
los[k][b][!c] = true;
q.push({k, b, !c});
}
}
}
}
for (int i = 0; i < N; i++) {
int cnt = 0;
for (int j = 0; j < N; j++)
cnt += win[i][j][0];
if (cnt == N)
return P = i;
}
return -1;
}
int nextMove(int R) {
return P = nxt[P][R];
}
