#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct UF {
vector<int> pere;
void init(int n) {
pere.resize(n);
iota(pere.begin(), pere.end(), 0);
}
int root(int x) {
return x == pere[x] ? x : pere[x] = root(pere[x]);
}
void merge(int x, int y) {
pere[root(x)] = root(y);
}
};
UF uf;
vector<int> non_explore;
vector<vector<int>> graphe;
void initialize(int n) {
uf.init(n);
non_explore.assign(n, n-1);
graphe.assign(n, vector<int>(n, -1));
for (int i=0; i < n; i++) {
graphe[i][i] = 2;
}
}
void complete(int u) {
if (non_explore[uf.root(u)] != 1) return;
auto it = find(graphe[u].begin(), graphe[u].end(), -1);
int v = it - graphe[u].begin();
graphe[u][v] = 1;
graphe[v][u] = 1;
int total_non_explore = non_explore[uf.root(u)] + non_explore[uf.root(v)] - 2;
uf.merge(u, v);
non_explore[uf.root(u)] = total_non_explore;
complete(v);
}
int hasEdge(int u, int v) {
if (graphe[u][v] != -1) {
return graphe[u][v];
} else if (non_explore[uf.root(u)] > 1 && non_explore[uf.root(v)] > 1) {
graphe[u][v] = 0;
graphe[v][u] = 0;
non_explore[uf.root(u)]--;
non_explore[uf.root(v)]--;
}
complete(u);
complete(v);
return graphe[u][v];
}
