#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],a[1507][1507],h,k[1507];
set<ll>s[1507],l[1507];
ll n,m,g;
void A(ll x,ll y){
if(rand()%2)swap(x,y);
d[x][y]=1;
d[y][x]=1;
l[x].insert(y);
l[y].insert(x);
s[y].erase(x);
s[x].erase(y);
return ;
}
ll F(ll x,ll y){
for(auto i:s[x]){
if(k[i]!=h){
A(x,i);
return 1;
}
}
for(auto i:l[x]){
if(i!=y){
if(F(i,x)==1)return 1;
}
}
return 0;
}
void K(ll x,ll y){
k[x]=h;
for(auto i:l[x]){
if(i!=y)K(i,x);
}
return ;
}
ll Del(ll x,ll y){
d[x][y]=0;
d[y][x]=0;
//s[x].erase(y);
//s[y].erase(x);
l[x].erase(y);
l[y].erase(x);
if(rand()%2)swap(x,y);
h++;
K(x,x);
if(F(x,x)==1)return 0;
else{
d[x][y]=1;
d[y][x]=1;
l[x].insert(y);
l[y].insert(x);
//s[x].insert(y);
//s[y].insert(x);
return 1;
}
}
void initialize(int N) {
n=N;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
a[i][j]=1;
a[j][i]=1;
s[i].insert(j);
s[j].insert(i);
}
}
for(int i=1;i<n;i++){
A(i,0);
}
return ;
}
int hasEdge(int u, int v) {
if(d[u][v]==0){
s[u].erase(v);
s[v].erase(u);
return 0;
}
else{
return Del(u,v);
}
return 0;
}
