Este es un problema interactivo.

En esta fiesta llena de aromas dulces, la preparación del postre final, la leche de doble piel, se enfrenta a una última dificultad.

Como el postre más popular de la tienda, una leche de doble piel perfecta requiere combinar a la perfección el pastel de la capa superior con el pudín de la capa inferior. En este mágico reino de las pulgas, las energías de los dos componentes del postre se entrelazan y se ocultan en una compleja red de ciudades.

Los dos maestros pasteleros veteranos de la tienda, dacake8 y dapudding8, han decidido ponerte a prueba. Han escondido el pastel y el pudín, respectivamente, en las carreteras entre las ciudades. ¡Solo consultándoles y encontrando con precisión una ciudad conectada a la tienda principal donde te encuentras (la ciudad $1$) por una carretera que contenga un postre podrás completar con éxito esta leche de doble piel que cierra la fiesta!

Hay $n$ ciudades, y existe una carretera entre cada par de ciudades. Hay $n-1$ porciones de pastel; la porción $i$ está en la carretera que conecta las ciudades $u_{i,1}$ y $v_{i,1}$. Hay $n-1$ porciones de pudín; la porción $i$ está en la carretera que conecta las ciudades $u_{i,2}$ y $v_{i,2}$. Las carreteras que contienen pastel y las que contienen pudín forman, respectivamente, dos árboles.

Al principio no conoces las ubicaciones concretas del pastel ni del pudín. Puedes hacer como máximo $\min(1000,\frac{n\times(n-1)}{2})$ consultas a dacake8 y dapudding8:

• Consultas a dacake8 y dapudding8 sobre las ciudades $u$ y $v$; inicialmente, el multiconjunto $S$ está vacío.

  • dacake8 parte de la ciudad $u$, sigue el camino que contiene pastel hasta llegar a la ciudad $v$ y añade a $S$ los números de las ciudades por las que pasa.
  • dapudding8 parte de la ciudad $u$, sigue el camino que contiene pudín hasta llegar a la ciudad $v$ y añade a $S$ los números de las ciudades por las que pasa.
• La biblioteca de interacción devuelve el multiconjunto $S$.

Te encuentras en la ciudad $1$. Una vez terminadas las consultas, debes indicar una ciudad $u$ tal que la carretera que conecta las ciudades $1$ y $u$ contenga algún tipo de postre.

dacake8 y dapudding8 no quieren ponértelo difícil y garantizan que las ubicaciones del pastel y del pudín se fijan antes de las consultas. Es decir, la biblioteca de interacción no es adaptativa.

Detalles de implementación

No necesitas ni debes implementar la función main.

Debes incluir el archivo de cabecera milk.h en el archivo fuente milk.cpp e implementar las siguientes dos funciones:

void init(int c, int t);

• $c,t$ representan, respectivamente, el número de la subtarea y la cantidad de casos de prueba. $id=0$ indica que el test es un ejemplo.
• Para cada test, la biblioteca de interacción llama a esta función exactamente una vez al iniciar la ejecución del programa.

int find(int c, int n);

• $c,n$ representan, respectivamente, el número de la subtarea y la cantidad de ciudades.
• Esta función debe devolver un entero positivo $u$, que indica una ciudad $u$ tal que la carretera que conecta las ciudades $1$ y $u$ contenga algún tipo de postre.
• Para cada test, la biblioteca de interacción llama a esta función exactamente $t$ veces.

Puedes realizar una consulta llamando a la siguiente función:

std::vector<int>query(int u, int v);

• $u,v$ indican las dos ciudades $u$ y $v$.
• Debes garantizar que $1\le u,v\le n$ y $u\ne v$.
• Esta función devuelve el multiconjunto $S$, cuyo significado se describe en el enunciado.
• Si el tamaño del multiconjunto $S$ es $m$, se cumple $1\le S_i\le n$ y $S_0\le S_1\le \ldots \le S_{m-1}$.
• Debes garantizar que, cada vez que la biblioteca de interacción llama a find, el número de llamadas a esta función no supere $1000$.

Cómo probar el programa

