En el laboratorio del profesor JOI se investigan $N$ tipos de minerales. Hay $2$ láminas de cada tipo de mineral. En total hay $2N$ láminas, numeradas del $1$ al $2N$.

Un día, el ayudante Bitaro dejó caer la caja que contenía las $2N$ láminas y ahora no sabe qué láminas son del mismo tipo de mineral.

El laboratorio dispone de un aparato que, al introducir algunas láminas, puede contar cuántos tipos de minerales hay en él midiendo la longitud de onda que absorbe cada mineral. Bitaro quiere determinar las $N$ parejas del mismo tipo de mineral entre las $2N$ láminas. Al principio no hay ninguna lámina dentro del aparato. Bitaro puede realizar las siguientes operaciones:

• Introducir una lámina en el aparato y conocer cuántos tipos de minerales hay en él.
• Extraer una lámina del aparato y conocer cuántos tipos de minerales hay en él.

Para que el profesor JOI no descubra que Bitaro ha causado problemas, Bitaro puede realizar estas operaciones como máximo $1\,000\,000$ de veces en total.

Escribe un programa que, dado el número de tipos de minerales, utilice el aparato para determinar todas las parejas del mismo tipo de mineral.

Detalles de implementación

Debes enviar un archivo.

El archivo debe llamarse minerals.cpp. Debe implementar la siguiente función. El programa debe incluir minerals.h.

• void Solve(int N)

Esta función se llama exactamente una vez por cada caso de prueba.

• El parámetro N representa $N$, el número de tipos de minerales.

Tu programa puede llamar a las siguientes funciones.

• int Query(int x)

Para el índice de lámina que especifiques, esta función extrae la lámina del aparato si ya está dentro, o la introduce en caso contrario. Después devuelve el número de tipos de minerales que hay en el aparato.

• Mediante el parámetro x especificas el índice $x$ de la lámina. Debe cumplirse $1 \le x \le 2N$. De lo contrario, tu programa recibe el veredicto de respuesta incorrecta Wrong Answer [1].

• La función Query no debe llamarse más de $1\,000\,000$ de veces. De lo contrario, tu programa recibe el veredicto de respuesta incorrecta Wrong Answer [2].

• void Answer(int a, int b)

Con esta función indicas las parejas del mismo mineral.

• Los parámetros a y b indican que la lámina $a$ y la lámina $b$ son del mismo tipo de mineral. Deben cumplirse $1 \le a \le 2N$ y $1 \le b \le 2N$. De lo contrario, tu programa recibe el veredicto de respuesta incorrecta Wrong Answer [3]. Si un mismo valor aparece más de una vez entre todos los valores de a y b, tu programa recibe el veredicto de respuesta incorrecta Wrong Answer [4]. Si se especifican láminas de distintos tipos de minerales, tu programa recibe el veredicto de respuesta incorrecta Wrong Answer [5].

La función Answer debe llamarse exactamente $N$ veces. Si al terminar la ejecución de la función Solve el número de llamadas a Answer no es $N$, tu programa recibe el veredicto de respuesta incorrecta Wrong Answer [6].

Avisos importantes

• Tu programa puede implementar otras funciones para uso interno o utilizar variables globales.
• Tu programa no debe utilizar la entrada estándar ni la salida estándar. Tampoco debe comunicarse con otros archivos por ningún medio. Sin embargo, puede escribir información de depuración en la salida de error estándar.

Compilación y ejecución de prueba

Puedes descargar de la página web del concurso un archivo comprimido que contiene el evaluador de ejemplo para probar tu programa. También contiene un archivo fuente de ejemplo de tu programa.

El evaluador de ejemplo es el archivo grader.cpp. Para probar tu programa, coloca grader.cpp, minerals.cpp y minerals.h en el mismo directorio y ejecuta el siguiente comando para compilar tus programas.

g++ -std=gnu++14 -O2 -o grader grader.cpp minerals.cpp

Si la compilación termina correctamente, se genera el archivo ejecutable grader.

Ten en cuenta que el evaluador real es distinto del evaluador de ejemplo. El evaluador de ejemplo se ejecuta como un único proceso, que lee los datos de la entrada estándar y escribe los resultados en la salida estándar.

Entrada del evaluador de ejemplo

El evaluador de ejemplo lee los siguientes datos de la entrada estándar.

$$ \begin{array}{l} N\\ X_1\ Y_1\\ \vdots\\ X_N\ Y_N \end{array} $$

$X_i$ e $Y_i$ ($1 \le i \le N$) indican que las láminas $X_i$ e $Y_i$ son del mismo tipo de mineral.

Salida del evaluador de ejemplo

Cuando el programa termina correctamente, el evaluador de ejemplo escribe la siguiente información en la salida estándar (las comillas se muestran para mayor claridad).

• Si tu programa se considera correcto, escribe el número de llamadas a la función Query, como en «Accepted: 100».
• Si tu programa recibe un veredicto de respuesta incorrecta, escribe su tipo, como en «Wrong Answer [1]».

Si tu programa incurre en varios tipos de respuesta incorrecta, el evaluador de ejemplo solo informa de uno de ellos.

Restricciones

Consulta la sección «Entrada del evaluador de ejemplo» para ver la definición de $X_i$ e $Y_i$.

• $1 \le N \le 43\,000$.
• $1 \le X_i \le 2N$ ($1 \le i \le N$).
• $1 \le Y_i \le 2N$ ($1 \le i \le N$).
• $X_i \ne X_j$ ($1 \le i < j \le N$).
• $Y_i \ne Y_j$ ($1 \le i < j \le N$).
• $X_i \ne Y_j$ ($1 \le i \le N$, $1 \le j \le N$).

Subtareas

1. (6 puntos) $N \le 100$.
2. (25 puntos) $N \le 15\,000$, $1 \le X_i \le N$, $N+1 \le Y_i \le 2N$ ($1 \le i \le N$).
3. (9 puntos) $N \le 15\,000$.
4. (30 puntos) $N \le 38\,000$.
5. (5 puntos) $N \le 39\,000$.
6. (5 puntos) $N \le 40\,000$.
7. (5 puntos) $N \le 41\,000$.
8. (5 puntos) $N \le 42\,000$.
9. (10 puntos) Sin restricciones adicionales.

Ejemplos

Aquí se muestra una entrada de ejemplo para el evaluador de ejemplo y las llamadas a funciones correspondientes.

Entrada 1

4
1 5
2 6
3 4
7 8

Llamadas de ejemplo