#include "game.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
const int N = 1500;
int s[N][N], d[N];
vector<int> lst[N];
int n;
void initialize(int m) {
n = m;
for(int i = 0; i < n; i++) {
d[i] = i;
lst[i].clear();
lst[i].pb(i);
for(int j = 0; j < n; j++) {
if(i != j) s[i][j] = 1;
}
}
}
bool merge(int u, int v) {
u = d[u], v = d[v];
if(u == v) return false;
if(lst[u].size() < lst[v].size()) swap(u, v);
if(s[u][v] > 1) {
s[u][v]--;
s[v][u]--;
return false;
} else {
for(auto &x : lst[v]) {
d[x] = u;
lst[u].pb(x);
}
for(int x = 0; x < n; x++) {
if(x == d[x] && x != u && x != v) {
int t = s[u][x] + s[v][x];
s[u][x] = s[x][u] = t;
}
}
return true;
}
}
int hasEdge(int u, int v) {
return merge(u, v);
}
