#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAXN = 1505;
int comps;
int n;
int called;
int root[MAXN], ranks[MAXN];
int findRoot(int node) {
if(root[node] == node) return node;
return root[node] = findRoot(root[node]);
}
bool sameComp(int u, int v) {
return findRoot(u) == findRoot(v);
}
bool unite(int u, int v) {
if(sameComp(u,v)) return false;
int r1 = findRoot(u);
int r2 = findRoot(v);
if(ranks[r1] >= ranks[r2]) {
root[r2] = r1;
ranks[r1] += ranks[r2];
} else {
root[r1] = r2;
ranks[r2] += ranks[r1];
}
return true;
}
void initialize(int _n) {
n = _n;
comps = n;
for(int i=0;i<n;i++) {
root[i] = i;
ranks[i] = 1;
}
}
int hasEdge(int u, int v) {
++called;
if(sameComp(u,v)) {
return 1;
}
if(called == (n*(n-1))/2) {
assert(comps == 2);
return 1;
}
if(comps == 2) return 0;
unite(u,v);
--comps;
return 1;
}
