En muchas partes de Rusia nieva durante el invierno. En Rusia hay $N$ ciudades, numeradas de $0$ a $N-1$, y $N-1$ carreteras, numeradas de $0$ a $N-2$. La carretera $i$ ($0 \le i \le N-2$) conecta en ambos sentidos dos ciudades distintas $A_i$, $B_i$ ($0 \le A_i < B_i \le N-1$). Se puede viajar entre cualesquiera dos ciudades distintas de Rusia pasando por algunas carreteras.

El estado de las nevadas de cada carretera cambia de un día a otro. En cualquier fecha, en cada carretera está nevando o no está nevando. Este estado no cambia durante un mismo día.

Anya y Boris trabajan en el departamento de transporte de Rusia. Anya pertenece a la sección de gestión de información vial, y Boris a la sección que responde las preguntas de los ciudadanos. Los ciudadanos preguntan cuál es el número mínimo de carreteras en las que está nevando que deben atravesar para viajar desde la ciudad $0$, la capital de Rusia, hasta otra ciudad. Normalmente, después de recibir una pregunta, Boris se comunica con Anya y responde al ciudadano.

Ahora se celebrará en Rusia un campeonato mundial de programación durante $Q$ días. Se espera que durante el campeonato las líneas de comunicación estén congestionadas y sea difícil que Anya y Boris se comuniquen directamente. Por ello, han decidido comunicarse de la siguiente manera.

• Al comienzo de cada día, Anya recibe la información sobre las nevadas de ese día y envía datos a un servidor intermediario.
• Cuando Boris recibe una pregunta de un ciudadano, la responde comunicándose con el servidor intermediario.

Sin embargo, su comunicación está sujeta a las siguientes restricciones.

• La capacidad del servidor intermediario es de $L=1\,000$ bits. Anya puede guardar en él como máximo $L$ bits de información.
• Al comienzo de cada día, todos los datos almacenados en el servidor se inicializan a $0$.
• En cada comunicación con el servidor, Boris puede leer un bit que especifique.
• Para responder una pregunta, Boris puede comunicarse con el servidor como máximo $20$ veces por pregunta.

Tú conoces al director del departamento de transporte y te han encargado diseñar la estrategia de Anya y Boris.

Tarea

Escribe programas que implementen las estrategias de Anya y Boris para responder correctamente las preguntas de los ciudadanos.

Detalles de implementación

Debes entregar dos archivos escritos en el mismo lenguaje de programación.

El primero debe llamarse Anya.c o Anya.cpp. Implementa la estrategia de Anya y debe implementar las dos rutinas siguientes. El programa debe incluir Anyalib.h.

void InitAnya(int N, int A[], int B[])

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

• El parámetro N representa el número de ciudades.
• Los parámetros A[] y B[] son secuencias de longitud $N-1$ que representan las conexiones de las carreteras. Los elementos A[i] y B[i] ($0 \le i \le N-2$) son enteros que indican que la carretera $i$ conecta en ambos sentidos las ciudades A[i] y B[i], y satisfacen $0 \le A[i] < B[i] \le N-1$.

void Anya(int C[])

Esta función se llama $Q$ veces después de llamar a InitAnya. Corresponde a la decisión de Anya sobre la secuencia de bits que guardará en el servidor después de actualizarse la información de nevadas al comienzo del día.

• El parámetro C[] es una secuencia de longitud $N-1$ que representa la información de nevadas. El elemento C[i] ($0 \le i \le N-2$) es un entero $0$ o $1$ que indica el estado de la carretera $i$: si C[i] = 1, está nevando en ella; si C[i] = 0, no está nevando.

Dentro de Anya se puede llamar a la siguiente función.

void Save(int place, int bit)

Esta función representa la operación de Anya de guardar un bit en el servidor.

• El parámetro place representa la posición donde se escribe el bit. Debe ser un entero entre $0$ y $L-1$, inclusive. Si se llama con un valor fuera de este intervalo, se obtiene Wrong Answer [1]. Además, en cada llamada a Anya no se puede llamar a esta función dos o más veces con el mismo parámetro place. Si se llama dos veces con el mismo parámetro, se obtiene Wrong Answer [2].
• El parámetro bit representa el bit que se escribe y debe ser el entero $0$ o $1$. Si se llama con otro valor, se obtiene Wrong Answer [3].

