Este es un problema de comunicación.

Asegúrese de vaciar el búfer de salida estándar después de cada salida. A continuación se muestra cómo hacerlo en varios lenguajes de programación:

• Para C/C++, utilice fflush(stdout) o cout.flush();
• Para Java, utilice System.out.flush();
• Para Python, utilice sys.stdout.flush().

Antecedentes del problema

La red de suministro eléctrico ha sido reparada y el proyector holográfico finalmente se ha iniciado con éxito. A medida que la noche se profundiza, las proyecciones holográficas en el aire se vuelven coloridas y deslumbrantes. Una vez que todo está listo, el pequeño T y el pequeño S han abierto oficialmente el telón de las actividades nocturnas, invitando a todos a participar juntos en este juego de luz y sombra cuidadosamente preparado que pone a prueba la comprensión tácita de la cooperación entre dos personas: "Descifrado de flujo de luz".

Los haces de luz en el centro de la plaza se entrelazan, convergiendo lentamente en un árbol de luz completo. El árbol de luz está compuesto por varios nodos de grupos de luz suspendidos y las líneas de flujo de luz que los conectan, presentando una estructura de árbol pura. Al comienzo del juego, ninguna de las líneas está iluminada, y los desafiantes no pueden observar ninguna línea iluminada. Karuha, quien opera el sistema, primero mostrará un número secreto a un desafiante estacionado frente a la consola. Posteriormente, las líneas de flujo de luz se iluminarán una por una, y el desafiante debe decidir la dirección del flujo en el momento en que cada línea aparece; mientras que el compañero que está al otro lado del escenario principal solo necesita deducir con precisión este número secreto basándose en la estructura final del árbol orientado.

Como participantes de la celebración, Neri y Noir han decidido cooperar para completar este desafío.

En este desafío, Neri estará estacionada frente a la consola. Karuha, quien controla el sistema, primero le dará dos números enteros positivos $n, s$ ($1 \le s \le 2^{n-1}$), que representan la cantidad de grupos de luz y el número secreto del árbol de luz completo.

Posteriormente, Karuha iluminará secuencialmente $n - 1$ líneas de flujo de luz. Neri debe decidir inmediatamente la dirección de flujo para cada línea en el momento en que esta se ilumine.

Para Noir, quien se encuentra al otro lado del escenario principal, ella observará la forma final del árbol de luz completo lleno de flujos de luz. Ella necesita deducir el número secreto $s$ que Karuha le transmitió a Neri basándose en la dirección de flujo de estas líneas.

Para ganar este desafío de luz y sombra, Neri y Noir deben formular una estrategia con antelación para asegurar que puedan superar este juego de cooperación mutua sin problemas.

Detalles de implementación

Tu programa se ejecutará dos veces. La primera vez interpretará a Neri, decidiendo la dirección de flujo de cada línea; la segunda vez interpretará a Noir, deduciendo el número secreto a partir de la forma final del árbol de luz. El interactuador interpretará a Karuha y transmitirá información a tu programa.

En la primera ejecución, tu programa recibirá primero la cantidad de grupos de luz $n$ y el número secreto $s$, y luego recibirá secuencialmente las $n - 1$ líneas de flujo de luz que se iluminan. Tu programa debe inmediatamente enviar a la biblioteca de interacción la dirección de flujo que ha determinado, para así transmitir la información a la segunda ejecución.

En la segunda ejecución, tu programa recibirá de la biblioteca de interacción la información de la primera ejecución, es decir, la dirección de flujo de las líneas de luz en el árbol de luz completo, y luego deberá deducir el número secreto $s$ que Karuha le transmitió a Neri basándose en esta información.

Cada caso de prueba contiene múltiples grupos de datos. La primera línea de la entrada contiene dos números enteros positivos $T, r$ ($1 \le T \le 10^4, r \in \{1, 2\}$), que representan el número de grupos y el número de etapa. Para cada grupo de prueba:

