Los países A y B mantienen malas relaciones. A quiere descubrir la red ferroviaria de B para invadirlo. Ha enviado espías muchas veces, pero siempre han sido capturados antes de obtener información relevante. Por tanto, A solo sabe lo siguiente.

• La red de B consta de $N$ estaciones, numeradas de $1$ a $N$.

• Cualesquiera dos estaciones distintas están conectadas directamente por una vía o a través de otras estaciones conectadas por vías.

• Entre cualesquiera dos estaciones hay exactamente un camino.

• Ninguna vía conecta directamente una estación consigo misma.

Al comprender las limitaciones del espionaje, A planea sobornar a un alto directivo de la compañía ferroviaria de B para obtener un dibujo de la red. Enviarlo directamente revelaría al traidor, así que este lo modificará como sigue antes de enviarlo a A.

• Dibuja $K$ vías falsas. Elige estaciones distintas $a$ y $b$ que no estén conectadas directamente en el dibujo y únelas con una vía falsa. Repite esto $K$ veces.

• Pon una marca especial en una estación.

• Por último, borra todos los números de las estaciones.

El traidor transmite el dibujo resultante a A. Como esta información por sí sola dificulta reconocer la red de B, nadie sabrá que se ha filtrado información secreta.

Para que el plan funcione, deben resolverse los siguientes problemas.

• El dibujo recibido no tiene números de estaciones ni indica qué vías son reales o falsas. A solo sabe qué estación está marcada y que se añadieron exactamente $K$ vías falsas.

• El emisor debe elegir adecuadamente las vías falsas y la estación marcada para que el receptor distinga vías reales y falsas únicamente a partir del dibujo.

• El receptor también debe entender cómo se modificó el dibujo y recuperar el dibujo de la red original.

Se necesitan dos funciones: una para modificar el dibujo y otra para recuperar la red real. A quiere confiarte este trabajo.

Detalles de implementación

Debes implementar las siguientes dos funciones.

vector< pair<int, int> > encode_map(int N, int K, int &X,
                                            vector< pair<int, int> > E)

• El argumento entero N es el número $N$ de estaciones de B. Cada estación se representa mediante un entero de $1$ a $N$, inclusive.

• El argumento entero K es el número $K$ de vías falsas que se añadirán.

• El argumento X registra el número de la estación que se marcará. Al terminar la función debe contener un entero positivo de $1$ a $N$, inclusive.

• El arreglo E tiene tamaño $N-1$ y representa la red de B. Un par $(a,b)$ en E indica una vía directa entre las estaciones $a$ y $b$.

• Devuelve un arreglo con $K$ pares $(a,b)$ que indiquen vías falsas entre estaciones distintas $a$ y $b$. No puedes añadir una vía falsa entre $a$ y $b$ si ya están conectadas por una vía real o falsa.

vector< pair<int, int> > decode_map(int N, int K, int X,
                                            vector< pair<int, int> > E)

• El argumento entero N es el número $N$ de estaciones de B. Las estaciones se representan mediante enteros de $1$ a $N$, inclusive. Como sus números se borraron al enviar el dibujo, los usados aquí pueden ser distintos de los reales. Son el resultado de aplicar alguna biyección a los números usados en encode_map.

• El argumento entero K es el número $K$ de vías falsas añadidas.

• El argumento entero X es el número de la estación marcada.

• El arreglo E tiene tamaño $N+K-1$ y representa el dibujo entregado a A. Un par $(a,b)$ significa que las estaciones $a$ y $b$ están conectadas directamente por una vía real o falsa en el dibujo. El orden de los elementos de E no tiene significado.

• Esta función recupera el dibujo original a partir del producido por encode_map. Devuelve un arreglo de $N-1$ pares $(a,b)$ que contenga la red de B.

No debes llamar a funciones de entrada o salida en ninguna parte del código enviado.

Cada caso de prueba contiene uno o más escenarios independientes. Para un caso con $T$ escenarios, el programa que llama a estas funciones se ejecuta exactamente dos veces, como sigue.

Durante la primera ejecución:

• Se llama a encode_map $T$ veces.

• El sistema de evaluación guarda los resultados de encode_map.

• No se llama a decode_map.

Durante la segunda ejecución:

• Se llama a decode_map varias veces. En cada llamada se elige un escenario arbitrario y el dibujo producido para él por encode_map se usa como entrada de decode_map.

• No se llama a encode_map.

El tiempo de ejecución y el uso de memoria se calculan combinando las dos ejecuciones.

Restricciones

• $1 \le T \le 200$

• $3 \le N \le 200$

• $1 \le K < \frac{N}{2}$

Subtareas

1. ($4$ puntos) $N \le 4$.

2. ($13$ puntos) $K=1$.

3. ($11$ puntos) Cada estación está conectada a como máximo dos vías.

4. ($29$ puntos) Desde cualquier estación se puede llegar a cualquier otra recorriendo como máximo $\lfloor N/2 \rfloor$ vías.

5. ($43$ puntos) Sin restricciones adicionales.

Subtareas

Una prueba solo se considera correcta si encode_map produce un dibujo válido y decode_map identifica correctamente la red. Si el arreglo devuelto por decode_map contiene siquiera una vía falsa, la puntuación de esa prueba es $0$. El orden de los elementos de los arreglos devueltos por ambas funciones no importa.

La puntuación de una subtarea es el mínimo de las puntuaciones de todas sus pruebas.

Ejemplos

• Considera $N=6$, $K=1$ y las vías $E=[(1,2),(1,3),(1,4),(4,5),(4,6)]$.

El evaluador llama a la siguiente función.

encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)])

El dibujo izquierdo muestra la red de B. Al añadir la vía falsa $(4,2)$ y marcar la estación $1$ se obtiene el dibujo derecho. En este caso, encode_map devuelve [(4, 2)] y guarda $1$ en X. Puede haber otras respuestas.

A continuación, el evaluador llama a la siguiente función. El orden de los elementos del arreglo del último argumento puede variar.

decode_map(6, 1, 2, [(1, 5), (2, 3), (2, 4), (2, 5), (3, 5), (5, 6)])

El dibujo representado por la entrada se muestra abajo. Los números de las estaciones son distintos de los usados en encode_map.

La función devuelve [(3, 2), (4, 2), (5, 6), (1, 5), (5, 2)]. El orden de los elementos puede variar.

Este ejemplo satisface las condiciones de las subtareas $2$, $4$ y $5$.

Evaluador de ejemplo

El evaluador de ejemplo acepta entrada en el siguiente formato.

• Línea $1$: $T$

A continuación hay $T$ bloques, cada uno con un escenario. Cada bloque tiene el siguiente formato.

• Línea $1$: $N\ K$

• Línea $1+i$ ($1 \le i \le N-1$): $a_i\ b_i$

El par $a_i,b_i$ indica una vía entre las estaciones $a_i$ y $b_i$.

Para cada escenario, el evaluador de ejemplo imprime lo siguiente.

• Línea $1$: el arreglo devuelto por encode_map.

• Línea $2$: el arreglo devuelto por decode_map.

El evaluador de ejemplo puede diferir del utilizado en la evaluación real.