#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int _n;
int allSets[1500][1500]; //<index,#ofthem>
int rankOfRoot[1500];
int parent[1500];
int root(int x) {
if (parent[x]==-1) return x;
return parent[x] = root(parent[x]);
}
void connect(int x, int y) {
int rootX = root(x), rootY = root(y);
if (rootX == rootY) return; // same root
if (rankOfRoot[rootX] > rankOfRoot[rootY]) {
parent[rootY] = rootX;
} else if (rankOfRoot[rootX] < rankOfRoot[rootY] ){
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rankOfRoot[rootX]++;
}
}
bool isConnected(int x, int y) {
return root(x) == root(y);
}
void initialize (int n){
_n = n;
memset(parent,-1,sizeof(parent));
memset(rankOfRoot,1,sizeof(rankOfRoot));
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i==j) allSets[i][j] = 0;
else allSets[i][j] = 1;
}
}
}
int hasEdge(int u, int v){
int x = root(u); int y = root(v);
/*if (u==0 && v==2){
cout << "R" << x << " " << y << endl;
cout << allSets[0][2] << endl;
}*/
allSets[x][y]--;
allSets[y][x]--;
if (allSets[x][y] <= 0){
//connect
connect(x,y);
int z = root(y);
if (z==y){
for (int i=0; i<_n; i++){
if (i==x) continue;
if (i==y) continue;
if (allSets[i][x] <= 0) continue;
int res = allSets[i][x];
allSets[i][x] = 0;
allSets[x][i] = 0;
allSets[i][y] += res;
allSets[y][i] += res;
}
}
if (z==x){
for (int i=0; i<_n; i++){
if (i==x) continue;
if (i==y) continue;
if (allSets[i][y] <= 0) continue;
int res = allSets[i][y];
allSets[i][y] = 0;
allSets[y][i] = 0;
allSets[i][x] += res;
allSets[x][i] += res;
}
}
return 1;
}
else{
return 0;
}
}
