#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];
ll n,m,g;
void A(ll x,ll y){
if(rand()%2)swap(x,y);
d[x][y]=1;
d[y][x]=1;
return ;
}
ll F(ll x,ll y){
if(rand()%2==0){
for(int i=n-1;i>0;i--){
if(d[x][i]==0 && a[x][i]==1 && i!=x && k[i]!=h){
A(x,i);
d[x][i]=1;
d[i][x]=1;
return 1;
}else if(d[x][i]==1 && i!=y){
if(F(i,x)==1)return 1;
}
}
}else{
for(int i=0;i<n;i++){
if(d[x][i]==0 && a[x][i]==1 && i!=x && k[i]!=h){
A(x,i);
d[x][i]=1;
d[i][x]=1;
return 1;
}else if(d[x][i]==1 && i!=y){
if(F(i,x)==1)return 1;
}
}
}
return 0;
}
void K(ll x,ll y){
k[x]=h;
for(int i=0;i<n;i++){
if(d[i][x]==1 && i!=y)K(i,x);
}
return ;
}
ll Del(ll x,ll y){
d[x][y]=0;
d[y][x]=0;
a[x][y]=0;
a[y][x]=0;
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;
a[x][y]=1;
a[y][x]=1;
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;
}
}
for(int i=1;i<n;i++){
A(i,0);
}
return ;
}
int hasEdge(int u, int v) {
if(d[u][v]==0){
a[u][v]=0;
a[v][u]=0;
return 0;
}
else{
return Del(u,v);
}
return 0;
}
