#include "game.h"
#include <iostream>
using namespace std;
int mtx[1501][1501]={};
int ask[1501][1501]={};
int pr[1501]={},sz[1501]={},n;
int fn(int x)
{
return pr[x] = (pr[x] - x)?fn(pr[x]):x;
}
void jn(int a,int b)
{
a = fn(a), b = fn(b);
if (a != b)
{
pr[b] = a;
sz[a] += sz[b];
for (int i = 0; i < n; i++)
{
ask[a][i] += ask[b][i];
ask[i][a] += ask[i][b];
}
}
}
void initialize(int n)
{
::n = n;
for (int i=0;i<n;i++)
{
for (int j = 0;j<n;j++)
{
mtx[i][j] = -1;
}
pr[i] = i;
sz[i] = 1;
}
}
int hasEdge(int u, int v)
{
if (mtx[u][v]==-1)
{
int tu = u,tv = v;
u = fn(u),v = fn(v);
ask[u][v]++;ask[v][u]++;
if (ask[u][v] == sz[u] * sz[v]) {jn(u,v);mtx[tu][tv] = 1;mtx[tv][tu] = 1;}
else {mtx[tu][tv] = 0;mtx[tv][tu] = 0;}
u = tu, v = tv;
}
return mtx[u][v];
}
