#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define P complex<int>
vector<vector<int>> adj;
bool B[MAX_N][MAX_N];
int N;
int rem[MAX_N][MAX_N];
int next_pos[MAX_N][MAX_N];
bool is_vis[2][MAX_N][MAX_N];
struct Pos{
int player_id;
int cop_pos, r_pos;
Pos(){};
Pos(int _id, int _cop_pos, int _r_pos){
player_id = _id;
cop_pos = _cop_pos;
r_pos = _r_pos;
}
bool& vis(){
return is_vis[player_id][cop_pos][r_pos];
}
};
int cop_pos = 0;
void calc(Pos cur){
if(cur.vis()){
return;
}
cur.vis() = true;
if(cur.player_id == 1){
for(auto s: adj[cur.cop_pos]){
auto e =Pos(0, s, cur.r_pos);
if(!e.vis()){
next_pos[e.cop_pos][e.r_pos] = cur.cop_pos;
calc(e);
}
}
}
else{
for(auto s: adj[cur.r_pos]){
auto e =Pos(1, cur.cop_pos, s);
if(!e.vis()){
rem[e.cop_pos][e.r_pos]--;
if(rem[e.cop_pos][e.r_pos] == 0){
calc(e);
}
}
}
auto e =Pos(1, cur.cop_pos, cur.r_pos);
if(!e.vis()){
rem[e.cop_pos][e.r_pos]--;
if(rem[e.cop_pos][e.r_pos] == 0){
calc(e);
}
}
}
}
int start(int _N, bool A[MAX_N][MAX_N])
{
N= _N;
adj.resize(N);
for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
is_vis[0][i][j] = false;
is_vis[1][i][j] = false;
if(A[i][j]){
adj[i].push_back(j);
}
}
}
for(int i = 0; i<N; i++){
for(int j= 0; j<N; j++){
rem[i][j] = adj[j].size();
}
}
for(int i = 0; i<N; i++){
calc(Pos(0, i, i));
calc(Pos(1, i, i));
}
for(int i = 0; i<N; i++){
bool ok = true;
for(int j = 0; j<N; j++){
if(!is_vis[0][i][j]){
ok = false;
}
}
if(ok){
cop_pos = i;
return i;
}
}
return -1;
}
int nextMove(int R)
{
cop_pos = next_pos[cop_pos][R];
return cop_pos;
}
