#include "coprobber.h"
#include "bits/stdc++.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
const int MOD = 1e9 + 7;
const int inf = 2e9;
bool w[MAX_N][MAX_N];
bool f[MAX_N][MAX_N][2];
int vis[MAX_N][MAX_N][2], opt[MAX_N][MAX_N];
vector<int> g[MAX_N];
int pre;
bool calc(int u, int v, int steps) {
if(u == v) {
return f[u][v][steps] = 1;
}
if(vis[u][v][steps] == 2) return f[u][v][steps];
vis[u][v][steps] = 1;
if(steps & 1) {
bool ans = 0;
for(int x : g[u]) {
if(vis[x][v][0] == 1) {
continue;
}
if(calc(x, v, 0)) opt[u][v] = x;
ans = ans | calc(x, v, 0);
}
if(vis[u][v][0] != 1) ans = ans | calc(u, v, 0);
if(calc(u, v, 0)) opt[u][v] = u;
vis[u][v][steps] = 2;
return f[u][v][steps] = ans;
} else {
bool ans = 1;
for(int x : g[v]) {
if(vis[u][x][1] == 1) {
ans = 0;
break;
}
ans = ans & calc(u, x, 1);
}
vis[u][v][steps] = 2;
return f[u][v][steps] = ans;
}
}
int start(int N, bool A[MAX_N][MAX_N]) {
int n = N;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
w[i][j] = A[i][j];
if(w[i][j]) {
g[i].pb(j);
}
}
}
int ans = -1;
for(int i = 0; i < n; i++) {
bool cur = 1;
for(int j = 0; j < n; j++) {
cur = cur & calc(i, j, 1);
}
if(cur) {
pre = i;
return i;
}
}
return ans;
}
int nextMove(int x) {
pre = opt[pre][x];
return pre;
}
