#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
const int NMAX = 510;
vector <int> adia[NMAX + 10];
bool dp[NMAX + 10][NMAX + 10][2];
int to[NMAX + 10][NMAX + 10];
int liber[NMAX + 10][NMAX + 10];
void open(int x, int y, int who)
{
dp[x][y][who] = 1;
if (who == 1) {
/// muta politistul
for (auto i : adia[x]) {
if (!dp[i][y][0]) {
to[i][y] = x;
open(i, y, 0);
}
}
if (!dp[x][y][0]) {
to[x][y] = x;
open(x, y, 0);
}
}
else {
/// hotul muta
for (auto i : adia[y]) {
liber[x][i]--;
if (!liber[x][i] && !dp[x][i][1])
open(x, i, 1);
}
}
}
int act;
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])
adia[i].push_back(j);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
liber[i][j] = adia[j].size();
for (int i = 0; i < N; i++) {
if (!dp[i][i][0])
open(i, i , 0);
if (!dp[i][i][1])
open(i, i, 1);
}
for (act = 0; act < N; act++) {
bool ok = 1;
for (int i = 0; i < N; i++)
if (!dp[act][i][0])
ok = 0;
if (ok)
return act;
}
return -1;
}
int nextMove(int R)
{
act = to[act][R];
return act;
}
