#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> cnt; // cnt[i][j] = how many edges are forbidden between i and j
vector<int> repr, siz;
int ffind(int a) { return (a == repr[a]) ? a : repr[a] = ffind(repr[a]); }
void unite(int u, int v) { // O(N), O(N^2) amortized
u = ffind(u); v = ffind(v);
if (u == v) return;
if (siz[u] > siz[v]) swap(u, v);
repr[u] = v; siz[v] += siz[u];
for (size_t i = 0; i < cnt.size(); ++i)
cnt[v][i] += cnt[u][i];
}
void initialize(int n) {
cnt.resize(n, vector<int>(n, 0));
repr.resize(n);
for (int i = 0; i < n; ++i)
repr[i] = i;
siz.resize(n, 1);
}
int hasEdge(int u, int v) {
int ru = ffind(u), rv = ffind(v);
if (ru == rv) return 1;
if (cnt[ru][rv] + 1 == siz[ru] * siz[rv]) { // We must unite!
unite(ru, rv);
return 1;
} else { // Nah, we can wait
++cnt[ru][rv];
++cnt[rv][ru];
return 0;
}
}
