#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#include "game.h"
int s[1510][1510];
int p[1510];
int sz[1510];
int n;
void initialize(int N) {
n=N;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
s[i][j]=1; s[j][i]=1;
}
p[i]=i;
}
}
int root(int u){
int cr=u;
vector<int> v;
// cout<<cr<<" ";
// cout<<"z"<<flush;
while(p[cr]!=cr){
v.pb(cr);
cr=p[cr];
// cout<<"y"<<flush;
}
//cout<<"z"<<flush;
if(!v.empty()){
// cout<<"z"<<flush;
for(auto nod:v){
p[nod]=cr;
}
}
return cr;
}
void unite(int u, int v){
int ru=root(u), rv=root(v);
if(sz[rv]>sz[ru]){
p[ru]=rv; sz[rv]+=sz[ru];
}
else{
p[rv]=ru; sz[ru]+=sz[rv];
}
}
int hasEdge(int u, int v) {
int ru=root(u), rv=root(v);
if(ru==rv){
return 0;
}
//cout<<"x"<<flush;
if(s[ru][rv]==1){
int w=( (sz[ru]>=sz[rv])?(ru):(rv) );
for(int i=0; i<n; i++){
if( (i==ru)||(i==rv) ){continue;}
s[w][i]=s[i][w]=s[ru][i]+s[rv][i];
}
//cout<<"x"<<flush;
unite(ru, rv);
return 1;
}
else{
s[ru][rv]--; s[rv][ru]--;
return 0;
}
}
