#include "game.h"
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 1500;
int coef[1 + nmax][1 + nmax];
int n;
namespace Dsu{
int mult[1 + nmax];
int sz[1 + nmax];
void init(){
for(int i = 0;i < n; i++)
mult[i] = i;
for(int i = 0;i < n; i++)
sz[i] = 1;
}
int jump(int gala){
if(mult[gala] != gala)
mult[gala] = jump(mult[gala]);
return mult[gala];
}
void unite(int gala, int galb){
gala = jump(gala);
galb = jump(galb);
sz[galb] += sz[gala];
for(int i = 0; i < n; i++)
coef[i][galb] += coef[i][gala];
for(int i = 0; i < n; i++)
coef[galb][i] += coef[gala][i];
mult[gala] = galb;
}
}
void initialize(int n_) {
n = n_;
Dsu::init();
}
int hasEdge(int u, int v) {
u = Dsu::jump(u);
v = Dsu::jump(v);
coef[u][v]++;
coef[v][u]++;
if(Dsu::sz[u] * Dsu::sz[v] == coef[u][v]) {
Dsu::unite(u, v);
return 1;
} else
return 0;
}
