#include "game.h"
int n;
int p[1500];
int mat[1500][1500],mem[1500][1500];
int sz[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;
sz[a] += sz[b];
p[b] = a;
for (int i = 0; i < n; ++i) {
if(i!=a && i!=b)
mat[a][i] += mat[b][i],mat[i][a]+=mat[i][b];
}
return true;
}
void initialize(int n) {
::n = n;
for (int i = 0; i < n; ++i) {
sz[i] = 1; p[i] = i;
for (int j = 0; j < n; ++j) mem[i][j] =mem[j][i]= -1;
}
}
int hasEdge(int u, int v) {
if (mem[u][v] == -1) {
int U = find(u), V = find(v);
if (U == V) return 0;
if (sz[U] * sz[V] - 1 == mat[U][V]) {
mem[u][v] = mem[v][u] = 1;
dsu(U, V);
}
else {
++mat[U][V]; ++mat[V][U];
mem[u][v] = mat[v][u] = 0;
}
}
return mem[u][v];
}
