#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int N = 1600;
int cnt[N][N], a[N], sz[N];
int nn;
int find(int x) {
if (a[x] == x)return x;
return a[x] = find(a[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
assert(x != y);
a[x] = y, sz[y] += sz[x];
rep(i, 0, nn)
cnt[i][y] += cnt[i][x],
cnt[y][i] += cnt[i][x];
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x,int y) {
return x + rng() % (y - x + 1);
}
bool al[N][N];
void initialize(int n) {
nn = n;
rep(i, 0, n)a[i] = i;
for (int i = 0; i < n-1; i += 2)
if (i+1 < n)al[i][i+1] = 1;
}
int c = 0;
int hasEdge(int u, int v) {
if (u>v)swap(u, v);
if(al[u][v]) {
unite(u, v);
return 1;
}
u = find(u), v = find(v);
cnt[u][v] += 1, cnt[v][u] += 1;
if (cnt[u][v] == sz[u]*sz[v]) {
unite(u, v);
return 1;
}
return 0;
}
//void solve() {
//}
//int32_t main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//solve();
//return 0;
//}
