#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
int n;
vector<int> sz, par;
vector<vector<int>> comp;
set<int> compo;
void initialize(int _n) { n=_n;
sz.resize(n, 1), par.resize(n), comp.resize(n, vector<int>(n, 0)); iota(all(par), 0);
for (int i=0; i<n; i++) compo.insert(i);
}
int get(int x) {
if (x==par[x]) return x;
return par[x]=get(par[x]);
}
bool same(int a, int b) { return get(a)==get(b); }
int merge(int a, int b) {
a=get(a), b=get(b);
if (a==b) return 0;
if (a>b) swap(a, b);
comp[a][b]++;
if (comp[a][b]<sz[a]*sz[b]) return 0;
if (sz[b]>sz[a]) swap(a, b);
sz[a]+=sz[b];
par[b]=a;
for (auto u: compo) comp[min(a, u)][max(a, u)]+=comp[min(b, u)][max(b, u)];
compo.erase(b);
return 1;
}
int hasEdge(int u, int v) {
return merge(u, v);
}
