#include "game.h"
int n, tot, e;
int rem[1500];
int p[1500];
int mat[1500][1500];
int find(int a) {
if (p[a] != a) p[a] = find(p[a]);
return p[a];
}
bool dsu(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
p[b] = a; rem[a] = 0;
for (int i = 0; i < n; ++i) {
int par = find(i);
if (par == a) {
mat[a][i] = 0;
}
else mat[a][i] += mat[b][i];
rem[a] += mat[a][i];
}
return true;
}
void initialize(int n) {
::n = n;
for (int i = 0; i < n; ++i) {
rem[i] = n - 1, p[i] = i;
for (int j = 0; j < n; ++j) if (j != i) mat[i][j] = 1;
}
tot = n * (n - 1) / 2;
e = n - 1;
}
int hasEdge(int u, int v) {
if (e == 1 && tot > 1) {
--tot;
return 0;
}
if (e == tot) {
--e; --tot;
return 1;
}
int U = find(u), V = find(v);
--tot;
if (V == U) {
return 0;
}
--rem[U]; --rem[V];
if (rem[U] == 0 || rem[V] == 0) {
dsu(U, V);
--e;
return 1;
}
return 0;
}
