#include <deque>
#include <vector>
#include <bitset>
constexpr int N = 1500;
int n{};
std::bitset<N> mask;
std::vector<std::bitset<N>> edges;
void initialize(int _n) {
n = _n;
edges.assign(n, {});
for (int i = 0; i < n; ++i) mask[i] = true;
for (int i = 0; i < n; ++i) {
edges[i] = ~edges[i] & mask;
}
}
int hasEdge(int u, int v) {
edges[u][v] = edges[v][u] = false;
if (edges[v].count() > edges[u].count()) {
std::swap(u, v);
}
std::bitset<N> not_visited = mask;
std::bitset<N> new_vs;
new_vs[u] = true, not_visited[u] = false;
while (new_vs.any() and not_visited[v]) {
std::bitset<N> next_new_vs;
for (int i = 0; i < n; ++i) {
if (new_vs[i]) {
next_new_vs |= edges[i];
}
}
new_vs = next_new_vs & not_visited;
not_visited &= ~new_vs;
}
if (not_visited[v]) {
edges[u][v] = edges[v][u] = true;
}
return edges[u][v];
}
