#include <bits/stdc++.h>
#include <game.h>
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){
if(x == parent[x]){
return x;
}
return find_head(parent[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<pair<int,int> > edges;
set<pair<int,int> > e;
dsu d;
void initialize (int n) {
d.n = n;
d.fill();
vector<int> vec;
for (int i = 0; i < n; i++) {
vec.push_back(i);
}
random_shuffle(vec.begin(), vec.end());
for (int i: vec) {
for (int j: vec) {
if (!d.comp(i, j)) {
d.join(i, j);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
e.insert(make_pair(min(i, j), max(i, j)));
}
}
}
}
int hasEdge (int u, int v) {
assert(edges.size() == d.n - 1);
if (!edges.count(make_pair(u, v)) && !edges.count(make_pair(v, u))) {
e.erase(make_pair(min(u, v), max(u, v)));
return false;
}
d.fill();
for (auto& p: edges) {
if (p != make_pair(u, v) && p != make_pair(v, u)) {
d.join(p.first, p.second);
}
}
assert(d.cc == 2);
for (auto& p: e) {
if (p == make_pair(u, v) || p == make_pair(v, u)) continue;
if (!d.comp(p.first, p.second)) {
edges.erase(make_pair(min(u, v), max(u, v)));
e.erase(make_pair(min(u, v), max(u, v)));
edges.insert(p);
return false;
}
}
return true;
}
