#include <bits/stdc++.h>
#ifndef _DEBUG
#include "game.h"
#endif
using namespace std;
vector<int> parent; // logn union find
vector<int> remain;
int find(int a)
{
return parent[a] = ((parent[a] == a) ? a : find(parent[a]));
}
void initialize(int n)
{
parent = remain = vector<int>(n);
for (int i = 0; i < n; i++)
{
parent[i] = i;
remain[i] = n - 1;
}
}
// if the remaining edge is queried, it exists, otherwise it doesn't. This guarantees there are at least 2 groups left until the end
int hasEdge(int u, int v)
{
u = find(u);
v = find(v);
remain[u]--;
remain[v]--;
if (remain[u] == 0 || remain[v] == 0)
{
parent[u] = u;
remain[v] += remain[u];
return 1;
}
return 0;
}
