#include <bits/stdc++.h>
#include "game.h"
using namespace std;
constexpr static int MXSIZE = 1500;
int m[MXSIZE][MXSIZE];
struct Node
{
int head;
int tail;
int size;
int nxt;
Node(int index) : head(index), tail(index), size(1), nxt(-1) {}
Node() : Node(-1) {}
};
Node node[MXSIZE];
int n;
void initialize(int nn)
{
n = nn;
for (int i = 0; i < n; i++)
node[i] = Node(i);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
m[i][j] = i != j;
}
void merge(int a, int b);
int hasEdge(int u, int v)
{
u = node[u].head, v = node[v].head;
if (m[u][v] == 1)
{
merge(u, v);
return 1;
}
m[u][v]--;
m[v][u]--;
return 0;
}
void merge(int a, int b)
{
if (node[b].size > node[a].size) swap(a, b);
for (int i = 0; i < n; i++)
{
m[a][i] += m[b][i];
m[i][a] += m[i][b];
}
node[a].size += node[b].size;
node[node[a].tail].nxt = b;
node[a].tail = node[b].tail;
for (; b != -1; b = node[b].nxt)
node[b].head = a;
}
