#include "game.h"
#include "bits/stdc++.h"
using namespace std;
typedef int ll;
typedef pair<ll,ll>pairll;
#define fr first
#define sc second
ll p[1507],f[1507],d[1507][1507];
set<pairll>s;
ll n,m,g;
ll P(ll x){
if(p[x]!=x)p[x]=P(p[x]);
return p[x];
}
void A(ll x,ll y){
if(rand()%2)swap(x,y);
x=P(x);
y=P(y);
p[y]=x;
return ;
}
void initialize(int N) {
n=N;
for(int i=0;i<n;i++){
p[i]=i;
for(int j=i+1;j<n;j++){
s.insert({i,j});
}
}
for(auto it:s){
if(P(it.fr)!=P(it.sc)){
A(it.fr,it.sc);
d[it.fr][it.sc]=1;
d[it.sc][it.fr]=1;
g--;
}else{
d[it.fr][it.sc]=0;
d[it.sc][it.fr]=1;
}
}
return ;
}
int hasEdge(int u, int v) {
if(d[u][v]==0)return 0;
else{
if(u>v)swap(u,v);
s.erase({u,v});
for(int i=0;i<n;i++){
p[i]=i;
}
g=n-1;
for(auto it:s){
if(P(it.fr)!=P(it.sc)){
A(it.fr,it.sc);
d[it.fr][it.sc]=1;
d[it.sc][it.fr]=1;
g--;
}else{
d[it.fr][it.sc]=0;
d[it.sc][it.fr]=1;
}
}
if(g!=0){
A(u,v);
s.insert({u,v});
return 1;
}else return 0;
}
return 0;
}
