#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int maxn = 1510, maxm = maxn * (maxn - 1) / 2;
int n, m;
pair<int,int> edge[maxm];
bool remain[maxm];
int par[maxn];
int findpar(int x)
{
return par[x] != -1 ? par[x] = findpar(par[x]) : x;
}
bool unite(int u, int v)
{
u = findpar(u);
v = findpar(v);
if (u != v) return par[u] = v, true;
return false;
}
bool check()
{
memset(par, -1, sizeof par);
int cnt = 0;
for (int i = 0; i < m; i++) {
if (remain[i]) cnt += unite(edge[i].first, edge[i].second);
}
return cnt == n - 1;
}
void initialize(int n)
{
::n = n;
m = n * (n - 1) / 2;
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
edge[cnt++] = {i, j};
}
}
for (int i = 0; i < m; i++) remain[i] = true;
}
int cnt = 0;
int hasEdge(int u, int v)
{
if (u > v) swap(u, v);
int id = lower_bound(edge, edge + m, make_pair(u, v)) - edge;
remain[id] = false;
if (check()) return 0;
remain[id] = true;
return 1;
}
