#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1505;
int n, par[MAXN], nver[MAXN], nedge[MAXN];
int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
bool join(int p, int q) {
p = anc(p), q = anc(q);
++nedge[p];
++nedge[q];
if (nedge[p] == nver[p] * (n - nver[p]) || nedge[q] == nver[q] * (n - nver[q])) {
// join p, q
nedge[p] -= nver[p] * nver[q];
nedge[q] -= nver[p] * nver[q];
nedge[q] += nedge[p]; nedge[p] = 0;
nver[q] += nver[p]; nver[p] = 0;
par[p] = q;
return true;
} else {
return false;
}
}
void initialize(int N) {
n = N;
for (int i = 0; i < n; ++i) {
par[i] = i;
nver[i] = 1;
nedge[i] = 0;
}
}
int hasEdge(int u, int v) {
return join(u, v);
}
