#include "game.h"
//#include "grader.cpp"
#include <map>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 1505;
struct Profile
{
int root1, root2;
int sz1, sz2;
Profile(){}
Profile(int root1, int root2, int sz1, int sz2)
{
this->root1 = root1;
this->root2 = root2;
this->sz1 = sz1;
this->sz2 = sz2;
}
};
bool operator <(Profile A, Profile B)
{
if(A.root1!=B.root1) return A.root1<B.root1;
if(A.root2!=B.root2) return A.root2<B.root2;
if(A.sz1!=B.sz1) return A.sz1<B.sz1;
return A.sz2<B.sz2;
}
struct DSU
{
int parent[MAXN];
vector <int> nodes[MAXN];
DSU(){}
DSU(int n)
{
for(int i = 0;i<n;i++)
{
this->parent[i] = i;
this->nodes[i] = {i};
}
}
int Find(int x)
{
if(parent[x]==x) return x;
parent[x] = Find(parent[x]);
return parent[x];
}
bool Union(int u, int v)
{
u = Find(u);
v = Find(v);
if(u==v) return false;
if(nodes[u].size()<nodes[v].size()) swap(u, v);
parent[v] = u;
for(int x: nodes[v]) nodes[u].push_back(x);
return true;
}
};
Profile makeProfile(int u, int v, DSU &T)
{
u = T.Find(u);
v = T.Find(v);
Profile out;
out.root1 = u;
out.root2 = v;
out.sz1 = T.nodes[u].size();
out.sz2 = T.nodes[v].size();
return out;
}
DSU T;
bool asked[MAXN][MAXN];
map <Profile, int> memo;
void initialize(int n)
{
T = DSU(n);
memset(asked, false, sizeof(asked));
}
int evalProfile(Profile p)
{
int u = p.root1, v = p.root2;
vector <int> &v1 = T.nodes[T.Find(u)];
vector <int> &v2 = T.nodes[T.Find(v)];
int found = 0;
for(int x: v1)
{
for(int y: v2)
{
if(asked[x][y]==false)
{
found++;
}
}
}
return found;
}
int hasEdge(int u, int v)
{
if(T.Find(u)==T.Find(v))
{
return 1;
}
if(asked[u][v]==true) return 0;
Profile p = makeProfile(u, v, T);
if(memo.count(p)==false) memo[p] = evalProfile(p);
asked[u][v] = true;
asked[v][u] = true;
memo[p]--;
if(memo[p]==0)
{
T.Union(u, v);
return 1;
}
else
{
return 0;
}
}
