#include "bits/stdc++.h"
#include "game.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
using ll = long long;
const int mod = 1e9+7;
vector<int> siz, link;
int n;
vector<vector<int>> cnt;
void initialize(int _n) {
n = _n;
siz.resize(n, 1);
link.resize(n);
for (int i = 0; i < n; ++i) link[i] = i;
cnt.resize(n);
for (auto &x : cnt) x.resize(n);
}
int find(int x) {
while (link[x] != x) x = link[x];
return x;
}
bool same(int a, int b) {
return find(a) == find(b);
}
int hasEdge(int u, int v) {
u = find(u);
v = find(v);
if (same(u, v)) {
return 1;
}
if (u < v) swap(u, v);
if (cnt[u][v] < siz[u] * siz[v] - 1) {
++cnt[u][v];
return 0;
}
siz[u] += siz[v];
link[v] = u;
for (int i = 0; i < u; ++i) cnt[u][i] += cnt[v][i];
for (int i = u+1; i < n; ++i) cnt[i][u] += cnt[i][v];
return 1;
}
