#include "game.h"
#include <iostream>
using namespace std;
const int nmax=1505;
int ad[nmax][nmax],grad[nmax][nmax];
bool asked[nmax][nmax];
int tt[nmax],rg[nmax];
int n,i;
void initialize(int N) {
n=N;
for(i=0;i<n;i++)
tt[i]=i,rg[i]=1;
}
int finds(int x)
{
while(x!=tt[x])
x=tt[x];
return x;
}
void unite(int A,int B)
{
if(rg[A]<rg[B]) swap(A,B);
tt[B]=A;rg[A]+=rg[B];
for(int i=0;i<n;i++)
{
grad[A][i]+=grad[B][i];
grad[i][A]+=grad[i][B];
}
}
int hasEdge(int u, int v) {
if(asked[u][v]) return ad[u][v];
asked[u][v]=asked[v][u]=1;
grad[finds(u)][finds(v)]++;
grad[finds(v)][finds(u)]++;
if(grad[finds(u)][finds(v)]==rg[finds(u)]*rg[finds(v)])
{
unite(finds(u),finds(v));
ad[u][v]=ad[v][u]=1;
}
return ad[u][v];
}
