#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int n;
bool has_edge[1505][1505];
namespace ufds {
int lnk[1505], sz[1505];
void init(int n) {
iota(lnk, lnk + n, 0);
fill(sz, sz + n, 1);
}
int find(int x) {
if (x == lnk[x]) return x;
return lnk[x] = find(lnk[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
lnk[b] = a;
}
};
void initialize(int n) {
::n = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
has_edge[i][j] = 1;
}
}
}
int hasEdge(int u, int v) {
if (u > v) swap(u, v);
ufds::init(n);
has_edge[u][v] = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (has_edge[i][j]) ufds::unite(i, j);
}
}
int comps = 0;
for (int i = 0; i < n; i++) {
if (i == ufds::find(i)) comps++;
}
return has_edge[u][v] = comps != 1;
}
