#include "game.h"
#include <vector>
using namespace std;
#define MAX_N 1500
int group[MAX_N+1];
bool b[MAX_N+1];
int num[MAX_N+1];
int graph[MAX_N+1][MAX_N+1];
vector<int> v;
int N;
int findg(int x){
if(group[x]==group[group[x]]){
return group[x];
}
while(x!=group[x]){
v.push_back(x);
x=group[x];
}
while(!v.empty()){
group[v.back()]=x;
v.pop_back();
}
return x;
}
bool mrg(int x, int y){
x=findg(x); y=findg(y);
if(x==y){
return false;
}
if(graph[x][y]>1){
graph[x][y]--;
graph[y][x]--;
return false;
}
if(graph[x][y]==1){
graph[x][y]--;
graph[y][x]--;
if(num[x]>num[y]){
int tmp=x;x=y;y=tmp;
}
group[x]=y;
num[y]+=num[x];
b[x]=false;
for(int i=0; i<N; i++){
if(b[i]){
graph[y][i]+=graph[x][i];
graph[i][y]=graph[y][i];
graph[x][i]=0;
graph[i][x]=0;
}
}
return true;
}
return false;
}
void initialize(int n) {
N=n;
for(int i=0; i<N; i++){
num[i]=1;
group[i]=i;
b[i]=true;
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(i!=j){
graph[i][j]=1;
}
}
}
}
int hasEdge(int u, int v) {
return mrg(u, v);
}
