#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 f,s,move;
};
// DP[police][robber][turn]
bool DP[MAX_N][MAX_N][2];
int zlicz[MAX_N][MAX_N];
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)
{
winning_pos.push({i,i,1});
DP[i][i][1] = true;
}
rep(pocz,0,n-1)
{
rep(kon,0,n-1)
{
zlicz[pocz][kon] = (int)graf[kon].size();
}
}
while(!winning_pos.empty())
{
dp t = winning_pos.front();
winning_pos.pop();
int p = t.f;
int k = t.s;
if(t.move == 0)
{
rep(new_v,0,n-1)
{
if(A[new_v][k])
{
zlicz[p][new_v]--;
if (zlicz[p][new_v] == 0 && !DP[p][new_v][1])
{
DP[p][new_v][1] = true;
winning_pos.push({p,new_v,1});
}
}
}
}
else
{
if(!DP[p][k][0])
{
where_go[p][k] = p;
DP[p][k][0] = true;
winning_pos.push({p,k,0});
}
rep(new_v,0,n-1)
{
if(A[new_v][p] && !DP[new_v][k][0])
{
where_go[new_v][k] = p;
DP[new_v][k][0] = true;
winning_pos.push({new_v,k,0});
}
}
}
}
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)
{
cur_poz = where_go[cur_poz][R];
return cur_poz;
}
// 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;
// }
// }
