#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int n;
struct DSU {
vector<int> par, rank, setsize;
int numsets;
vector<vector<int>> con;
explicit DSU(int n) {
par.assign(n, 0);
iota(begin(par), end(par), 0);
rank.assign(n, 0);
setsize.assign(n, 1);
con.assign(n, vector<int>(n));
numsets = n;
}
int findSet(int x) { return (par[x] == x) ? x : (par[x] = findSet(par[x])); }
bool sameSet(int x, int y) { return findSet(x) == findSet(y); }
bool unite(int x, int y) {
if (sameSet(x, y)) return false;
x = findSet(x), y = findSet(y);
if (rank[x] > rank[y]) swap(x, y);
par[x] = y;
for (int i = 0; i < n; ++i) {
con[y][i] += con[x][i];
con[i][y] = con[y][i];
}
if (rank[x] == rank[y]) ++rank[y];
setsize[y] += setsize[x];
--numsets;
return true;
}
};
DSU dsu(1);
void initialize(int n) {
::n = n;
dsu = DSU(n);
}
int hasEdge(int u, int v) {
int a = dsu.findSet(u);
int b = dsu.findSet(v);
dsu.con[a][b]++;
dsu.con[b][a]++;
if (dsu.con[a][b] == dsu.setsize[a] * dsu.setsize[b]) {
dsu.unite(a, b);
return 1;
} else {
return 0;
}
}
