#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];
int edges[MAXN][MAXN];
EdgeKeeper welko;
DSU(){}
DSU(int n)
{
memset(this->edges, 0, sizeof(this->edges));
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(u>v) swap(u, v);
for(int x: nodes[v]) edges[u][Find(x)] += edges[v][Find(x)];
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);
if(u>v) swap(u, v);
edges[u][v]++;
}
int getEdges(int u, int v)
{
u = Find(u);
v = Find(v);
if(u>v) swap(u, v);
return edges[u][v];
}
};
DSU T;
void initialize(int n)
{
T = DSU(n);
}
int eval(int u, int v)
{
u = T.Find(u);
v = T.Find(v);
return T.nodes[u].size()*T.nodes[v].size() - T.getEdges(u, v);
}
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;
}
int found = eval(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
7
2 4
4 6
0 6
1 3
0 1
1 5
0 2
3 5
2 3
3 4
2 6
1 6
1 2
0 5
5 6
0 3
3 6
4 5
---------
2 5
0 4
1 4
*/
