#include <bits/stdc++.h>
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
vector<vector<bool>> dd, used;
int cc;
struct dsu {
int n;
vector<int> e;
dsu() {};
dsu(int n): n(n) {
e.resize(n, -1);
}
int get(int u) {
return e[u] < 0 ? u : e[u] = get(e[u]);
}
bool same(int u, int v) {
return get(u) == get(v);
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (u != v) {
if (e[u] > e[v]) {
swap(u, v);
}
e[u] += e[v];
e[v] = u;
}
}
void reset() {
fill(e.begin(), e.end(), -1);
}
} G;
int hasEdge(int u, int v) {
if (u > v) {
swap(u, v);
}
G.reset();
int n = G.n;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (i != u || j != v) {
if (dd[i][j]) {
if (used[i][j]) {
G.unite(i, j);
}
} else {
G.unite(i, j);
}
}
}
}
dd[u][v] = true;
used[u][v] = !G.same(u, v);
cc -= used[u][v];
return used[u][v];
}
void initialize(int n) {
cc = n;
G = dsu(n);
used.resize(n, vector<bool>(n, false));
dd = used;
}
