#include "game.h"
#include "bits/stdc++.h"
using namespace std;
const int maxn = 1501;
int dsu[maxn];
int tmp[maxn];
int adj[maxn][maxn];
int N;
int Find (int i) {
return dsu[i] == i ? i : dsu[i] = Find(dsu[i]);
}
void Union (int i, int j) {
dsu[Find(i)] = Find(j);
}
void initialize(int n) {
N = n;
for (int i = 0 ; i < n ; i++) {
dsu[i] = i;
for (int j = i + 1 ; j < n ; j++) adj[i][j] = 0;
}
}
int hasEdge(int u, int v) { // u < v
if (v < u) swap(u, v);
if (Find(u) == Find(v)) {
adj[u][v] = 1;
return 0;
}
int ret = 0;
copy(dsu, dsu + N, tmp);
for (int i = 0 ; i < N ; i++) {
for (int j = i + 1 ; j < N ; j++) {
if (!adj[i][j] and Find(i) != Find(j)) Union(i, j);
}
}
int rut = Find(0);
for (int i = 1 ; i < N ; i++) if (rut != Find(i)) ret = 1;
copy(tmp, tmp + N, dsu);
if (ret) Union(u, v);
adj[u][v] = 1;
return ret;
}
