#include "game.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int nax = 81;
int N;
struct Dsu {
int par[nax];
int sz[nax];
Dsu(int n=nax) {
for(int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
}
int find(int v) {
if (par[v] == v) {
return v;
}
return par[v] = find(par[v]);
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) {
return false;
}
if (sz[b] > sz[a]) {
swap(a, b);
}
par[b] = a;
sz[a] += sz[b];
return true;
}
bool form_full() {
return sz[find(0)] == N;
}
};
bool form_full(Dsu a, Dsu& b) {
for(int i = 0; i < N; i++) {
for(int j = i+1; j < N; j++) {
if (b.find(i) == b.find(j)) {
a.unite(i, j);
}
}
}
return a.form_full();
}
Dsu curr;
vector<pair<int, int>> edges;
void initialize(int n) {
N = n;
// curr + all Yes -> form full
// curr + all No -> not form full
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
edges.emplace_back(i, j);
}
}
}
int hasEdge(int u, int v) {
if (u > v) {
swap(u, v);
}
edges.erase(find(edges.begin(), edges.end(), pair<int, int>(u, v)));
Dsu curr_add = curr;
curr_add.unite(u, v);
if (curr_add.form_full()) {
return 0;
}
Dsu curr_all = curr_add;
for(auto& i : edges) {
curr_all.unite(i.first, i.second);
}
if (!curr_all.form_full()) {
return 0;
}
curr = curr_add;
return 1;
}
