La asociación de clubes de programación universitaria anunció hace tres años que cambiaría el UCPC a un formato de torneo, pero experimentó muchos problemas al intentar implementar un cambio tan grande. Hye-ah, quien asumió el cargo de presidenta de la asociación este año, encontró los registros de preparación de este torneo mientras leía documentos internos y decidió volver a organizar el torneo.

Afortunadamente, como exactamente $2^N$ participantes se inscribieron en el UCPC de este año, Hye-ah pudo llevar a cabo el torneo de manera muy ordenada utilizando el formato de eliminación simple. Este es el formato de competencia que generalmente viene a la mente cuando se menciona un "torneo", y el proceso se explica en detalle a continuación:

1. Se asignan números de serie distintos del 1 al $2^N$ a los participantes y se alinean en una fila en un orden arbitrario.
2. Los participantes en la fila se emparejan de dos en dos desde el principio. Los dos participantes emparejados juegan un partido uno a uno, y el participante que pierde abandona la fila. Se puede observar que después de que todos los pares juegan, el número de participantes restantes en la fila se reduce a la mitad.
3. Por lo tanto, si se repite el proceso 2 $N$ veces, solo quedará un participante, y este participante será el ganador del torneo.

El torneo de eliminación simple se representa comúnmente mediante un cuadro de torneo en forma de árbol binario como el que se muestra a continuación.

Figura K.1: Ejemplo de un cuadro de torneo con $2^3 = 8$ participantes

El equipo de gestión del torneo, incluida Hye-ah, supervisó todos los partidos realizados y registró los resultados en un documento compartido. Sin embargo, debido a que varias personas escribieron los resultados de los partidos de forma desordenada, se volvió imposible entender el flujo del torneo a partir de este registro. Además, después de que terminó el torneo, el equipo de gestión contó el número de partidos y descubrió el hecho desesperante de que faltaba un partido.

En lugar del equipo de gestión, que está demasiado agotado por la organización del torneo como para tener la energía de resolver esta situación, encontremos el partido que falta en el registro.

Entrada

En la primera línea se proporciona un entero $N$ ($2 \le N \le 20$).

En las siguientes $2^N - 2$ líneas, se proporcionan dos enteros $a_i$ y $b_i$ separados por un espacio, que representan el resultado de cada partido. Esto significa que en el partido, el participante $a_i$ y el participante $b_i$ se enfrentaron y el participante $a_i$ ganó.

Se garantiza que la entrada proporcionada es un registro completo del torneo al que le falta un partido. Es decir, no se proporcionará ninguna entrada en la que, sin importar cómo se infiera el resultado del partido faltante, no se pueda crear un registro válido.

Salida

Imprima el resultado del partido faltante como dos enteros en el mismo formato que la entrada. Si hay múltiples resultados de partido posibles, imprima todas las respuestas posibles, una por línea. En este caso, imprima primero los resultados con el número de ganador más pequeño y, si hay varios, imprima aquellos con el número de perdedor más pequeño.

Ejemplos

Entrada 1

3
3 6
1 8
3 7
3 5
6 1
7 4

Salida 1

6 2

Entrada 2

2
3 4
1 2

Salida 2

1 3
3 1

Nota

El cuadro del torneo del primer ejemplo es el mismo que el de la figura proporcionada en el enunciado.

El segundo ejemplo es un registro de un torneo con $2^2 = 4$ participantes donde falta la final; como no se puede saber quién es el ganador de la final, se imprimen ambas posibilidades.