¿Conoces la empresa Just Ordinary Inventions? Su actividad consiste en hacer «invenciones simplemente corrientes».

JOI-kun está jugando al último juego desarrollado por Just Ordinary Inventions.

El juego consiste en explorar una mazmorra formada por varias habitaciones y caminos. Cada camino conecta dos habitaciones distintas y se puede recorrer en ambos sentidos. Entre dos habitaciones distintas hay como máximo un camino, y no hay caminos cuyos dos extremos sean la misma habitación. Además, se sabe que es posible viajar entre cualesquiera dos habitaciones utilizando algunos caminos. Las habitaciones son muy parecidas: las que tienen el mismo número de caminos de salida son completamente indistinguibles con solo observarlas.

Para facilitar el juego, cada habitación tiene una marca de referencia y un pedestal. Los caminos que salen de una habitación pueden numerarse como primero, segundo, etc., tomando la marca como referencia. La estructura de la mazmorra no cambia durante el juego. Por tanto, al salir de una misma habitación por el camino de un mismo número, siempre se llega a la misma habitación. En el pedestal hay una gema cuyo color puede cambiar el jugador. Su color es uno de los colores $1,2,\ldots,X$, y al comenzar el juego todas las gemas tienen el color 1. El color de una gema no cambia salvo que el jugador lo modifique.

JOI-kun se dio cuenta de que, si conociera la estructura de la mazmorra, es decir, cómo están conectadas sus habitaciones por caminos, podría superar el juego fácilmente. Sin embargo, por mucho que lo intentó, no consiguió determinarla. Por eso has decidido escribir un programa que determine la estructura de la mazmorra en su lugar.

Tarea

Escribe un programa que explore la mazmorra y determine su estructura. Sin embargo, JOI-kun no quería que se le revelara toda la estructura; por tanto, en lugar de responderla directamente, para cada entero $i$ entre $1$ y $R$, inclusive, el programa debe indicar cuántos pares de habitaciones tienen una distancia mínima de exactamente $i$ caminos. Intercambiar el orden de las habitaciones no cambia el par.

Para explorar la mazmorra se proporciona una biblioteca que permite realizar las siguientes acciones.

• Averiguar cuántos caminos salen de la habitación actual.
• Averiguar el color de la gema del pedestal de la habitación actual.
• Cambiar el color de la gema del pedestal de la habitación actual al color indicado, que puede ser el mismo que ya tiene. Después, elegir un camino de salida y recorrerlo hasta otra habitación.
• Averiguar qué número tiene, entre los caminos que salen de la habitación actual, el último camino recorrido.

Detalles de implementación

Debes escribir un programa que implemente cómo responder a JOI-kun. El programa debe incluir dungeon2.h.

Debe implementar la siguiente rutina.

void Inspect(int R)

Esta rutina se llama una sola vez al principio.

• El argumento $R$ indica que, para cada entero $i$ entre $1$ y $R$, inclusive, debes responder cuántos pares de habitaciones tienen una distancia mínima de exactamente $i$ caminos. Intercambiar el orden de las habitaciones no cambia el par.

Además, debes responder llamando a la siguiente rutina.

void Answer(int D, int A)

• Los argumentos $D,A$ indican que esta llamada responde que hay $A$ pares de habitaciones cuya distancia mínima es exactamente $D$ caminos.

Las llamadas a Answer deben cumplir las siguientes condiciones.

• $D$ debe ser un entero entre $1$ y $R$, inclusive. En caso contrario, se obtiene respuesta incorrecta [1].
• No debes llamar a Answer dos o más veces con el mismo argumento $D$. En caso contrario, se obtiene respuesta incorrecta [2].
• Debes llamar a Answer exactamente $R$ veces. En caso contrario, se obtiene respuesta incorrecta [3].
• $A$ debe ser el número de pares de habitaciones cuya distancia mínima es exactamente $D$ caminos. En caso contrario, se obtiene respuesta incorrecta [4].

Si una llamada a Answer se considera incorrecta, no se garantiza que el programa siga ejecutándose.

Además, el programa puede llamar a las siguientes rutinas.

void Move(int I, int C)

• El argumento $I$ es el número del camino elegido para moverse. Inmediatamente después de esta llamada, el jugador recorre el camino de salida número $I$ de la habitación actual hasta otra habitación.
• El argumento $C$ indica que, antes de moverse, el color de la gema del pedestal de la habitación actual se cambia al color $C$.

Las llamadas a Move deben cumplir las siguientes condiciones.

• Si $K$ es el número de caminos que salen de la habitación actual, el argumento $I$ debe ser un entero entre $1$ y $K$, inclusive. En caso contrario, se obtiene respuesta incorrecta [5].
• Si hay $X$ colores de gemas, el argumento $C$ debe ser un entero entre $1$ y $X$, inclusive. El valor de $X$ depende de la subtarea. En caso contrario, se obtiene respuesta incorrecta [6].
• No debes llamar a Move más de $1\,500\,000$ veces. Si lo haces, se obtiene respuesta incorrecta [7].

int NumberOfRoads()

• Esta función devuelve el número de caminos que salen de la habitación actual del jugador.

int LastRoad()

• Esta función devuelve el número del último camino recorrido, entre los caminos que salen de la habitación actual. Sin embargo, si se llama antes de haber llamado a Move por primera vez, devuelve $-1$.

