#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
using tiii = tuple<int, int, int>;
int now, n, D[MAX_N][MAX_N][2], deg[MAX_N][MAX_N][2], W[MAX_N][MAX_N];
bool adj[MAX_N][MAX_N], vs[MAX_N][MAX_N];
int start(int N, bool A[MAX_N][MAX_N]) {
n = N;
memset(W, -1, sizeof(W));
for(int i=0; i<n; i++) for(int j=0; j<n; j++) D[i][j][0] = D[i][j][1] = 1;
for(int i=0; i<n; i++) for(int j=0; j<n; j++) adj[i][j] = A[i][j], deg[0][i][0] += A[i][j], deg[i][j][1] = 1;
for(int i=1; i<n; i++) for(int j=0; j<n; j++) deg[i][j][0] = deg[0][j][0];
for(int i=0; i<n; i++) deg[i][i][0] = deg[i][i][1] = 0;
queue<tiii> que;
for(int i=0; i<n; i++) { que.push((tiii){i, i, 0}); que.push((tiii){i, i, 1}); }
while(que.size()) {
int c, r, t; tie(c, r, t) = que.front(); que.pop();
D[c][r][t] = 0;
if(t == 0) {
for(int i=0; i<n; i++) {
if(adj[r][i] && --deg[c][i][0] == 0) que.push((tiii){c, i, 1});
}
}
else {
for(int i=0; i<n; i++) {
if((adj[c][i] || i == c) && --deg[i][r][1] == 0) {
que.push((tiii){i, r, 0});
W[i][r] = c;
}
}
}
}
for(int i=0; i<n; i++) {
bool fl = 1;
for(int j=0; j<n; j++) if(D[i][j][0] == 1) fl = 0;
if(fl) return now = i;
}
return -1;
}
bool chk(int v, int R) {
for(int i=0; i<n; i++) if(adj[R][i] && vs[v][i]) return 0;
return 1;
}
int nextMove(int R) {
return now = W[now][R];
vs[now][R] = 1;
if(D[now][R][1] == 0 && chk(now, R)) return now;
for(int i=0; i<n; i++) {
if(adj[now][i] && D[i][R][1] == 0 && chk(i, R)) return now = i;
}
return -1;
}
