// #include <game.h>
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1.5e3 + 5;
bool visited[MAX_N];
// 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
// Czyli tworzymy graf z grafu_ustawionych_i_mozliwych bez krawedzi {a, b}, nastepnie robimy DFS i sprawdzamy czy jest sciezka z a do b
// DFS -> O(MAX_N ^ 2)
// Wszystkich mozliwych krawedzi (ilosci zapytan) jest O(MAX_N ^ 2)
// Calkowita zlozonosc: O(MAX_N ^ 2 * MAX_N ^ 2) == O(MAX_N ^ 4)
int graf_ustawionych_i_mozliwych[MAX_N][MAX_N];
int n;
void initialize(int ilosc_wierzcholkow)
{
n = ilosc_wierzcholkow;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
graf_ustawionych_i_mozliwych[i][j] = (i != j);
graf_ustawionych_i_mozliwych[j][i] = (i != j);
}
}
}
void wyczysc()
{
for(int i = 0; i < n; i++)
{
visited[i] = false;
}
}
void DFS(int v)
{
visited[v] = true;
for(int i = 0; i < n; i++)
{
if(!visited[i] && graf_ustawionych_i_mozliwych[v][i])
{
DFS(i);
}
}
}
int hasEdge(int a, int b)
{
// usuwamy krawedz {a, b}
graf_ustawionych_i_mozliwych[a][b] = 0;
graf_ustawionych_i_mozliwych[b][a] = 0;
DFS(a);
// true -> {a, b} nie jest mostem w grafie_ustawionych_i_mozliwych
// false -> {a, b} nalezy do cyklu w grafie_ustawionych_i_mozliwych
bool ok = !visited[b];
if(ok)
{
graf_ustawionych_i_mozliwych[a][b] = 1;
graf_ustawionych_i_mozliwych[b][a] = 1;
}
wyczysc();
return ok;
}
