#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> p;
vector<vector<int>> st;
void xxx(int n) {
this->n = n;
p.resize(n);
st.resize(n);
for (int i = 0; i < n; ++i) {
p[i] = i;
st[i].push_back(i);
}
}
int find_set(int v) {
return v == p[v] ? v : p[v] = find_set(p[v]);
}
void unite(int u, int v) {
u = find_set(u);
v = find_set(v);
if (u == v) return;
if (st[u].size() > st[v].size()) swap(u, v);
p[u] = v;
for (auto i : st[u]) {
st[v].push_back(i);
}
st[u].clear();
}
};
DSU g;
bool used[1500][1500];
void initialize(int n) {
g.xxx(n);
}
int hasEdge(int U, int V) {
int u = g.find_set(U);
int v = g.find_set(V);
if (u == v) return 0;
used[U][V] = used[V][U] = true;
bool flag = false;
for (auto a : g.st[u]) {
for (auto b : g.st[v]) {
if (!used[a][b]) {
flag = true;
break;
}
}
}
if (flag) return 0;
g.unite(U, V);
return 1;
}
