#include "coprobber.h"
#include <vector>
#include <algorithm>
using namespace std;
vector<int> nei[555];
int st[555], en[555], cur, E, tr, R, C;
void dfs(int u){
st[u] = ++cur;
for (int i : nei[u]){
nei[i].erase(find(begin(nei[i]), end(nei[i]), u));
dfs(i);
}
en[u] = ++cur;
}
int start(int n, bool A[MAX_N][MAX_N]){
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (A[i][j])
nei[i].push_back(j), E++;
}
}
if (E == n + n - 2)
dfs(0), tr = 1;
else{
for (int i=1;i < n and R + C == 0;i++)
if (A[i-1][i] == 0)
C = i, R = n / C;
}
return 0;
}
int I, J;
int nextMove(int R){
J = R;
if (tr == 1){
for (int i : nei[I]){
if (st[i] <= st[J] and en[J] <= en[i])
I = i;
}
return I;
}
int v = I / C - J / C;
int h = I % C - J % C;
if (abs(v) == 1 and abs(h) == 1)
return I;
if (v >= 0 and h >= 0){
if (v > h)
I = I - C;
else
I--;
}
else if (v >= 0){
if (v > abs(h))
I = I - C;
else
I++;
}
else if (h >= 0){
if (abs(v) > h)
I = I + C;
else
I--;
}
else{
if (abs(v) > abs(h))
I = I + C;
else
I++;
}
return I;
}
