// mrrrow mnyaa ;3c
// go play vivid/stasis! it's a really awesome free game on steam
int links[1502][1502][2];
bool used[1502];
int n, call_num;
void initialize(int N) {
n = N;
call_num = 0;
for (int i = 1; i <= n; i++) {
links[i][0][1] = 1;
for (int j = 0; j < n; j++) {
links[i][j + 1][0] = j;
links[i][j + 1][1] = j + 2;
}
links[i][n + 1][1] = -1;
}
}
bool dfs(int i, int j, int mi, int ma) {
used[i] = true;
for (int it = links[i][0][1]; it <= ma && links[i][it][1] != -1; it = links[i][it][1])
if (it >= mi && it == j || !used[it] && dfs(it, j, mi, ma)) return true;
return false;
}
int hasEdge(int u, int v) {
call_num++;
u++, v++;
int up = links[u][v][0], un = links[u][v][1];
int vp = links[v][u][0], vn = links[v][u][1];
links[u][up][1] = un;
links[u][un][0] = up;
links[v][vp][1] = vn;
links[v][vn][0] = vp;
for (int i = 1; i <= n; i++) used[i] = false;
if (call_num < n - 1) return false;
int r = 0xffff;
while (u & r > 0 && u & ~r < n) {
if (dfs(u, v, u & r, u & ~r)) return false;
r <<= 1;
}
if (!dfs(u, v, 0, n)) {
links[u][up][1] = v;
links[u][un][0] = v;
links[v][vp][1] = u;
links[v][vn][0] = u;
return true;
} else return false;
}
