#include "game.h"
#include <bits/stdc++.h>
#pragma GCC target("popcnt")
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
struct Dsu {
int n;
vi par, sz;
vvi cnt;
Dsu() {}
Dsu(int n): n(n) {
par.resize(n), sz.resize(n, 1);
iota(all(par), 0);
cnt.resize(n, vi(n, 1));
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
bool Union(int a, int b) {
int pa = Find(a), pb = Find(b);
if (pa == pb) return false;
if (sz[pa] < sz[pb]) swap(pa, pb);
par[pb] = pa;
sz[pa] += sz[pb];
for (int i = 0; i < n; i++) {
cnt[pa][i] += cnt[pb][i];
cnt[i][pa] += cnt[i][pb];
}
return true;
}
};
const int MAX_N = 1505;
int n;
Dsu dsu;
void initialize(int N) {
n = N;
dsu = Dsu(n);
}
int hasEdge(int u, int v) {
int a = dsu.Find(u), b = dsu.Find(v);
if (dsu.cnt[a][b] > 1) {
dsu.cnt[a][b]--, dsu.cnt[b][a]--;
return 0;
}
dsu.Union(u, v);
return 1;
}
