#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 1500;
int g[nax][nax];
int n;
int sz[nax], qr[nax], par[nax];
void initialize(int N) {
n = N;
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) if(i!=j) {
g[i][j] = 2;
}
}
for(int i=0; i<n; ++i) {
sz[i] = 1, par[i] = i, qr[i] = 0;
}
}
int find(int v) {
return par[v] = (v==par[v]) ? v : find(par[v]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if(sz[u] < sz[v]) swap(u, v);
qr[u] = (qr[u] + qr[v] - 2 * (sz[u] * sz[v] - 1));
sz[u] += sz[v];
par[v] = u;
}
bool must(int v) {
v = find(v);
if(qr[v]==sz[v] * (n-sz[v]) - 1) return 1;
return 0;
}
int hasEdge(int u, int v) {
if(u==v) return 0;
if(g[u][v]!=2) return g[u][v];
if(find(u)==find(v)) return g[v][u] = g[u][v] = 0;
for(int x : {u, v}) {
if(must(x)) {
unite(u, v);
return g[u][v] = g[v][u] = 1;
}
}
qr[find(u)]++;
qr[find(v)]++;
return g[u][v] = g[v][u] = 0;
}
