#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
int posc;
//const int MAX_N = 500;
vi choice[MAX_N+1][MAX_N+1][3];
int start(int N, bool A[MAX_N][MAX_N]) {
int ct[MAX_N+1][MAX_N+1][3], win[MAX_N+1][MAX_N+1][3];
vi deg(N);
for_(i, 0, N) for_(j, 0, N) if (A[i][j]) deg[i] += 1;
queue<vi> q; // {0, 0, 0 -> cop / 1 -> robber}
for_(i, 0, N) {
win[i][i][0] = win[i][i][1] = true;
q.push({i, i, 0});
q.push({i, i, 1});
}
while (q.size()) {
vi curr = q.front(); q.pop();
if (curr[2] == 0) {
for_(i, 0, N) if (A[i][curr[1]] and !win[curr[0]][i][1]) {
ct[curr[0]][i][1] += 1;
if (ct[curr[0]][i][1] == deg[i]) {
win[curr[0]][i][1] = true;
choice[curr[0]][i][1] = curr;
q.push({curr[0], i, 1});
}
}
} else {
for_(i, 0, N) if ((A[i][curr[0]] or i == curr[0]) and !win[i][curr[1]][0]) {
win[i][curr[1]][0] = true;
choice[i][curr[1]][0] = curr;
q.push({i, curr[1], 0});
}
}
}
posc = -1;
for_(i, 0, N) {
int c = 0;
for_(j, 0, N) c += win[i][j][0];
if (c == N) {
posc = i;
//cout << "can start at " << i << endl;
}
}
return posc;
}
int nextMove(int R) {
//cout << posc << " " << R << endl;
posc = choice[posc][R][0][0];
return posc;
}
//int main() {
//#ifndef ONLINE_JUDGE
//freopen("test.in", "r", stdin);
//#endif
//ios_base::sync_with_stdio(false);
//cin.tie(0);
//bool A[MAX_N][MAX_N] = {{0, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}};
//cout << start(4, A) << endl;
//cout << nextMove(1) << endl;
//cout << nextMove(0) << endl;
//return 0;
//}
