#include <iostream>
using namespace std;
#define MAX_N 500
// modify the following functions
// you can define global variables and functions
int qu[MAX_N * MAX_N * 2], dd[MAX_N][MAX_N], nxt[MAX_N][MAX_N];
int i_;
int start(int N, bool A[MAX_N][MAX_N]) {
int i, j, k;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
nxt[i][j] = -1;
int head = 0, cnt = 0;
for (j = 0; j < N; j++) {
int d = 0;
for (k = 0; k < N; k++)
if (A[j][k])
d++;
for (i = 0; i < N; i++)
if (i == j)
qu[head + cnt++] = (i * N + j) * 2 + 1;
else
dd[i][j] = d;
}
while (cnt) {
int ijt = qu[cnt--, head++], i = ijt / 2 / N, j = ijt / 2 % N, t = ijt % 2;
if (t == 1) {
for (k = 0; k < N; k++)
if ((k == i || A[k][i]) && nxt[k][j] == -1)
nxt[k][j] = i, qu[head + cnt++] = (k * N + j) * 2 + 0;
} else {
for (k = 0; k < N; k++)
if (A[k][j] && --dd[i][k] == 0)
qu[head + cnt++] = (i * N + k) * 2 + 1;
}
}
return head == N * N * 2 ? 0 : -1;
}
int nextMove(int R) {
return (i_ = nxt[i_][R]);
}
