#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1500 + 1;
int n;
int queried[MAX_N][MAX_N];
int par[MAX_N];
vector<int> group[MAX_N];
int remain_deg[MAX_N];
int find(int x) {
return par[x] = (x == par[x] ? x : find(par[x]));
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (group[u].size() > group[v].size()) swap(u, v);
par[u] = v;
for (int x: group[u]) group[v].push_back(x);
remain_deg[v] = 0;
for (int x: group[v]) {
for (int i=0; i<n; ++i) {
if (find(i) != v && queried[find(i)][x] != 0) {
remain_deg[v]++;
}
}
}
// cout << u << ' ' << v << ' ' << remain_deg[v] << endl;
}
void initialize(int N) {
n = N;
memset(queried, -1, sizeof queried);
iota(par, par+n, 0);
for (int i=0; i<n; ++i) group[i].push_back(i);
fill(remain_deg, remain_deg+n, n-1);
}
int hasEdge(int u, int v) {
if (find(u) == find(v)) {
queried[u][v] = queried[v][u] = 1;
} else {
if (remain_deg[find(u)] == 1 || remain_deg[find(v)] == 1) {
queried[u][v] = queried[v][u] = 1;
merge(u, v);
} else {
queried[u][v] = queried[v][u] = 0;
remain_deg[find(u)]--;
remain_deg[find(v)]--;
}
}
return queried[u][v];
}
