#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];
int where_go[MAX_N][MAX_N];
vector<int> graf[MAX_N];
int n;
int cur_poz;
int start(int N, bool A[MAX_N][MAX_N])
{
n = N;
queue<dp> winning_pos;
rep(i,0,n-1)
{
rep(j,0,n-1)
{
if(A[i][j] == 1)
{
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.front();
winning_pos.pop();
// cout << t.police << " " << t.rob << " " << t.move << " win\n";
DP[t.police][t.rob][t.move] = 1;
if(t.move == 0)
{
for(auto it: graf[t.police])
{
zlicz[it][t.rob][1]--;
//cout << it << " " << t.rob << " " << 1 << " " << zlicz[it][t.rob][1] << " new\n";
if(zlicz[it][t.rob][1] == 0)
{
where_go[it][t.rob] = t.police;
winning_pos.push({t.rob,it,1});
}
}
zlicz[t.police][t.rob][1]--;
// cout << t.police << " " << t.rob << " " << 1 << " " << zlicz[t.police][t.rob][1] << " new\n";
if(zlicz[t.police][t.rob][1] == 0)
{
where_go[t.police][t.rob] = t.police;
winning_pos.push({t.rob,t.police,1});
}
}
if(t.move == 1)
{
for(auto it: graf[t.rob])
{
zlicz[t.police][it][0]++;
// cout << t.police << " " << it << " " << 0 << " " << zlicz[t.police][it][0] << " new\n";
if(zlicz[t.police][it][0] == 1)
{
winning_pos.push({it,t.police,0});
// where_go[t.police][it] =
}
}
}
}
rep(start,0,n-1)
{
bool is = true;
rep(end,0,n-1)
{
if(DP[start][end][0] == false)
{
// cout << start << " " << end << " se\n";
is = false;
break;
}
}
if(is)
{
cur_poz = start;
return start;
}
}
return -1;
}
int nextMove(int R)
{
return where_go[cur_poz][R];
}
// int main()
// {
// int n;
// cin >> n;
// bool A[500][500];
// rep(i,0,n-1)
// {
// rep(j,0,n-1)
// {
// cin >> A[i][j];
// }
// }
// int poz = start(n,A);
// cout << "police: " << poz << "\n";
// if(poz == -1)
// {
// return 0;
// }
// cout << "Rob poz: ";
// int rob;
// cin >> rob;
// while(poz != rob)
// {
// poz = nextMove(rob);
// cout << "new poz: " << poz << "\n";
// cout << "Rob: ";
// cin >> rob;
// }
// }