int Color()

• Esta función devuelve el color de la gema del pedestal de la habitación actual del jugador.

Después de llamar a la rutina Inspect, se comprueban las respuestas.

Puedes implementar otras rutinas para uso interno y declarar variables globales. Sin embargo, tu envío no debe interactuar de ninguna manera con la entrada estándar, la salida estándar ni otros archivos.

Compilación y ejecución

El archivo que puede descargarse del sitio del concurso contiene un evaluador de ejemplo para probar tu programa. También contiene un ejemplo del archivo que debes enviar.

El evaluador de ejemplo consta de un solo archivo, grader.c o grader.cpp. Para probar tu programa, ejecuta los comandos siguientes.

C

gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

C++

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

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

Ten en cuenta que el evaluador real es distinto del de ejemplo. El evaluador de ejemplo se inicia como un único proceso, lee la entrada 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.

• La primera línea contiene los enteros $N,X,R$ separados por espacios. Esto significa que hay $N$ habitaciones, numeradas $1,2,\ldots,N$, hay $X$ colores de gemas y el programa debe responder $R$ valores.
• En las siguientes $2N$ líneas, la línea $2i-1$ ($1 \le i \le N$) contiene un entero $D_i$, que indica que salen $D_i$ caminos de la habitación $i$. La línea $2i$ ($1 \le i \le N$) contiene $D_i$ enteros $T_{i1},T_{i2},\ldots,T_{iD_i}$ separados por espacios. Esto indica que recorrer el camino de salida número $j$ ($1 \le j \le D_i$) de la habitación $i$ lleva a la habitación $T_{ij}$.
• La línea $j$ ($1 \le j \le R$) de las siguientes $R$ líneas contiene un entero $A_j$. Esto significa que hay $A_j$ pares de habitaciones cuya distancia mínima es exactamente $j$ caminos. Es decir, para cada $j$ ($1 \le j \le R$), el evaluador de ejemplo considera correcta una llamada a Answer con $D=j$ y $A=A_j$, e incorrecta cualquier otra respuesta.

El evaluador de ejemplo llama a tu rutina situando inicialmente al jugador en la habitación 1.

Salida del evaluador de ejemplo

Si la ejecución termina normalmente, el evaluador de ejemplo escribe una línea con la siguiente información en la salida estándar. (Las comillas no se imprimen.)

• Si la respuesta es correcta, imprime el número de llamadas a Move, por ejemplo, “Accepted : #move = 8”.
• Si la respuesta es incorrecta, imprime el tipo de error, por ejemplo, “Wrong Answer [1]”.

Restricciones

Todos los datos de entrada satisfacen las condiciones siguientes. Consulta el significado de $N,D_i,T_{ij}$ en la sección Entrada del evaluador de ejemplo.

• $2 \le N \le 200$.
• $3 \le X \le 100$.
• $1 \le R \le 200$.
• $1 \le D_i \le N-1$ ($1 \le i \le N$).
• $1 \le T_{ij} \le N$ y $T_{ij}\ne i$ ($1 \le i \le N$, $1 \le j \le D_i$).
• Los valores $T_{i1},T_{i2},\ldots,T_{iD_i}$ ($1 \le i \le N$) son distintos entre sí.
• Para cada $i,j$ ($1 \le i \le N$, $1 \le j \le D_i$), existe un $k$ ($1 \le k \le D_{T_{ij}}$) tal que $T_{T_{ij}k}=i$.
• Es posible viajar entre cualesquiera dos habitaciones utilizando algunos caminos.

Subtareas

En lo que sigue, $N$ es el número de habitaciones y $M$ el número de caminos de la mazmorra en los datos de entrada.

Subtarea 1 [17 puntos]

Se cumplen las siguientes condiciones.

• $N \le 50$.
• $M \le 100$.
• $X=100$.

Subtarea 2 [27 puntos]

Se cumplen las siguientes condiciones.

• $N \le 50$.
• $M \le 100$.
• $X=3$.

Subtarea 3 [56 puntos]

• Se cumple $X=3$.

La puntuación de esta subtarea se determina del modo siguiente.

• Sea $L$ el máximo, sobre todos los casos de prueba de esta subtarea, del siguiente valor:

  • $\frac{C}{M}$, donde $C$ es el número de llamadas a Move.

• Entonces, la puntuación de esta subtarea es:

  • 56 puntos si $L \le 14$.
  • $\lfloor 70-L\rfloor$ puntos si $14<L\le 32$.
  • $\left\lfloor 54-\frac{L}{2}\right\rfloor$ puntos si $32<L\le 64$.
  • 0 puntos si $64<L$.

Aquí, $\lfloor x\rfloor$ representa el mayor entero que no supera $x$.

En el sistema de evaluación, si el programa termina correctamente y su respuesta se considera correcta, se muestra “Accepted” en la columna de detalles. Sin embargo, en la evaluación de la subtarea 3, para un caso en el que los valores $C,M$ anteriores satisfagan $64<\frac{C}{M}$, se mostrará respuesta incorrecta en la columna de resultado.

Ejemplo de interacción

A continuación se muestra una entrada de ejemplo que lee el evaluador de ejemplo y las llamadas a rutinas correspondientes.

Entrada 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Llamadas de ejemplo

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