Después de llamar a Save, el contenido del bit de posición place del servidor es bit.

Si una llamada a Save provoca un veredicto de respuesta incorrecta, el programa termina en ese momento.

Justo antes de cada llamada a Anya, todos los bits del servidor se inicializan siempre a $0$. Es decir, al terminar Anya, las posiciones en las que no se haya escrito mediante Save contienen $0$.

El segundo archivo debe llamarse Boris.c o Boris.cpp. Implementa la estrategia de Boris y debe implementar las dos rutinas siguientes. El programa debe incluir Borislib.h.

void InitBoris(int N, int A[], int B[])

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

• El parámetro N representa el número de ciudades.
• Los parámetros A[] y B[] son secuencias de longitud $N-1$ que representan las conexiones de las carreteras. Los elementos A[i] y B[i] ($0 \le i \le N-2$) son enteros que indican que la carretera $i$ conecta en ambos sentidos las ciudades A[i] y B[i], y satisfacen $0 \le A[i] < B[i] \le N-1$.

int Boris(int city)

Esta función se llama varias veces después de llamar a InitBoris. Corresponde a las acciones de Boris al responder una pregunta de un ciudadano.

• El parámetro city representa la pregunta del ciudadano y es un entero entre $1$ y $N-1$, inclusive. Indica que el ciudadano pregunta cuál es el número mínimo de carreteras en las que está nevando que debe atravesar para viajar desde la ciudad $0$ hasta la ciudad city.
• La función Boris debe devolver un entero entre $0$ y $N-1$, inclusive, que responda la pregunta. Si devuelve un entero fuera de este intervalo, se obtiene Wrong Answer [4]. Si la respuesta no es correcta, se obtiene Wrong Answer [7].

Dentro de Boris se puede llamar a la siguiente función.

int Ask(int place)

Esta función representa la operación de Boris de leer un bit del servidor.

• El parámetro place representa la posición del bit que se lee. Debe ser un entero entre $0$ y $L-1$, inclusive. Si se llama con un valor fuera de este intervalo, se obtiene Wrong Answer [5].

El valor devuelto por Ask es un entero $0$ o $1$ que representa el contenido del bit de posición place del servidor. Además, por cada llamada a Boris, solo se puede llamar a Ask como máximo $20$ veces. Si se llama más de $20$ veces, se obtiene Wrong Answer [6].

Si una llamada a Ask provoca un veredicto de respuesta incorrecta, el programa termina en ese momento.

Procedimiento de evaluación

La evaluación se realiza de la siguiente manera. Si se obtiene un veredicto de respuesta incorrecta, el programa termina en ese momento.

1. Se llama una vez a InitAnya y una vez a InitBoris, en ese orden, para proporcionar la información de las carreteras.

2. Para $i=1,\ldots,Q$, se realizan en orden las siguientes operaciones.

   • (a) Se llama a Anya exactamente una vez. Corresponde a la decisión de Anya sobre los bits que guardará en el servidor después de actualizarse la información de nevadas al comienzo del día.
   • (b) Se llama a Boris $D_i$ veces. $D_i$ es el número de preguntas de los ciudadanos en el día $i$. El parámetro de la llamada $j$ ($1 \le j \le D_i$) es $R_{ij}$ ($1 \le R_{ij} \le N-1$). Si en la llamada $j$ el valor devuelto por Boris no coincide con el número mínimo de carreteras en las que está nevando que hay que atravesar para viajar desde la ciudad $0$ hasta la ciudad $R_{ij}$, se obtiene una respuesta incorrecta.

3. Si no se ha obtenido ninguna respuesta incorrecta, la solución se considera correcta.

Observaciones importantes

• El tiempo de ejecución y la memoria utilizada se miden en los pasos (1) y (2) del «Procedimiento de evaluación». Si la solución es correcta, en el paso (2) se llama a Anya un total de $Q$ veces y a Boris un total de $D_1+\cdots+D_Q$ veces.
• Ni Anya ni Boris pueden conocer los valores $D_1,\ldots,D_Q$.
• La función Boris no recibe información que indique cuándo la función Anya ha actualizado los datos guardados en el servidor.
• Puedes implementar otras rutinas para uso interno y declarar variables globales. Sin embargo, los dos programas entregados se enlazan junto con el evaluador para formar un único ejecutable, por lo que todas las variables globales y rutinas internas de cada archivo (excepto InitAnya, Anya, InitBoris y Boris) deben declararse static para evitar interferencias con otros archivos. Durante la evaluación, el programa se ejecuta en dos procesos, uno para Anya y otro para Boris; ambos no pueden compartir las variables globales del programa.
• Tu solución no debe comunicarse de ninguna manera con la entrada estándar, la salida estándar ni otros archivos.

