#include <bits/stdc++.h>
using namespace std;
// Máximo número de ciudades (ajusta este valor según las restricciones del problema)
static const int MAX_N = 1100;
int nCities;
// Estructura Union-Find (Disjoint Set) para mantener la conectividad
int parent[MAX_N];
int compSize[MAX_N];
// Para cada representante, mantenemos la lista de vértices (ciudades) en esa componente.
vector<int> compVertices[MAX_N];
// Matriz global para marcar que la pregunta (u,v) ya se hizo.
// Se utiliza la convención: para u < v, asked[u][v] == true indica que la consulta se realizó.
bool asked[MAX_N][MAX_N];
// Función find con compresión de caminos.
int findp(int a) {
if (parent[a] == a) return a;
return parent[a] = findp(parent[a]);
}
// Función para unir dos componentes (por tamaño).
void unionComponents(int a, int b) {
a = findp(a), b = findp(b);
if (a == b) return;
if (compSize[a] < compSize[b]) swap(a, b);
parent[b] = a;
compSize[a] += compSize[b];
// Fusionamos las listas de vértices.
for (int v : compVertices[b]) {
compVertices[a].push_back(v);
}
compVertices[b].clear();
}
// Dada dos componentes (identificadas por sus representantes),
// cuenta cuántos pares (x, y) con x en el primer componente y y en el segundo ya han sido consultados.
int countAskedBetween(int compA, int compB) {
int cnt = 0;
for (int u : compVertices[compA]) {
for (int v : compVertices[compB]) {
int a = min(u, v), b = max(u, v);
if (asked[a][b])
cnt++;
}
}
return cnt;
}
// Se llama al inicio de cada juego.
void initialize(int n) {
nCities = n;
// Inicializamos union-find y las listas de componentes.
for (int i = 0; i < n; i++) {
parent[i] = i;
compSize[i] = 1;
compVertices[i].clear();
compVertices[i].push_back(i);
}
// Inicializamos la matriz 'asked'. Sólo consideramos u < v.
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
asked[i][j] = false;
}
}
}
// Se invoca para cada pregunta: "¿existe un vuelo directo entre u y v?".
// Debe responder inmediatamente 1 (sí) o 0 (no).
int hasEdge(int u, int v) {
// Asegurarse de trabajar con u < v para la matriz 'asked'
if (u > v) swap(u, v);
// Registrar que se realizó la consulta (u, v).
asked[u][v] = true;
// Obtenemos los representantes (componentes) de u y v.
int ru = findp(u), rv = findp(v);
if (ru == rv) {
// Ya están conectados a través de respuestas "yes" anteriores, por lo que se responde "no".
return 0;
}
// Si pertenecen a componentes diferentes:
// El número total de pares entre las dos componentes es:
int total_possible = compSize[ru] * compSize[rv];
// Contamos cuántos de esos pares ya se han consultado.
int cnt = countAskedBetween(ru, rv);
// Si esta consulta es la ÚLTIMA posibilidad para conectar estas dos componentes
// (es decir, se han consultado total_possible - 1 de los pares), debemos contestar "yes"
// para no dejar revelada la conectividad (y así, Jian-Jia gana el juego).
if (cnt == total_possible - 1) {
unionComponents(ru, rv);
return 1;
}
else {
// En otro caso, contestamos "no".
return 0;
}
}
