#include <bits/stdc++.h>
#include "game.h"
using namespace std;
struct Node
{
int head;
int tail;
int size;
int rcount;
int nxt;
Node(int index) : head(index), tail(index), size(1), rcount(0), nxt(-1) {}
Node() : Node(-1) {}
};
constexpr static int MXSIZE = 1500;
int ans[MXSIZE][MXSIZE];
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++)
ans[i][j] = -1;
}
bool needs_friends(int i)
{
return (n-node[i].size) * node[i].size == node[i].rcount + 1;
}
void merge(int a, int b)
{
if (node[a].size < node[b].size) swap(a, b);
node[a].size += node[b].size;
node[a].rcount += node[b].rcount;
node[node[a].tail].nxt = b;
node[a].tail = node[b].tail;
for (int i = b; i != -1; i = node[i].nxt)
{
for (int j = a; j != -1; j = node[j].nxt)
if (ans[min(i,j)][max(i,j)] == 0)
node[a].rcount--;
node[i].head = a;
}
}
int hasEdge(int u, int v)
{
if (u > v) swap(u, v);
if ((ans[u][v] == -1) && (node[u].head != node[v].head) && (needs_friends(node[u].head) || needs_friends(node[v].head)))
{
merge(node[u].head, node[v].head);
ans[u][v] = 1;
}
else if (ans[u][v] == -1)
{
if (node[u].head != node[v].head)
{
node[node[u].head].rcount++;
node[node[v].head].rcount++;
}
ans[u][v] = 0;
}
return ans[u][v];
}
