#include "game.h"
#include <bits/stdc++.h>
using namespace std;
static const int N=1500, S=100;
static struct DSU{
int n;
vector<int> lab;
void init(int _n){
n=_n;
lab.assign(n, -1);
}
int find_set(int u){
return lab[u]<0?u:lab[u]=find_set(lab[u]);
}
void union_sets(int u, int v){
u=find_set(u); v=find_set(v);
if (u!=v){
if (lab[u]>lab[v]) swap(u, v);
lab[u]+=lab[v];
lab[v]=u;
}
}
} dsu;
static int n;
static set<pair<int, int>> edge[N/S], edge2;
static int cnt[N/S][N/S];
void initialize(int n_) {
n=n_;
for (int i=0; i<n; ++i){
for (int j=i+1; j<n; ++j){
if (i/S==j/S){
edge[i/S].emplace(i, j);
}else{
++cnt[i/S][j/S];
}
}
}
for (int i=0; i<(n+S-1)/S; ++i) for (int j=i+1; j<(n+S-1)/S; ++j) edge2.emplace(i, j);
}
int hasEdge(int u, int v) {
if (u>v) swap(u, v);
if (u/S!=v/S){
u/=S, v/=S;
--cnt[u][v];
if (cnt[u][v]) return 0;
dsu.init((n+S-1)/S);
edge2.erase({u, v});
for (auto &i:edge2) dsu.union_sets(i.first, i.second);
if (dsu.lab[dsu.find_set(0)]+(n+S-1)/S){
edge2.emplace(u, v);
return 1;
}
return 0;
}
int id=u/S;
int size=min(n, id*S+S)-id*S;
dsu.init(size);
edge[id].erase({u, v});
for (auto &i:edge[id]) dsu.union_sets(i.first-S*id, i.second-S*id);
if (dsu.lab[dsu.find_set(0)]+size){
edge[id].emplace(u, v);
return 1;
}
return 0;
}
