#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> cnt, s;
vector<int> p;
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void unite(int u, int v) {
u = find(u);
v = find(v);
if (s[u].size() > s[v].size()) {
swap(u, v);
}
for (int x : s[u]) {
p[x] = v;
s[v].push_back(x);
}
for (int i = 0; i < n; i++) {
if (i == v) {
continue;
}
cnt[i][v] += cnt[i][u];
cnt[v][i] += cnt[u][i];
}
}
void initialize(int _n) {
n = _n;
cnt = vector(n, vector<int>(n));
s.resize(n);
p.resize(n);
for (int i = 0; i < n; i++) {
p[i] = i;
s[i].push_back(i);
}
}
int hasEdge(int u, int v) {
int a(find(u));
int b(find(v));
int x(s[a].size());
int y(s[b].size());
if (cnt[a][b] + 1 == x * y) {
unite(u, v);
return 1;
}
cnt[a][b]++;
cnt[b][a]++;
return 0;
}
