#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct disjoint_set {
int n;
vector<int> parent;
vector<list<int>> elem;
vector<vector<int>> maybe_cnt;
disjoint_set() {}
disjoint_set(int n)
: n(n), parent(n), elem(n), maybe_cnt(n, vector<int>(n, 1)) {
iota(parent.begin(), parent.end(), 0);
for (int i = 0; i < n; ++i) {
maybe_cnt[i][i] = 0;
elem[i].push_back(i);
}
}
bool query(int u, int v) {
u = parent[u];
v = parent[v];
if (maybe_cnt[u][v] == 1) {
for (int i : elem[v]) {
parent[i] = u;
}
elem[u].splice(elem[u].end(), elem[v]);
for (int x = 0; x < n; ++x) {
if (parent[x] != x) continue;
maybe_cnt[u][x] += maybe_cnt[v][x];
maybe_cnt[x][u] += maybe_cnt[x][v];
}
return true;
} else {
--maybe_cnt[u][v];
--maybe_cnt[v][u];
return false;
}
}
};
disjoint_set ds;
void initialize(int n) {
ds = disjoint_set(n);
}
int hasEdge(int u, int v) {
return ds.query(u, v);
}
