#include "game.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
/// imamo matricu setova koja nam odrzava grane koje su potrebne da se spoje komponente i i j
/// u matrici na mestu [i][j] je grana (i,j) (i<j)
/// imamo i niz koji odrzava u kojoj komponenti je koji cvor (racuna se tek kad nastane potpuna komponenta)
/// na pocetku svaki cvor je svoja komponenta
///imamo i niz koji odrzava velicine komponenti, po tome koliko ukupno ta komponenta ima "falecih" grana, na pocetku svi imaju n-1
/// sada imamo dva slucaja, jedan je kada grana spaja dve komponente i drugi kada ne
/// da bismo odredili koji je slucaj, nalazimo u kojoj komp je v, u kojoj je u, i brisemo granu (u,v) iz matrice [komp1][komp2] (komp1<komp2)
/// azuriramo velicinu (sz) i komponente 1 i komponente 2 (smanjujemo za 1)
/// ako je sada set na mestu [komp1][komp2] prazan, onda je prvi slucaj, ako nije onda je drugi
/// ako je drugi ne radimo nista, vracamo ne
/// ako je prvi
/// vidimo koja od komponenti komp1 i komp2 ima manji sz
/// neka to bude komp1
/// sada hocemo komp1 da prikljucimo za komp2
/// sz[komp2]+=sz[komp1]
/// sada prolazimo kroz sve komponente sem komp1 i komp2, neka je trenutna komp c, prebacujemo sve grane sa polja [komp1][c] na [komp2][c]
/// sada prolazimo kroz niz koji odrzava koji je cvor u kojoj komp, i sve gde pise komp1 prebacujemo u komp 2
/// vracamo da
int n;
vector<vector<set<pair<int,int>>>> m;
vector<int> col;
vector<int> sz;
void initialize(int N) {
n=N;
m.resize(n);
for(int i=0;i<n;i++)m[i].resize(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
m[i][j].insert(make_pair(i,j));
}
}
col.assign(n,0);
for(int i=0;i<n;i++)col[i]=i;
sz.assign(n,n-1);
}
int hasEdge(int u, int v) {
if(u>v)swap(u,v);
int komp1=col[u];
int komp2=col[v];
if(komp1>komp2)swap(komp1,komp2);
m[komp1][komp2].erase(make_pair(u,v));
sz[komp1]--;
sz[komp2]--;
if(m[komp1][komp2].size()!=0)return 0;
if(sz[komp1]>sz[komp2])swap(komp1,komp2);
sz[komp2]+=sz[komp1];
for(int c=0;c<n;c++){
if(c==komp1 || c==komp2)continue;
for(auto a:m[min(c,komp1)][max(c,komp1)]){
//m[min(c,komp2)][max(c,komp2)].insert(a);
//m[min(c,komp1)][max(c,komp1)].erase(a);
continue;
}
}
for(int i=0;i<n;i++){
if(col[i]==komp1)col[i]=komp2;
}
return 1;
}
