#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int MAX = 1505;
int N;
int par[MAX];
int c;
set<pii> edges;
int get(int node){
if(par[node] < 0) return node;
return get(par[node]);
}
stack<array<int, 4>> calls;
void unite(int u, int v, bool isTemp){
u = get(u);
v = get(v);
if(u == v) return;
if(-par[u] < -par[v]) swap(u, v);
if(isTemp){
calls.push({u, v, par[u], par[v]});
}
par[u] += par[v];
par[v] = u;
c--;
}
void rollback(){
while(calls.size()){
auto a = calls.top();
par[a[0]] = a[2];
par[a[1]] = a[3];
c++;
calls.pop();
}
}
void initialize(int n) {
memset(par, -1, sizeof(par));
N = n;
c = n;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
edges.insert({i, j});
}
}
}
int hasEdge(int u, int v) {
if(u > v) swap(u, v);
edges.erase({u, v});
unite(u, v, 1);
if(c == 1){
rollback();
return 0;
}
rollback();
for(auto a : edges){
unite(a.first, a.second, 1);
}
if(c != 1){
rollback();
unite(u, v, 0);
return 1;
}
rollback();
return 0;
}
