Hay $N$ islas donde viven castores, numeradas de $0$ a $N-1$. Estas islas están conectadas por $N-1$ puentes bidireccionales. Es posible viajar entre cualesquiera islas utilizando algunos puentes. Cada isla tiene como máximo 18 puentes conectados directamente a ella. En cada isla vive un castor.

A veces, algunos castores se reúnen en una isla para celebrar una reunión. Cuando se reúnen exactamente tres castores, se congregan en la siguiente isla:

La isla que minimiza el número total de puentes que los tres castores atraviesan para reunirse (existe una única isla así).

Observa que esta isla puede coincidir con una de las islas donde vive uno de los tres castores.

Te interesa saber cómo están conectadas por puentes las $N$ islas. No puedes ir a comprobar las islas directamente, por lo que darás algunas instrucciones a los castores. Una instrucción es la siguiente:

• Especificas tres islas $u$, $v$ y $w$ ($0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$, $v\ne w$), y haces que los castores que viven en las islas $u$, $v$ y $w$ celebren una reunión.
• A continuación, puedes ver la isla donde se reúnen los tres castores.

Quieres determinar cómo están conectadas las islas utilizando pocas instrucciones.

Escribe un programa que, dado el número de islas y comunicándose con los castores, determine cómo están conectadas las islas.

Detalles de implementación

Debes entregar un archivo.

El archivo se llama meetings.cpp. Debe implementar la siguiente función. El programa debe incluir meetings.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 islas.

Tu programa puede llamar a las siguientes funciones.

• int Query(int u, int v, int w)

Esta función devuelve, para los índices de las tres islas que especifiques, el índice de la isla donde los castores que viven allí se reúnen.

• Especificas los índices $u$, $v$ y $w$ de las tres islas mediante los parámetros u, v y w, respectivamente. Deben satisfacer $0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$ y $v\ne w$. De lo contrario, tu programa se considera Wrong Answer [1].

• La función Query no debe llamarse más de $100\,000$ veces. De lo contrario, tu programa se considera Wrong Answer [2].

• void Bridge(int u, int v)

Mediante esta función, indicas cómo están conectadas por puentes las islas.

• Los parámetros u y v indican que las islas $u$ y $v$ están conectadas directamente por un puente.
• Si no se cumple $0\le u<v\le N-1$, tu programa se considera Wrong Answer [3].
• Si las islas $u$ y $v$ no están conectadas directamente por un puente, tu programa se considera Wrong Answer [4].
• Si se llama a la función Bridge varias veces con los mismos parámetros u y v, tu programa se considera Wrong Answer [5].
• Como hay $N-1$ puentes, la función Bridge debe llamarse exactamente $N-1$ veces. Si el número de llamadas a la función Bridge no es $N-1$ al terminar la ejecución de la función Solve, tu programa se considera 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. Tu programa no debe comunicarse con otros archivos mediante ningún método. 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 desde la página web del concurso un archivo comprimido que contiene el evaluador de ejemplo para probar tu programa. El archivo comprimido 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, meetings.cpp y meetings.h en el mismo directorio y ejecuta el siguiente comando para compilar tus programas.

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

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

Observa que el evaluador real es diferente del evaluador de ejemplo. El evaluador de ejemplo se ejecutará como un único proceso, que leerá los datos de entrada de la entrada estándar y escribirá 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}{ll} N & \\ A_0 & B_0 \\ \vdots & \\ A_{N-2} & B_{N-2} \end{array} $$

$A_i$ y $B_i$ ($0\le i\le N-2$) indican que las islas $A_i$ y $B_i$ están conectadas directamente por un puente.

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 utilizan 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 se considera Wrong Answer, escribe su tipo, como en «Wrong Answer [1]».

Si tu programa se considera de varios tipos de Wrong Answer, el evaluador de ejemplo solo informa de uno de ellos.

Restricciones

Consulta la sección «Entrada del evaluador de ejemplo» para la definición de $A_i$ y $B_i$.

• $3\le N\le 2\,000$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le N-2$).
• Es posible viajar entre cualesquiera islas utilizando algunos puentes.
• Cada isla tiene como máximo 18 puentes conectados directamente a ella.

Subtareas

1. (7 puntos) $N\le 7$.
2. (10 puntos) $N\le 50$.
3. (12 puntos) $N\le 300$.

4. (71 puntos) Sin restricciones adicionales.

5. En las subtareas 1, 2 y 3, si tu programa es correcto para todos los casos de prueba de una subtarea, obtienes la puntuación completa.

6. En la subtarea 4, si tu programa es correcto para todos los casos de prueba, tu puntuación será la siguiente, donde $X$ es el máximo número de llamadas a la función Query para un caso de prueba.
   • 49 puntos si $40\,000<X\le 100\,000$, y
   • 71 puntos si $X\le 40\,000$.

Ejemplos

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

Entrada 1

5
0 1
0 2
1 3
1 4

Llamadas de ejemplo