#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
struct DSU {
vector<int> p;
vector<int> r;
vector<int> q;
DSU(int n) {
p.assign(n,0);
r.assign(n,0);
forn(i,n) p[i]=i;
q.assign(n,n-1);
}
int get(int i) {
return p[i]==i ? i : get(p[i]);
}
void uni(int a, int b) {
a=get(a);
b=get(b);
if (r[a]==r[b]) r[a]++;
if (r[a]>r[b]) {
p[b]=a;
q[a]+=q[b]-2;
} else {
p[a]=b;
q[b]+=q[a]-2;
}
}
void substract(int a, int b) {
a=get(a);
b=get(b);
--q[a];
--q[b];
}
int getq(int a) {
a=get(a);
return q[a];
}
};
DSU dsu(0);
int q;
void initialize(int n) {
DSU paiu(n);
dsu=paiu;
q=n*(n-1)/2;
//cout<<"!"<<dsu.p.size()<<'\n';
}
int hasEdge(int u, int v) {
--q;
if (q==1) {
return 0;
}
if (q==0) {
return 1;
}
int U=dsu.getq(u);
int V=dsu.getq(v);
if (U<=2 || V<=2) {
dsu.uni(u,v);
return 1;
} else {
dsu.substract(u,v);
return 0;
}
}
