#include "game.h"
#include <bits/stdc++.h>
using namespace std;
class UFDS {
typedef vector<int> vi;
public:
vi p, rak, setSize;
int numSets;
void create(int n){
setSize.assign(n, 1);
numSets = n;
rak.assign(n, 0);
p.assign(n, 0);
for(int i =0;i < n;i++){
p[i] = i;
}
}
int findSet(int i){
return (p[i] == i) ? i : (p[i] = findSet(p[i]));
}
bool isSameSet(int i, int j){
return findSet(i) == findSet(j);
}
void unionSet(int i, int j){
if(isSameSet(i,j))
return;
numSets--;
int x = findSet(i);
int y = findSet(j);
if(rak[x] > rak[y]) {
p[y] = x; setSize[x] += setSize[y];
}
else {
p[x] = y; setSize[y] += setSize[x];
if(rak[x] == rak[y]) rak[y]++;
}
}
};
UFDS uf;
typedef pair<int,int> ii;
map<ii, int> m;
int N;
void initialize(int n) {
uf.create(n);
N = n;
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
m[ii(i,j)] = 1;
}
}
}
ii mii(int x, int y){
if(x < y) return ii(x,y);
else return ii(y,x);
}
int hasEdge(int u, int v) {
if(uf.isSameSet(u,v)){
return 0;
}
int x = uf.findSet(u);
int y = uf.findSet(v);
if(m[mii(x,y)] == 1){
uf.unionSet(u,v);
for(int i = 0;i < N;i++){
int w = i;
int z = uf.findSet(u);
m[mii(w,z)] = m[mii(w,x)] + m[mii(w,y)];
}
return 1;
}
else{
m[mii(x,y)]--;
return 0;
}
}
