#include "game.h"
//#include "grader.cpp"
#include <map>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
using namespace std;
const int MAXN = 1505;
struct EdgeKeeper
{
int added[MAXN][MAXN];
EdgeKeeper()
{
memset(this->added, 0, sizeof(this->added));
}
void addEdge(int u, int v)
{
if(u>v) swap(u, v);
added[u][v]++;
}
void remEdge(int u, int v)
{
if(u>v) swap(u, v);
added[u][v]--;
}
int getEdges(int u, int v)
{
if(u>v) swap(u, v);
return added[u][v];
}
};
vector <pair <int, int>> allEdges;
struct DSU
{
int parent[MAXN];
vector <int> nodes[MAXN];
vector <int> presentEdges[MAXN];
EdgeKeeper welko;
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);
for(int x: nodes[v]) nodes[u].push_back(x);
for(int x: presentEdges[v]) welko.remEdge(Find(allEdges[x].first), Find(allEdges[x].second));
parent[v] = u;
for(int x: presentEdges[v]) welko.addEdge(Find(allEdges[x].first), Find(allEdges[x].second));
return true;
}
void addEdge(int u, int v, int eInd)
{
u = Find(u);
v = Find(v);
welko.addEdge(u, v);
presentEdges[u].push_back(eInd);
presentEdges[v].push_back(eInd);
}
};
DSU T;
bool asked[MAXN][MAXN];
void initialize(int n)
{
T = DSU(n);
memset(asked, false, sizeof(asked));
}
int eval(int u, int v)
{
u = T.Find(u);
v = T.Find(v);
vector <int> &v1 = T.nodes[u];
vector <int> &v2 = T.nodes[v];
return v1.size()*v2.size() - T.welko.getEdges(u, v);
}
int evalSlow(int u, int v)
{
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)
{
T.addEdge(u, v, allEdges.size());
allEdges.push_back({u, v});
if(T.Find(u)==T.Find(v))
{
return 1;
}
if(asked[u][v]==true) return 0;
asked[u][v] = true;
asked[v][u] = true;
int found = eval(u, v);
assert(eval(u, v)==evalSlow(u, v));
if(found==0)
{
T.Union(u, v);
return 1;
}
else
{
return 0;
}
}
/*
4
0 2
1 3
0 3
1 2
0 1
2 3
*/
