#include "game.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=1505;
vector<int> E[N];
int n;
int d[N];
vector<pair<int, int> > span;
/*bool bfs(int s){
vector<int> V={s};
d[s]=1;
vector<pair<int, int> > span2;
for(int i=0; i<V.size(); i++){
int v=V[i];
for(int u:E[v]){
if(!d[u]){
d[u]=d[v]+1;
V.push_back(u);
span2.push_back({min(u, v), max(u, v)});
}
}
}
for(int i:V)d[i]=0;
if(V.size()==n)span=span2;
return (V.size()==n);
}*/
int lo[N], pre[N], par[N];
int wsk;
void dfs(int v){
pre[v]=wsk++;
for(int u:E[v]){
if(!pre[u]){
par[u]=v;
dfs(u);
//lo[v]=min(lo[v], lo[u]);
}
//else if(u!=par[v])lo[v]=min(lo[v], pre[u]);
}
}
bool check(int s){
wsk=1;
dfs(s);
for(int u=0; u<n; u++)pre[u]=0;
if(wsk!=n+1)return 0;
span.clear();
for(int u=0; u<n; u++)if(u!=s)span.push_back({min(u,par[u]), max(u, par[u])});
return 1;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
void initialize(int _n){
n=_n;
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
E[i].push_back(j);
E[j].push_back(i);
}
}
check(rng()%n);
}
int hasEdge(int u, int v) {
if(u>v)swap(u, v);
for(int &j:E[u])if(j==v)swap(j, E[u].back());
for(int &j:E[v])if(j==u)swap(j, E[v].back());
E[u].pop_back();
E[v].pop_back();
bool b=0;
//cout<<u<<" "<<v<<"\n";
for(auto j:span)if(j.st==u && j.nd==v)b=1;
//for(auto j:span)cout<<j.st<<" "<<j.nd<<"\n";
//cout<<"\n";
if(!b)return 0;
if(check(rng()%n)){
return 0;
}
E[u].push_back(v);
E[v].push_back(u);
return 1;
}
