#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int N, cnt = 0, par[1500];
bool valid[1500][1500];
int fp(int x) {
if (par[x] == -1) return x;
return par[x] = fp(par[x]);
}
void initialize(int n) {
N = n;
memset(par, -1, sizeof(par));
memset(valid, true, sizeof(valid));
for (int i = 0; i < n; i++) valid[i][i] = false;
}
int hasEdge(int u, int v) {
cnt++;
if (cnt == N * (N-1) / 2) return 1;
int cu = 0, cv = 0;
for (int i = 0; i < N; i++) {
if (valid[i][u]) cu++;
if (valid[i][v]) cv++;
}
if (cu == 1 || cv == 1) {
int pu = fp(u), pv = fp(v);
par[pu] = pv;
for (int i = 0; i < N; i++) {
if (pv != fp(i)) continue;
valid[i][u] = valid[u][i] = valid[i][v] = valid[v][i] = false;
}
return 1;
} else {
valid[u][v] = valid[v][u] = false;
return 0;
}
}
