#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;
}
vector<Pos> rev_adj(){
vector<Pos> res;
if(player_id == 0){
for(auto e: adj[r_pos]){
res.push_back(Pos(1, cop_pos, e));
}
}
if(player_id == 1){
for(auto e: adj[cop_pos]){
res.push_back(Pos(0, e, r_pos));
}
res.push_back(Pos(0, cop_pos, r_pos));
}
return res;
}
bool& vis(){
return is_vis[player_id][cop_pos][r_pos];
}
bool operator<(const Pos b)const{
if(player_id!=b.player_id){
return player_id<b.player_id;
}
if(cop_pos != b.cop_pos){
return cop_pos<b.cop_pos;
}
if(r_pos != b.r_pos){
return r_pos < b.r_pos;
}
return false;
}
};
int cop_pos = 0;
void calc(Pos cur){
if(cur.vis()){
return;
}
cur.vis() = true;
if(cur.player_id == 1){
for(auto e: cur.rev_adj()){
if(!e.vis()){
next_pos[e.cop_pos][e.r_pos] = cur.cop_pos;
calc(e);
}
}
}
else{
for(auto e: cur.rev_adj()){
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++){
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();
}
}
vector<Pos> wining;
for(int i = 0; i<N; i++){
calc(Pos(0, i, i));
calc(Pos(1, i, i));
}
while(wining.size()>0){
Pos cur = wining.back();
cur.vis() = true;
wining.pop_back();
if(cur.player_id == 1){
for(auto e: cur.rev_adj()){
if(!e.vis()){
e.vis() = true;
next_pos[e.cop_pos][e.r_pos] = cur.cop_pos;
wining.push_back(e);
}
}
}
else{
for(auto e: cur.rev_adj()){
if(!e.vis()){
rem[e.cop_pos][e.r_pos]--;
if(rem[e.cop_pos][e.r_pos] == 0){
e.vis() = true;
wining.push_back(e);
}
}
}
}
}
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;
}
