L'association UCPC avait annoncé il y a trois ans son intention de passer à un format de tournoi, mais a rencontré de nombreuses difficultés en raison de l'ampleur des changements. Hye-ah, qui est devenue présidente de l'association cette année, a découvert les archives de préparation de ce tournoi en lisant des documents internes et a décidé de relancer la compétition sous ce format.

Heureusement, comme exactement $2^N$ participants se sont inscrits à l'UCPC cette année, Hye-ah a pu organiser le tournoi de manière très propre en utilisant un format à élimination directe. Il s'agit du format de compétition qui vient généralement à l'esprit lorsque l'on parle de « tournoi ». Le processus est décrit en détail ci-dessous :

1. On attribue à chaque participant un numéro de tête de série unique allant de $1$ à $2^N$, et on les aligne dans une file dans un ordre arbitraire.
2. Les participants dans la file sont appariés deux par deux en commençant par le début. Les deux participants appariés disputent un match en tête-à-tête, et le perdant quitte la file. Une fois que toutes les paires ont disputé leur match, on constate que le nombre de participants restants dans la file est réduit de moitié.
3. Par conséquent, en répétant le processus 2 $N$ fois, il ne reste qu'un seul participant, qui devient le vainqueur du tournoi.

Un tournoi à élimination directe est souvent représenté par un tableau de tournoi en forme d'arbre binaire, comme illustré ci-dessous.

Figure K.1 : Exemple de tableau de tournoi pour $2^3 = 8$ participants

L'équipe organisatrice, dont fait partie Hye-ah, a supervisé tous les matchs du tournoi et a enregistré les résultats dans un document partagé. Cependant, comme plusieurs personnes ont noté les résultats de manière désordonnée, il est devenu impossible de suivre le déroulement du tournoi à partir de ces notes. De plus, après avoir compté le nombre de matchs à la fin du tournoi, l'équipe a découvert avec désespoir qu'un match manquait.

Fatiguée par l'organisation du tournoi et incapable de résoudre cette situation, l'équipe vous demande de retrouver le match manquant dans les archives.

Entrée

La première ligne contient un entier $N$ ($2 \le N \le 20$).

Les $2^N - 2$ lignes suivantes contiennent chacune deux entiers $a_i$ et $b_i$ séparés par un espace, représentant le résultat de chaque match. Cela signifie que le participant $a_i$ et le participant $b_i$ se sont affrontés et que le participant $a_i$ a gagné.

Il est garanti que l'entrée fournie correspond à un enregistrement complet du tournoi dont un match est manquant. En d'autres termes, il n'y aura pas d'entrée pour laquelle il est impossible de construire un enregistrement valide, quelle que soit la manière dont on devine le résultat du match manquant.

Sortie

Affichez le résultat du match manquant sous la forme de deux entiers, en respectant le même format que l'entrée. S'il existe plusieurs résultats possibles pour le match manquant, affichez toutes les solutions possibles, une par ligne. Dans ce cas, triez les solutions par le numéro du vainqueur croissant, puis, en cas d'égalité, par le numéro du perdant croissant.

Exemples

Entrée 1

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

Sortie 1

6 2

Entrée 2

2
3 4
1 2

Sortie 2

1 3
3 1

Remarque

Le tableau de tournoi du premier exemple est identique à celui illustré dans l'énoncé.

Le deuxième exemple correspond à un tournoi de $2^2 = 4$ participants où la finale est manquante. Comme on ne peut pas savoir qui est le vainqueur de la finale, les deux possibilités sont affichées.