#include "coprobber.h"
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#define X first
#define Y second
#define PB push_back
using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair < int, int > pii;
typedef pair < pii, bool > ppi;
int pob[MAX_N][MAX_N][2], n;
vector < ppi > v[MAX_N][MAX_N][2];
queue < ppi > Q;
int u[MAX_N][MAX_N], cur, a[MAX_N][MAX_N];
int start(int N, bool A[MAX_N][MAX_N]){
n = N;
// 0 je cajo na potezu 1 je lopov
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(A[i][j]){
a[i][j] = 1;
for(int k = 0;k < n;k++){
v[i][k][1].PB({{j, k}, 0}); // edgevi su obrnuti
v[k][i][0].PB({{k, j}, 1});
}
}
}
}
for(int i = 0;i < n;i++){
pob[i][i][1] = 1;
}
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
u[i][j] = (int)v[i][j][1].size();
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
//if(pob[i][j][0]) Q.push({{i, j}, 0});
if(pob[i][j][1]) Q.push({{i, j}, 1});
}
}
for(;!Q.empty();){
int x = Q.front().X.X;
int y = Q.front().X.Y;
int z = Q.front().Y;
Q.pop();
for(ppi N : v[x][y][z]){
int nx = N.X.X;
int ny = N.X.Y;
if(pob[nx][ny][!z]) continue;
if(z){
pob[nx][ny][!z] = 1;
Q.push({{nx, ny}, !z});
}
else{
u[nx][ny]--;
if(!u[nx][ny]){
pob[nx][ny][!z] = 1;
Q.push({{nx, ny}, !z});
}
}
}
}
for(int i = 0;i < n;i++){
int bad = 0;
for(int j = 0;j < n;j++) bad |= !pob[i][j][0];
if(!bad) return cur = i;
}
return -1;
}
int nextMove(int R){
for(int i = 0;i < n;i++){
if(a[cur][i] && pob[i][R][1]) return cur = i;
}
return -1;
}