• Si $r = 1$:

  • La primera línea contiene dos números enteros positivos $n, s$ ($3 \le n \le 30, 1 \le s \le 2^{n-1}$), que representan la cantidad de grupos de luz y el número secreto del árbol de luz completo.
  • A continuación, se iluminarán secuencialmente $n - 1$ líneas de flujo de luz. Cada vez que se ilumine una línea, se introducirán dos números enteros positivos $u, v$ ($1 \le u < v \le n$), que representan los números de los dos grupos de luz conectados por la línea. Debes inmediatamente imprimir una línea con dos números enteros positivos $u, v$ o $v, u$, indicando que la dirección del flujo es de $u$ a $v$ o de $v$ a $u$.
  • Para cada línea de flujo de luz, debes imprimir la dirección de flujo de esa línea y vaciar el búfer de salida estándar antes de poder continuar recibiendo la siguiente línea de flujo de luz.

• Si $r = 2$:

  • La primera línea contiene un número entero positivo $n$ ($3 \le n \le 30$), que representa la cantidad de grupos de luz del árbol de luz completo.
  • A continuación, se introducen $n - 1$ líneas, cada una con dos números enteros positivos $u, v$ ($1 \le u, v \le n$), que representan una línea de flujo de luz que va del grupo de luz $u$ al grupo de luz $v$.
  • Debes inmediatamente imprimir una línea con un número entero positivo, que represente el número secreto $s$ deducido.
  • El orden de entrada de los datos de prueba dentro de un mismo caso de prueba puede ser diferente al de la primera ejecución.
  • Para el mismo grupo de prueba, el orden de entrada de las líneas de flujo de luz puede ser inconsistente entre las dos ejecuciones, pero la numeración de todos los grupos de luz permanece sin cambios.
  • Para cada grupo de prueba, debes imprimir el número secreto $s$ deducido y vaciar el búfer de salida estándar antes de poder continuar recibiendo el siguiente grupo de prueba.

Ejemplos

Entrada 1

1 1
7 21
1 6
3 5
2 4
3 4
1 2
6 7

Salida 1

6 1
3 5
4 2
3 4
1 2
7 6

Entrada 2

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

Salida 2

59

Figura 1: Primer grupo de datos de prueba

Figura 2: Segundo grupo de datos de prueba

Detalles de implementación (Herramienta de prueba)

El script proporcionado treedir_testing_tool.py puede ayudarte a realizar pruebas locales para verificar la corrección de tu programa e imprimir el proceso de interacción detallado. Para realizar la prueba, coloca el script en el mismo directorio que tu ejecutable compilado y luego ejecuta el siguiente comando en la terminal:

python3 treedir_testing_tool.py [--quiet] <data_file> <program> <arguments>

Donde: -q, --quiet es un parámetro opcional. Si se utiliza, el script de prueba ya no imprimirá el proceso de interacción detallado. data_file es la ruta del archivo de datos de entrada proporcionado al script de prueba. Este archivo debe cumplir con el siguiente formato: La primera línea contiene dos números enteros no negativos $T, seed$, que representan el número de grupos de prueba y la semilla aleatoria utilizada para barajar el orden de las pruebas y el orden de las conexiones dentro del árbol. Si se especifica seed = 0, significa que no se realiza ninguna baraja. El formato de cada grupo es exactamente el mismo que el formato de entrada de la "primera ejecución" descrito anteriormente. program es la ruta de tu ejecutable compilado. arguments son los argumentos de línea de comandos adicionales que se pasan al ejecutable.

Nota

1. La implementación del script de prueba no es exactamente igual a la de la biblioteca de evaluación real; los resultados de las pruebas locales no son concluyentes y solo sirven como referencia durante la fase de depuración.
2. El script de prueba solo realizará una validación de formato básica sobre los datos en data_file, y no comprobará si cumplen legalmente con las restricciones del problema (por ejemplo, no comprobará si $s$ satisface la restricción $1 \le s \le 2^{n-1}$, ni juzgará si las líneas de flujo de luz pueden formar correctamente un árbol).
3. El script de prueba no monitoreará el consumo de tiempo y espacio de tu programa, por lo que no puede utilizarse para probar si cumple con las restricciones de espacio y tiempo del problema.