#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
} else {
return false;
}
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
} else {
return false;
}
}
constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;
class UnionFindWithCounter {
Vec<i32> par;
Vec<i32> cnt;
i32 root(i32 x) {
if (par[x] < 0) {
return x;
} else {
return par[x] = root(par[x]);
}
}
public:
UnionFindWithCounter() = default;
UnionFindWithCounter(i32 n) : par(n, -1), cnt(n, 0) {}
bool same(i32 x, i32 y) {
x = root(x);
y = root(y);
return x == y;
}
void unite(i32 x, i32 y) {
x = root(x);
y = root(y);
if (x == y) {
return;
}
if (-par[x] > -par[y]) {
swap(x, y);
}
cnt[y] += cnt[x];
cnt[x] = 0;
par[y] += par[x];
par[x] = y;
}
void increase(i32 x) {
x = root(x);
++cnt[x];
}
i32 access(i32 x) {
x = root(x);
return cnt[x];
}
i32 size(i32 x) {
x = root(x);
return -par[x];
}
};
i32 m;
UnionFindWithCounter uf;
void initialize(int n) {
m = n;
uf = UnionFindWithCounter(m);
}
i32 cut(i32 v) {
return v * (m - v) + v * (v - 1) / 2 - v + 1;
}
int hasEdge(int u, int v) {
i32 sz_u = uf.size(u);
i32 cnt_u = uf.access(u);
i32 sz_v = uf.size(v);
i32 cnt_v = uf.access(v);
if (cnt_u == cut(sz_u) - 1 || cnt_v == cut(sz_v) - 1) {
uf.unite(u, v);
return 1;
} else {
uf.increase(u);
uf.increase(v);
return 0;
}
}
