#include"bits/stdc++.h"
using namespace std;
#include "game.h"
bitset<1500> adj[1500], st[1500], badst;
int n;
// adj[i][j] = 1 if there is an edge from i to j which still exists
// st[i][j] = 1 if the edge from i to j is an edge in the st
// badst[i] = 1 if the node i is connected to v through the edges of the st after edge u v is deleted
vector<int> madj[1500];
void initialize(int N) {
n = N;
for (int i = 0 ; i < n ; i++) {
if (i + 1 < n) {
st[i][i + 1] = 1;
st[i + 1][i] = 1;
madj[i].push_back(i + 1);
madj[i + 1].push_back(i);
}
adj[i] = 0;
for (int j = 0 ; j < n ; j++) {
adj[i][j] = i != j;
}
}
}
int badu;
void dfs (int cur) {
// cerr << cur << endl;
badst[cur] = 1;
for (int j : madj[cur]) {
if (j != badu and badst[j] == 0) dfs(j);
}
}
int hasEdge(int u, int v) {
if (!st[u][v]) {
adj[u][v] = 0;
adj[v][u] = 0;
return 0;
}
badst = 0;
badu = u;
dfs(v);
adj[u][v] = adj[v][u] = 0;
for (int i = 0 ; i < n ; i++) {
if (!badst[i]) {
auto j = adj[i] & badst;
int k = j._Find_first();
if (k < n) {
st[u][v] = st[v][u] = 0;
st[i][k] = st[k][i] = 1;
madj[u].erase(find(madj[u].begin(), madj[u].end(), v));
madj[v].erase(find(madj[v].begin(), madj[v].end(), u));
madj[i].push_back(k);
madj[k].push_back(i);
// cerr << i << " " << k << endl;
return 0;
}
}
}
adj[u][v] = adj[v][u] = 1;
return 1;
}
