En el juego de emparejamiento (matching) en línea clásico, las aristas de un grafo se revelan una por una. Cada vez que se muestra una arista, debes decidir inmediata e irrevocablemente si incluirla en tu emparejamiento. Tu objetivo es asegurar que no haya dos aristas elegidas que compartan un vértice, mientras maximizas el número total de aristas seleccionadas.

Eres un ambicioso científico de la computación, hambriento de fama. Como bien sabes, encontrar un emparejamiento máximo en un entorno en línea es demostrablemente imposible con alta probabilidad, incluso para las clases más simples de grafos, como los grafos bipartitos. Sin embargo, donde otros ven una barrera fundamental, tú ves una oportunidad para la gloria. Hoy, afirmas haber resuelto el problema abierto de larga data para árboles y estás listo para revelar tu algoritmo innovador al mundo.

Solo hay un problema: ayer descubriste un error en tu demostración y todavía no tienes idea de cómo solucionarlo. Sin querer abandonar el centro de atención, decides convertir tu demostración en un espectáculo de magia: tu asistente, oculto tras bambalinas, transmitirá una pequeña pista sobre todo el árbol con $n$ vértices antes de que comience el juego.

Tu plan original era simple: hacer que tu asistente envíe la respuesta a cada consulta de arista directamente. Con este fin, has instalado un auricular secreto capaz de recibir una única cadena binaria de longitud $(n - 1)$. Pero la audiencia es escéptica respecto a tu "avance". Para evitar cualquier truco preestablecido, exigen que las aristas se presenten en un orden uniformemente aleatorio, uno que ni tú ni tu asistente pueden predecir o controlar.

El escenario está listo. Las luces están sobre ti. Ahora demuestra tu afirmación, sin cambiar de canal.

Interacción

Tu solución se ejecuta dos veces en cada prueba. En la ronda prepare, tu solución actuará como el asistente. En la ronda play, tu solución actuará como tú, el mago. En cualquiera de las rondas, tu solución será evaluada como un procedimiento interactivo.

Recuerda vaciar el búfer de salida después de cada impresión. Para vaciar tu salida, puedes usar: fflush(stdout) o cout.flush() en C/C++; System.out.flush() en Java y Kotlin; * sys.stdout.flush() en Python.

Ronda prepare

La primera línea de la entrada contiene la palabra prepare. La segunda línea contiene un entero $n$ ($2 \le n \le 500$), el número de vértices. Las siguientes $(n - 1)$ líneas contienen cada una dos enteros $u$ y $v$ ($1 \le u, v \le n, u < v$), que denotan una arista no dirigida entre $u$ y $v$ en el árbol.

Debes imprimir una línea que contenga una cadena binaria $s$ de longitud exacta $(n - 1)$ que consista únicamente en los caracteres 0 y 1. Esta es la cadena transmitida a la segunda ronda, play. Si tu salida no se ajusta al formato deseado, recibirás el veredicto de Wrong Answer.

Ronda play

Tu solución será reiniciada para la ronda play.

La primera línea contiene la palabra play. La segunda línea contiene el entero $n$. La tercera línea contiene la cadena binaria $s$ exactamente como la imprimiste en la ronda prepare.

Después de eso, el juego comienza con $(n - 1)$ turnos. En cada turno, se proporcionará una línea que contiene dos enteros $u$ y $v$ ($1 \le u, v \le n, u < v$). Como respuesta, debes imprimir una línea que contenga take o ignore. Todas las aristas en la primera ronda se proporcionarán exactamente una vez, y el orden de las aristas se elige uniformemente al azar de entre $(n - 1)!$ permutaciones posibles.

Cuando hay una salida en formato no válido, el juego terminará inmediatamente sin más información del interactor.

Evaluación de la corrección

Sea $M$ el conjunto de aristas que tu solución toma. Se considera aceptable si ningún vértice es incidente a más de una arista tomada y $|M| = |M^*|$, donde $M^*$ es el emparejamiento máximo del grafo.

Hay exactamente 50 pruebas, excluyendo las pruebas de ejemplo. Para aprobar el problema, tu solución debe ser correcta en todas las pruebas, incluidas las de ejemplo.

Todas las mezclas están garantizadas de estar fijadas antes de recibir la salida de la solución. La aleatoriedad está fijada para cada prueba, implementada fijando la semilla de un generador de números pseudoaleatorios.

Se proporciona una herramienta de prueba para ayudarte a desarrollar y probar tu solución.

Ejemplos

Entrada 1

prepare
3
1 2
1 3

Salida 1

00

Entrada 2

play
3
00
1 3
1 2

Salida 2

take
ignore

Nota

Explicación del Ejemplo 1: Dado que $|M^*| = 1$, tomar cualquier arista es aceptable, y la pista puede ser arbitraria.

Magically Marked Matching Master