#include "game.h"
int cnt[1500][1500];
int link[1500], h[1500], m;
int _find(int x){
if(x == link[x]) return x;
return link[x] = _find(link[x]);
}
bool _unite(int x, int y){
x = _find(x), y = _find(y);
if(x == y) return 1;
if(h[x] + h[y] == m) return 0;
if(cnt[x][y] >= 2){
cnt[x][y]--; cnt[y][x]--;
return 0;
}
link[x] = y; h[y] += h[x];
for(int i=0;i<m;i++){
cnt[y][i] += cnt[x][i]; cnt[i][y] += cnt[i][x];
}
return 1;
}
void initialize(int n) {
m = n;
for(int i=0;i<n;i++){
link[i] = i; h[i] = 1;
for(int j=0;j<n;j++) cnt[i][j] = 1;
}
}
int hasEdge(int u, int v) {
return _unite(u, v);
}
