#include "game.h"
#include <iostream>
using namespace std;
int n,par[1510],rnk[1500],ok[1500][1500];
void initialize(int _n) {
n = _n;
for(int i = 0;i < n;i++){
par[i] = i;
rnk[i] = 0;
}
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++) ok[i][j] = 1;
ok[i][i] = 0;
}
}
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void unite(int x,int y){
x = find(x);
y = find(y);
int a = x,b = y;
if(rnk[x] < rnk[y]) par[x] = y;
else{
par[y] = x;
if(rnk[x] == rnk[y]) rnk[x]++;
}
for(int i = 0;i < n;i++){
int tmp = ok[i][a] + ok[i][b];
ok[i][a] = 0;
ok[i][b] = 0;
ok[i][find(x)] = tmp;
tmp = ok[a][i] + ok[b][i];
ok[a][i] = 0;
ok[b][i] = 0;
ok[find(x)][i] = tmp;
}
}
bool same(int x,int y){
return find(x) == find(y);
}
int hasEdge(int u, int v) {
int x = find(u),y = find(v);
/*for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++) cout << ok[i][j] << " ";
cout << endl;
}*/
if(x == y) return 1;
ok[x][y]--;
ok[y][x]--;
if(!ok[x][y]){
unite(u,v);
return 1;
}
return 0;
}
