#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];
}
};
mt19937 mt(998244353);
i32 m;
Vec<i32> deg;
Vec<Vec<i32>> rem;
set<pair<i32, i32>> st;
//UnionFindWithCounter uf;
void initialize(int n) {
m = n;
deg = Vec<i32>(m, m - 1);
rem = Vec<Vec<i32>>(m, Vec<i32>(m, 1));
REP(i, m) {
rem[i][i] = 0;
}
//uf = UnionFindWithCounter(m);
}
void opt(i32 u, i32 v) {
st.insert(make_pair(u, v));
st.insert(make_pair(v, u));
--deg[u];
--deg[v];
rem[u][v] = rem[v][u] = 0;
if (deg[u] == 1) {
REP(x, m) {
if (rem[u][x]) {
opt(u, x);
}
}
}
if (deg[v] == 1) {
REP(x, m) {
if (rem[v][x]) {
opt(v, x);
}
}
}
}
int hasEdge(int u, int v) {
if (m == 2) {
return 1;
}
--deg[u];
--deg[v];
rem[u][v] = rem[v][u] = 0;
if (deg[u] == 1) {
REP(x, m) {
if (rem[u][x]) {
opt(u, x);
}
}
}
if (deg[v] == 1) {
REP(x, m) {
if (rem[v][x]) {
opt(v, x);
}
}
}
if (st.count(make_pair(u, v))) {
return 1;
} else {
return 0;
}
}
