#include <bits/stdc++.h>
#include <game.h>
#pragma GCC target ("popcnt")
using namespace std;
struct dsu {
vector<int> parent;
vector<int> compSize;
int n;
int cc;
void fill(){
cc = n;
parent.resize(n), compSize.resize(n);
for(int i = 0; i < n; i++){
parent[i] = i, compSize[i] = 1;
}
}
int find_head(int x){
int o = x;
while (x != parent[x]) {
x = parent[x];
}
parent[o] = x;
return x;
}
void join(int x, int y){
x = find_head(x);
y = find_head(y);
if(x == y){
return;
}
cc--;
if(compSize[x] > compSize[y]){
swap(x,y);
}
parent[x] = y;
compSize[y] += compSize[x];
}
bool comp(int x, int y){
return (find_head(x) == find_head(y));
}
};
set<int> edges[(int)1500];
int deg[(int)1500];
bitset<1500> e[(int)1500];
dsu d;
void initialize (int n) {
d.n = n;
d.fill();
vector<pair<int,int> > vec;
for (int i = 0; i < n; i++) {
deg[i] = 0;
for (int j = i + 1; j < n; j++) {
vec.push_back(make_pair(i, j));
}
}
random_shuffle(vec.begin(), vec.end());
for (auto& p: vec) {
if (d.comp(p.first, p.second)) {
continue;
}
d.join(p.first, p.second);
edges[p.first].insert(p.second);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
e[i].set(j);
deg[i]++, deg[j]++;
}
}
}
int hasEdge (int u, int v) {
if (u > v) {
swap(u, v);
}
if (!edges[u].count(v)) {
e[u].set(v, false);
deg[u]--, deg[v]--;
return false;
}
d.fill();
for (int i = 0; i < d.n; i++) {
for (int j: edges[i]) {
if (make_pair(i, j) != make_pair(u, v)) {
d.join(i, j);
}
}
}
vector<int> ord;
ord.push_back(u), ord.push_back(v);
for (int i = 0; i < d.n; i++) {
if (i == u || i == v) continue;
ord.push_back(i);
}
if (e[u].size() == 1) {
return true;
}
vector<int> head(d.n);
for (int i = 0; i < d.n; i++) {
head[i] = d.find_head(i);
}
for (int i: ord) {
int x = head[i];
for (int j = i; j < d.n; j++) {
if (!e[i][j]) continue;
if (edges[i].count(j)) {
continue;
}
int y = head[j];
if (x != y) {
edges[u].erase(v);
e[u].set(v, false);
deg[u]--, deg[v]--;
edges[i].insert(j);
return false;
}
}
}
return true;
}
