#include "game.h"
#include <iostream>
#define MAXN 1505
using namespace std;
int N, Num[MAXN], can[MAXN][MAXN];
class DSU {
public:
int Set[MAXN];
void init(int n) {
for (int i=0; i<=n; i++) {Set[i] = i;}
}
int Find(int x) {
return(Set[x] == x ? x : Set[x] = Find(Set[x]));
}
void Union(int x, int y) {
int p1 = Find(x), p2 = Find(y);
Set[p1] = p2;
Num[p2] = 0;
for (int i=0; i<N; i++) {
if (Find(i) == p2) {can[p2][i] = 0;}
else {can[p2][i] += can[p1][i];}
Num[p2] += can[p2][i];
//printf("DEBUG %d %d %d\n",p2,i,can[p2][i]);
}
}
} UF;
void initialize(int n) {
UF.init(n), N=n;
for (int i=0; i<n; i++) {
Num[i]= n-1;
for (int j=0; j<n; j++) {
can[i][j] = i != j;
}
}
}
int hasEdge(int u, int v) {
int U = UF.Find(u), V = UF.Find(v);
if (U == V) {return(0);}
if (Num[U] == 1 || Num[V] == 1) {
UF.Union(u,v);
return(1);
} else {
Num[U ] -= 1;
Num[V ] -= 1;
can[U][V] = can[V][U] = 0;
return(0);
}
}
