#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1.5e3 + 20;
vector<int> adj[maxn];
int q1[maxn];
int q2[maxn];
int flag[maxn];
int t = 1;
mt19937 gen(69420);
void initialize(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j != i) {
adj[i].push_back(j);
}
}
shuffle(adj[i].begin(), adj[i].end(), gen);
}
}
int hasEdge(int u, int v) {
adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
int pt1 = 0;
int sz1 = 1;
int pt2 = 0;
int sz2 = 1;
q1[pt1] = u;
flag[u] = t;
q2[pt2] = v;
flag[v] = t + 1;
while (pt1 < sz1 && pt2 < sz2) {
int x = q1[pt1++];
for (auto y: adj[x]) {
if (flag[y] == t + 1) {
t += 2;
return 0;
}
if (flag[y] != t) {
flag[y] = t;
q1[sz1++] = y;
}
}
x = q2[pt2++];
for (auto y: adj[x]) {
if (flag[y] == t) {
t += 2;
return 0;
}
if (flag[y] != t + 1) {
flag[y] = t + 1;
q2[sz2++] = y;
}
}
}
t += 2;
return 1;
}
