#include "bits/stdc++.h"
#include "game.h"
using namespace std;
#define MAX_N 1503
#define all(v) (v).begin() ,(v).end()
int n;
vector <int> adj[MAX_N];
vector <pair<int ,int>> tree;
vector <bool> bld_vis;
void bld_tree(int u){
bld_vis[u] = 1;
for(int&v : adj[u]) if(!bld_vis[v]){
tree.push_back({u ,v});
bld_tree(v);
}
}
void get_tree(){
fill(bld_vis.begin() ,bld_vis.end() ,0);
tree.clear();
bld_tree(rand()%n);
}
void initialize(int N) {
srand(time(NULL));
n = N;
bld_vis.resize(n);
for(int u=0; u<n; u++){
for(int v=u+1; v<n; v++){
adj[u].push_back(v);
adj[v].push_back(u);
}
random_shuffle(all(adj[u]));
}
get_tree();
}
int conn = 0;
bool vis[MAX_N];
void dfs(int u){
vis[u] = 1 ,conn++;
for(auto&v : adj[u]) if(!vis[v])
dfs(v);
}
int hasEdge(int u, int v) {
adj[u].erase(find(all(adj[u]) ,v));
adj[v].erase(find(all(adj[v]) ,u));
if(find(all(tree) ,make_pair(u ,v)) != tree.end()
|| find(all(tree) ,make_pair(v ,u)) != tree.end()){
memset(vis ,0 ,sizeof vis) ,conn = 0 ,dfs(u);
if(conn == n){
get_tree();
return 0;
}else{
adj[u].push_back(v); random_shuffle(all(adj[u]));
adj[v].push_back(u); random_shuffle(all(adj[v]));
return 1;
}
}
return 0;
}
