#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const int MAXN = 3000 + 10;
int n, f[MAXN][MAXN], id[MAXN], par[MAXN], sz[MAXN], dsz = 0;
void initialize(int n_) {
n = n_;
for (int i = 1; i <= n; i++) {
id[i] = par[i] = i;
sz[i] = 1;
}
dsz = n;
}
inline int find(int v) {
return par[v] == v ? v : par[v] = find(par[v]);
}
inline void unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
for (int i = 1; i <= dsz; i++)
f[dsz + 1][i] = f[i][dsz + 1] = f[id[u]][i] + f[id[v]][i];
par[v] = u;
sz[u] += sz[v];
id[u] = ++dsz;
}
int hasEdge(int u, int v) {
u++;
v++;
if (f[id[find(u)]][id[find(v)]] == sz[find(u)] * sz[find(v)] - 1) {
unite(u, v);
return 1;
}
f[id[find(u)]][id[find(v)]]++;
f[id[find(v)]][id[find(u)]]++;
return 0;
}
