#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
/*
Si les deux sommets sont connectes : on peut repondre comme on veut !
si chemin entre deux sommets mais on a pas demande arete entre les deux sommets -> impossible !!
A quelle condition mettre une arete entre u et v
Soit U et V les cc respectives de u, v. U != V
Si c'est la derniere arete entre U et V : on la met
Sinon, on la met pas
graphe connexe seulement apres la derniere arete !
*/
void initialize(int n);
int hasEdge(int u, int v);
int nb_sommets;
const int MAXSOMMETS = 1500;
int id[MAXSOMMETS];
int nb_questions[MAXSOMMETS][MAXSOMMETS];
int sz[MAXSOMMETS];
void initialize(int n)
{
nb_sommets = n;
for (int i(0); i < n; ++i)
{
id[i] = i;
sz[i] = 1;
}
}
int find(int u)
{
if (id[u] == u) return u;
return id[u] = find(id[u]);
}
void merge(int u, int v)
{
u = find(u), v = find(v);
if (sz[v] > sz[u]) swap(u, v);
for (int i(0); i < nb_sommets; ++i)
{
nb_questions[u][i] += nb_questions[v][i];
nb_questions[i][u] += nb_questions[i][v];
}
sz[u] += sz[v];
id[v] = u;
}
int hasEdge(int u, int v)
{
u = find(u);
v = find(v);
if (u == v)
return 1;
nb_questions[u][v]++;
nb_questions[v][u]++;
if (nb_questions[u][v] == (sz[u] * sz[v]))
{
merge(u,v);
return 1;
}
return 0;
}
