// #include <game.h>
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1.5e3 + 5;
// graf_ustawionych -> graf krawedzi ustawionych i przyjmuje, ze mozliwe nie sa ustawione
// graf_ustawionych_i_mozliwych -> graf krawedzi ustawionych i przyjmuje, ze mozliwe tez sa ustawione
// Na poczatku ma wszystkie krawedzie sa nieustawione w grafie graf_ustawionych
// Na poczatku ma wszystkie krawedzie sa ustawione w grafie graf_ustawionych_i_mozliwych
// Na zapytanie o to czy {a, b} sa polaczone:
// * "YES" -> gdy {a, b} jest mostem w grafie_ustawionych_i_mozliwych
// * "NO" -> w przeciwnym przypadku
// Czyli innymi slowy odpowiadamy:
// * "YES" -> w przeciwnym przypadku
// * "NO" -> gdy {a, b} nalezy do cyklu w grafie_ustawionych_i_mozliwych
// Zeby rozwiazac to szybciej niz w O(MAX_N ^ 4) -> czyli w O(MAX_N ^ 2)
// Do znajdowania mostow posluzymy sie struktura F & U (DSU)
// I tablice ilosc_krawedzi_laczacych_wierzcholki[a][b], ktora bedzie mowila nam
// Ile krawedzi laczy find_set(a) z find_set(b)
// Krawedz {a, b} bedzie mostem w grafie_ustawionych_i_mozliwych,
// Jesli ilosc_krawedzi_laczacych_wierzcholki[a][b] == 1
// union_sets() zajmuje O(n), a find_set() zajmuje O(1)
// Poczatkowo ilosc_krawedzi_laczacych_wierzcholki[a][b] == 1 dla kazdej pary {a, b},
// Gdzie a != b
// Jesli odpowiadamy "NO", to zmniejszamy ilosc_krawedzi_laczacych_wierzcholki[a][b] i ilosc_krawedzi_laczacych_wierzcholki[b][a] o 1
// Jesli odpowiadamy "YES", to dla kazdego reprezentanta i,
// Robimy ilosc_krawedzi_laczacych_wierzcholki[a][i] += ilosc_krawedzi_laczacych_wierzcholki[b][i]
// Operacji union_set() moze byc maksymalnie (n - 1), wiec wszystkie operacje union_set() to O(MAX_N ^ 2)
// Update ilosc_krawedzi_laczacych_wierzcholki[a][b] w przypadku "YES", to O(n), ale operacji update wykonamy maksymalnie (n - 1), wiec wszystkie updaty to O(MAX_N ^ 2)
// Calkowita zlozonosc: O(MAX_N ^ 2)
int ilosc_krawedzi_laczacych_wierzcholki[MAX_N][MAX_N];
vector <int> rodzic(MAX_N);
int n;
int find_set(int v)
{
if(v == rodzic[v])
{
return v;
}
return rodzic[v] = find_set(rodzic[v]);
}
void make_set(int v)
{
rodzic[v] = v;
}
void union_sets(int a, int b)
{
a = find_set(a);
b = find_set(b);
for(int i = 0; i < n; i++)
{
int reprezentant_i = find_set(i);
if(reprezentant_i == i)
{
ilosc_krawedzi_laczacych_wierzcholki[a][i] += ilosc_krawedzi_laczacych_wierzcholki[b][i];
ilosc_krawedzi_laczacych_wierzcholki[i][a] = ilosc_krawedzi_laczacych_wierzcholki[a][i];
}
}
rodzic[b] = a;
}
bool check(int a, int b)
{
return find_set(a) == find_set(b);
}
void initialize(int ilosc_wierzcholkow)
{
n = ilosc_wierzcholkow;
for(int i = 0; i < n; i++)
{
make_set(i);
}
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
ilosc_krawedzi_laczacych_wierzcholki[i][j] = (i != j);
ilosc_krawedzi_laczacych_wierzcholki[j][i] = (i != j);
}
}
}
int hasEdge(int a, int b)
{
a = find_set(a);
b = find_set(b);
if(a == b)
{
return 0;
}
bool ok = (ilosc_krawedzi_laczacych_wierzcholki[a][b] == 1);
if(ok)
{
union_sets(a, b);
}
else
{
ilosc_krawedzi_laczacych_wierzcholki[a][b]--;
ilosc_krawedzi_laczacych_wierzcholki[b][a]--;
}
return ok;
}
