#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;
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;
}
int hasEdge(int u, int v) {
if(u > v) swap(u, v);
unite(u, v, 1);
if(c == 1){
rollback();
return 0;
}
rollback();
unite(u, v, 0);
return 1;
}
