#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n; vector<int> pai, sz;
vector<vector<int>> attempts;
DSU(int _n=0): n(_n), pai(_n), sz(_n, 1),
attempts(_n, vector<int> (_n, 0)) {
for (int i=0; i<n; i++) pai[i] = i;
}
bool merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
attempts[a][b]++;
attempts[b][a]++;
if (attempts[a][b] < sz[a] * sz[b]) return false;
for (int i=0; i<n; i++) {
attempts[b][i] += attempts[a][i];
attempts[i][b] += attempts[i][a];
}
for (int i=0; i<n; i++) {
if (pai[i] == a) pai[i] = b;
}
sz[b] += sz[a];
return true;
}
int find(int v) {
return pai[v]; // serão diretos mesmo
}
};
int n;
DSU dsu;
void initialize(int N) {
n = N;
dsu = DSU(n);
}
int hasEdge(int u, int v) {
return dsu.merge(u, v);
}
