#include "game.h"
//#include "grader.cpp"
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 1505;
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;
}
};
DSU T;
bool asked[MAXN][MAXN];
void initialize(int n)
{
T = DSU(n);
memset(asked, false, sizeof(asked));
}
int hasEdge(int u, int v)
{
if(T.Find(u)==T.Find(v))
{
return 1;
}
asked[u][v] = true;
asked[v][u] = true;
vector <int> &v1 = T.nodes[T.Find(u)];
vector <int> &v2 = T.nodes[T.Find(v)];
/*
cout << "v1:";
for(int x: v1) cout << " " << x;
cout << '\n';
cout << "v2:";
for(int x: v2) cout << " " << x;
cout << '\n';
*/
bool found = 0;
for(int x: v1)
{
for(int y: v2)
{
if(asked[x][y]==false)
{
found = 1;
break;
}
}
if(found==1) break;
}
if(found==false) T.Union(u, v);
return found^1;
}
