#include "game.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
mt19937 rng(time(0));
struct Dsu {
int n;
vi par, sz;
Dsu() {}
Dsu(int n): n(n) {
par.resize(n), sz.resize(n, 1);
iota(all(par), 0);
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
bool Union(int a, int b) {
int pa = Find(a), pb = Find(b);
if (pa == pb) return false;
if (sz[pa] < sz[pb]) swap(pa, pb);
par[pb] = pa;
sz[pa] += sz[pb];
return true;
}
};
set<pii> edges;
set<pii> tree;
int n;
void initialize(int N) {
n = N;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
edges.insert({i, j});
}
}
Dsu dsu(n);
vii e(all(edges));
shuffle(all(e), rng);
for (pii p : e) {
if (dsu.Union(p.x, p.y)) {
tree.insert(p);
}
}
}
int hasEdge(int u, int v) {
if (u > v) swap(u, v);
if (!tree.count({u, v})) {
edges.erase(edges.find({u, v}));
return 0;
}
Dsu dsu(n);
set<pii> next;
vii e(all(edges));
shuffle(all(e), rng);
for (auto [a, b] : e) {
if (a != u || b != v) {
if (dsu.Union(a, b)) next.insert({a, b});
}
}
if (dsu.sz[dsu.Find(0)] != n) return 1;
edges.erase(edges.find({u, v}));
tree = next;
return 0;
}
