#include "coprobber.h"
#include<vector>
#pragma GCC optimize(2)
int ok[MAX_N][MAX_N][2], move[MAX_N][MAX_N], vis[MAX_N][MAX_N][2], sz[MAX_N][MAX_N];
bool a[MAX_N][MAX_N];
std::vector<int> adj[MAX_N];
int pos;
void dfs(int x, int y, int who)
{
ok[x][y][who] = 1;
if (who == 1) {
for (auto i : adj[x]) {
if (!ok[i][y][0]) {
move[i][y] = x;
dfs(i, y, 0);
}
}
if (!ok[x][y][0]) {
move[x][y] = x;
dfs(x, y, 0);
}
}
else {
for (auto i : adj[y]) {
sz[x][i]--;
if (!sz[x][i] && !ok[x][i][1])
dfs(x, i, 1);
}
}
}
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++)
sz[i][j] = adj[j].size();
for (int i = 0; i < N; i++) {
if (!ok[i][i][0])
dfs(i, i , 0);
if (!ok[i][i][1])
dfs(i, i, 1);
}
for (pos = 0; pos < N; pos++) {
bool still = 1;
for (int i = 0; i < N; i++)
if (!ok[pos][i][0])
still = 0;
if (still)
return pos;
}
return -1;
}
int nextMove(int R)
{
return pos=move[pos][R];
}