Compilación y ejecución

En el archivo que se puede descargar desde la página del concurso hay un evaluador de ejemplo para probar tu programa. También contiene ejemplos de los archivos que debes entregar.

El evaluador de ejemplo consta de un único archivo, grader.c o grader.cpp. Si tus programas son Anya.c y Boris.c, o Anya.cpp y Boris.cpp, ejecuta los siguientes comandos para probarlos.

• Para C

gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• Para C++

g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.cpp

Si la compilación tiene éxito, se genera un ejecutable llamado grader.

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

Descripción del evaluador de ejemplo

El evaluador de ejemplo llama a las funciones según el «Procedimiento de evaluación».

Ten en cuenta la siguiente diferencia con el comportamiento del evaluador real.

• El evaluador de ejemplo no comprueba Wrong Answer [7]; en su lugar, imprime el valor devuelto por Boris para cada pregunta.

Entrada del evaluador de ejemplo

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

• La primera línea contiene un entero $N$, que indica el número de ciudades.
• La línea $i+1$ ($0 \le i \le N-2$) de las siguientes $N-1$ líneas contiene los enteros $A_i$, $B_i$ separados por un espacio. Indican que la carretera $i$ conecta en ambos sentidos las ciudades $A_i$ y $B_i$.
• La siguiente línea contiene un entero $Q$, que indica que el campeonato dura $Q$ días.
• La línea $i$ ($1 \le i \le Q$) de las siguientes $Q$ líneas contiene una cadena $S_i$ de longitud $N-1$ y $D_i+1$ enteros, separados por espacios. $S_i$ representa las nevadas del día $i$: si su carácter $j+1$ desde la izquierda ($0 \le j \le N-2$) es 1, está nevando en la carretera $j$; si es 0, no está nevando en ella. El primero de los $D_i+1$ enteros es $D_i$, y los siguientes $D_i$ enteros son $R_{i1},\ldots,R_{iD_i}$. Indican que la pregunta $j$ ($1 \le j \le D_i$) del día $i$ trata sobre el número mínimo de carreteras en las que está nevando que hay que atravesar para viajar desde la ciudad $0$ hasta la ciudad $R_{ij}$.

Salida del evaluador de ejemplo

El evaluador de ejemplo escribe la siguiente información en la salida estándar (las comillas no se imprimen realmente).

• Si durante la ejecución se obtiene un veredicto de respuesta incorrecta, se imprime su tipo, por ejemplo Wrong Answer [1], y la ejecución termina.
• Si ninguna de las $D_i$ llamadas a Boris posteriores a la llamada $i$ a Anya ($1 \le i \le Q$) obtiene un veredicto de respuesta incorrecta, en ese momento se imprimen en una línea $D_i$ enteros separados por espacios. El entero $j$ ($1 \le j \le D_i$) es el valor devuelto por Boris al recibir $R_{ij}$.

Si el programa cumple varias condiciones de respuesta incorrecta, solo se muestra uno de los tipos correspondientes.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1+\cdots+D_Q \le 500$.
• Se puede viajar entre cualesquiera dos ciudades distintas pasando por algunas carreteras.

Subtareas

Subtarea 1 [15 puntos]

• Se cumple $N \le 20$.

Subtarea 2 [5 puntos]

• Se cumple $N \le 100$.

Subtarea 3 [35 puntos]

Se cumplen las siguientes condiciones.

• $A_i=i$ ($0 \le i \le N-2$).
• $B_i=i+1$ ($0 \le i \le N-2$).

Subtarea 4 [45 puntos]

No hay restricciones adicionales.

Ejemplos

A continuación se muestra un ejemplo de entrada para el evaluador de ejemplo y las llamadas a funciones correspondientes.

Entrada 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Ejemplo de llamadas

Ten en cuenta que las llamadas a funciones de este ejemplo no son necesariamente significativas.

En este caso, los argumentos pasados a InitAnya(...), InitBoris(...) y a la primera y segunda llamadas a Anya(...) son los siguientes.