#include <bits/stdc++.h>
using namespace std;
struct dsu {
int n;
vector<int> p, c, f;
dsu() {}
dsu(int m) {
n = m;
p.assign(n, 0);
c.assign(n, 1);
f.assign(n, 0);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
void merge(int a, int b) {
p[b] = a;
f[a] = f[a] + f[b] - c[a] * c[b] * 2;
c[a] += c[b];
}
};
int n, p, k;
dsu d;
void initialize(int N) { n = k = N, d = dsu(n), p = n * (n - 1) / 2; }
int hasEdge(int u, int v) {
u = d.find(u);
v = d.find(v);
if (u == v) {
p--;
return 0;
}
if (d.f[u] + k - 1 == d.c[u] * (n - d.c[u]) || d.f[v] + k - 1 == d.c[v] * (n - d.c[u]) || p == n - 1) {
d.f[u]++;
d.f[v]++;
d.merge(u, v);
k--;
return 1;
}
p--;
return 0;
}
