#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int pai[505][505], cop_pos;
bool vis[505][505][2];
int qtd[505][505];
int start(int N, bool A[MAX_N][MAX_N]) {
// lugar do policial, lugar do ladrao, de quem é a vez
vector<vector<int>> edges(N);
queue<trio> fila;
for(int i = 0; i < N; i++) {
fila.push({i,i,0});
fila.push({i,i,1});
vis[i][i][0] = vis[i][i][1] = 1;
}
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(A[i][j]) edges[i].pb(j);
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
qtd[i][j] = sz(edges[j]);
while(!fila.empty()) {
auto [cop, robber, flag] = fila.front();
fila.pop();
if(flag == 0) {
// é a vez do policial
for(auto viz : edges[robber]) {
qtd[cop][viz]--;
if(qtd[cop][viz] == 0 and !vis[cop][viz][1])
fila.push({cop, viz, 1}), vis[cop][viz][1] = 1;
}
}
else {
// vez do ladrao
for(auto viz : edges[cop]) {
if(!vis[viz][robber][0])
fila.push({viz, robber, 0}), vis[viz][robber][0] = 1, pai[viz][robber] = cop;
}
if(!vis[cop][robber][0])
fila.push({cop, robber, 0}), vis[cop][robber][0] = 1, pai[cop][robber] = cop;
}
}
for(int i = 0; i < N; i++) {
bool ok = 1;
for(int j = 0; j < N; j++)
if(!vis[i][j][0]) ok = 0;
if(ok) return cop_pos = i;
}
return -1;
}
int nextMove(int R) {
return cop_pos = pai[cop_pos][R];
}