Coloca milk.cpp, milk.h y el archivo grader.cpp incluido en los adjuntos en el mismo directorio y compila usando C++17:

g++ grader.cpp milk.cpp -o milk -O2 -std=c++17
./milk < ex_milk1.in

Para el ejecutable milk obtenido al compilar:

La primera línea de la entrada de la biblioteca de interacción contiene dos enteros no negativos $id,t$, que representan, respectivamente, el número del test y la cantidad de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero positivo $n$, que representa la cantidad de ciudades. Cada una de las líneas $2\sim n$ contiene dos enteros positivos $u_{i,1}$, $v_{i,1}$; cada una de las siguientes $n-1$ líneas contiene otros dos enteros positivos $u_{i,2}$, $v_{i,2}$.

Si las respuestas de las $t$ llamadas a find son todas correctas, la biblioteca de interacción imprime Correct! en la primera línea y Max queries used: Q en la segunda, donde $Q$ representa el máximo número de llamadas a query entre todos los casos de prueba. Si al menos una respuesta es incorrecta, imprime Wrong answer.; si una llamada a la interfaz no es válida, también indica el motivo del error en la salida de error estándar.

Ejemplos

Entrada 1

0 3
5
1 5
2 5
2 4
3 5
1 2
1 4
3 4
4 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 7
2 4
3 6
4 6
5 7
5 8
6 8
2
1 2
1 2

Salida 1

Correct!
Max queries used: 28

Nota

Ten en cuenta que los datos de prueba finales no incluyen el ejemplo.

En los diagramas, una arista roja indica que hay una porción de pastel en la carretera entre las dos ciudades, y una arista azul indica que hay una porción de pudín.

Para el primer caso de prueba, los árboles formados por las carreteras con pastel y con pudín tienen la siguiente forma:

Para el segundo caso de prueba, los árboles formados por las carreteras con pastel y con pudín tienen la siguiente forma:

Para el tercer caso de prueba, una misma carretera también puede contener tanto pastel como pudín.

Restricciones

Propiedad especial $\text{A}$: las ubicaciones del pastel y del pudín se generan de forma completamente aleatoria.

Propiedad especial $\text{B}$: se garantiza que existe una única respuesta posible.

Propiedad especial $\text{C}$: si ambos árboles formados por las carreteras con pastel y con pudín se enraízan en la ciudad $1$, y desde cada ciudad se trazan aristas dirigidas hacia su padre en cada uno de los dos árboles, el grafo dirigido resultante es un DAG.

Propiedad especial $\text{D}$: si ambos árboles formados por las carreteras con pastel y con pudín se enraízan en la ciudad $2$, y desde cada ciudad se trazan aristas dirigidas hacia su padre en cada uno de los dos árboles, el grafo dirigido resultante es un DAG.

Propiedad especial $\text{E}$: las ubicaciones del pudín se generan de forma completamente aleatoria. Las ubicaciones del pastel no dependen de las ubicaciones del pudín.

Propiedad especial $\text{F}$: los dos árboles formados por las carreteras con pastel y con pudín son dos cadenas, ambas con la ciudad $1$ como extremo inicial.

En este problema, generar un árbol aleatoriamente significa usar una secuencia de Prufer aleatoria.

Subtareas

Si la respuesta devuelta por find es incorrecta o los parámetros de query no son válidos, el multiplicador de puntuación de ese test es $0$.

Para las subtareas $1,2,3$, si el número de consultas supera $\frac{n\times(n-1)}{2}$, el multiplicador de puntuación de ese test es $0$; en caso contrario, es $1$.

Para las subtareas $4\sim 15$, sea $Q$ el máximo número de llamadas a query entre todos los casos de prueba. El multiplicador de puntuación $f(Q)$ se calcula según la siguiente tabla:

La puntuación final de un test es el producto de su valor en puntos y el multiplicador de puntuación, conservando tres cifras decimales según las reglas de UOJ para puntuaciones reales.

Límite de tiempo: $20\ \mathrm{s}$.

Límite de memoria: $512\ \mathrm{MiB}$.