#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#ifdef B01
#include "../deb.h"
#else
#define deb(...)
#endif
struct dsu {
vector<int> p;
dsu() {}
dsu(int n) {
p.assign(n, -1);
}
inline int get(int x) {
return (p[x] < 0 ? x : (p[x] = get(p[x])));
}
inline void unite(int x, int y) {
x = get(x);
y = get(y);
if (p[x] < p[y]) {
swap(x, y);
}
p[y] += p[x];
p[x] = y;
}
};
const int N = 2003;
int n;
dsu d;
int g[N][N];
void initialize(int n_) {
n = n_;
d = dsu(n);
memset(g, -1, sizeof g);
}
int hasEdge(int u, int v) {
if (g[u][v] == -1) {
g[u][v] = g[v][u] = 0;
int pu = d.get(u);
int pv = d.get(v);
if (pu != pv) {
vector<int> cur;
for (int i = 0; i < n; i++) {
if (d.get(i) == pu) {
cur.push_back(i);
}
}
bool found = false;
for (int i = 0; i < n; i++) {
int pi = d.get(i);
if (pi == pu) {
continue;
}
for (int uu : cur) {
if (g[uu][i] != 0) {
found = true;
}
}
}
if (!found) {
g[u][v] = g[v][u] = 1;
d.unite(u, v);
} else {
found = false;
cur.clear();
for (int i = 0; i < n; i++) {
if (d.get(i) == pv) {
cur.push_back(i);
}
}
for (int i = 0; i < n; i++) {
int pi = d.get(i);
if (pi == pv) {
continue;
}
for (int vv : cur) {
if (g[vv][i] != 0) {
found = true;
}
}
}
if (!found) {
d.unite(u, v);
g[u][v] = g[v][u] = 1;
}
}
}
}
return g[u][v];
}
