#include "game.h"
#include <vector>
using namespace std;
const int MAX_N = 1500;
int n;
bool ap[MAX_N][MAX_N];
vector<pair<int, int>> edges;
struct DSU {
int comp;
vector<int> parent;
void init(int n) {
parent.clear();
parent.resize(n);
for (int v = 0; v < n; v++)
parent[v] = v;
comp = n;
}
int findParent(int v) {
if (parent[v] != v)
parent[v] = findParent(parent[v]);
return parent[v];
}
void connect(int u, int v) {
u = findParent(u);
v = findParent(v);
if (u == v)
return;
comp--;
parent[u] = v;
}
};
void initialize(int N) {
n = N;
edges.clear();
for (int u = 0; u < n; u++) {
for (int v = u + 1; v < n; v++)
ap[u][v] = false;
}
}
int hasEdge(int u, int v) {
ap[u][v] = ap[v][u] = true;
DSU dsu;
dsu.init(n);
for (auto e: edges)
dsu.connect(e.first, e.second);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (ap[i][j])
continue;
dsu.connect(i, j);
}
}
if (dsu.comp == 1)
return 0;
edges.push_back({u, v});
return 1;
}
