#include <bits/stdc++.h>
#include "coprobber.h"
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define pii pair<int,int>
#define pb push_back
using namespace std;
struct dp
{
int rob,police,move;
};
// DP[police][robber][turn]
bool DP[MAX_N][MAX_N][2];
int zlicz[MAX_N][MAX_N][2];
vector<int> graf[MAX_N];
int n;
int cur_poz;
int start(int N, bool A[MAX_N][MAX_N])
{
n = N;
stack<dp> winning_pos;
rep(i,0,n-1)
{
rep(j,0,n-1)
{
if(A[i][j] == 0)
{
graf[i].push_back(j);
}
}
}
rep(i,0,n-1)
{
rep(j,0,n-1)
{
for(auto& it: graf[j])
{
zlicz[i][j][1]++;
}
zlicz[i][j][0] = 0;
}
}
rep(i,0,n-1)
{
winning_pos.push({i,i,0});
winning_pos.push({i,i,1});
zlicz[i][i][0] = 1;
zlicz[i][i][1] = 0;
}
while(!winning_pos.empty())
{
dp t = winning_pos.top();
winning_pos.pop();
DP[t.police][t.rob][t.move] = 1;
if(t.move == 0)
{
for(auto it: graf[t.police])
{
zlicz[it][t.rob][1]--;
if(zlicz[it][t.rob][1] == 0)
{
winning_pos.push({t.rob,it,1});
}
}
zlicz[t.police][t.rob][1]--;
if(zlicz[t.police][t.rob][1] == 0)
{
winning_pos.push({t.rob,t.police,1});
}
}
if(t.move == 1)
{
for(auto it: graf[t.rob])
{
zlicz[t.police][it][0]++;
if(zlicz[it][t.rob][1] == 1)
{
winning_pos.push({it,t.police,1});
}
}
}
}
rep(start,0,n-1)
{
bool is = true;
rep(end,0,n-1)
{
if(DP[start][end][0] == false) is = false;
}
if(is)
{
cur_poz = start;
return start;
}
}
return -1;
}
int nextMove(int R)
{
for(auto it: graf[cur_poz])
{
if(DP[it][R][1]) return it;
}
}
