#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;
using state = tuple<int, int, int>;
vector<state> adj_rev[MAX_N][MAX_N][2];
bool win[MAX_N][MAX_N][2];
bool los[MAX_N][MAX_N][2];
bool vis[MAX_N][MAX_N][2];
int deg[MAX_N][MAX_N][2];
pii pos[MAX_N][MAX_N][2];
void dfs(state v) {
auto [a, b, p] = v;
vis[a][b][p] = true;
for (state u : adj_rev[a][b][p]) {
auto [aa, bb, pp] = u;
if (vis[aa][bb][pp]) continue;
if (los[a][b][p]) {
win[aa][bb][pp] = true;
pos[aa][bb][pp] = {a, b};
} else if (--deg[aa][bb][pp] == 0)
los[aa][bb][pp] = true;
else
continue;
dfs(u);
}
}
int P;
int start(int N, bool A[MAX_N][MAX_N]) {
vector<vector<int>> adj(N + 1);
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 a = 0; a < N; a++)
for (int b = 0; b < N; b++)
for (int p = 0; p < 2; p++) {
if (p == 0)
win[a][b][p] = a == b;
else
los[a][b][p] = a == b;
if (win[a][b][p] || los[a][b][p])
continue;
if (p == 0) {
adj_rev[a][b][!p].push_back({a, b, p});
deg[a][b][p]++;
for (int k : adj[a]) {
adj_rev[k][b][!p].push_back({a, b, p});
deg[a][b][p]++;
}
} else {
for (int k : adj[b]) {
adj_rev[a][k][!p].push_back({a, b, p});
deg[a][b][p]++;
}
}
}
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
for (int p = 0; p < 2; p++)
if ((win[a][b][p] || los[a][b][p]) && !vis[a][b][p])
dfs({a, b, p});
for (int i = 0; i < N; i++) {
int cnt = 0;
for (int j = 0; j < N; j++)
if (win[i][j][0])
cnt++;
if (cnt == N) return P = i;
}
return -1;
}
int nextMove(int R) {
return P = pos[P][R][0].first;
}
