#include <bits/stdc++.h>
#include "game.h"
#define shit cout << "shit\n";
using namespace std;
struct subset{
int parent;
int rank;
};
subset subsets[1510];
int n;
int find(int x){
if(subsets[x].parent==-1)return x;
subsets[x].parent = find(subsets[x].parent);
return subsets[x].parent;
}
void Union(int X,int Y){
int x = find(X);
int y = find(Y);
if(subsets[x].rank<subsets[y].rank){
subsets[x].parent = y;
}else if(subsets[x].rank>subsets[y].rank){
subsets[y].parent = x;
}else{
subsets[x].parent = y;
subsets[y].rank++;
}
}
bool flag[1501][1501];
void initialize(int N) {
n=N;
for(int i=0;i<n;i++){
subsets[i] = {-1,1};
}
}
bool getRemaining(int u,int v){
vector<int> u_set,v_set;
int U =find(u),V = find(v);
for(int i=0;i<n;i++){
// int p = find(i);
int p = subsets[i].parent;
if(p==U)u_set.push_back(i);
if(p==V)v_set.push_back(i);
}
int C = 0;
// for(int a:u_set)
// cout << a << "\t";
// cout << endl;
// for(int b:v_set)
// cout << b << "\t";
// cout << endl;
for(int a:u_set){
for(int b:v_set){
if(!flag[a][b])C++;
if(C>=2)return false;
}
}
return true;
}
int hasEdge(int u, int v) {
int r = 0;
if(getRemaining(u,v))r=1;
flag[u][v] =flag[v][u] = true;
if(r==1)
Union(u,v);
return r;
}
// int main(){
// int n,r;
// cin >> n >> r;
// initialize(n);
// for(int i=0;i<r;i++){
// int a,b;
// cin >> a >> b;
// cout << hasEdge(a,b) << "\n";
// }
// }
