Zadanie : drzbin-8
Zadanie

Jaś właśnie narysował pełne drzewo binarne o wysokości n poziomów, w którym wszystkie wierzchołki mają różne wartości i dla każdego wierzchołka, który nie jest liściem jego lewy bezpośredni potomek jest mniejszy od prawego. Następnie Jaś opisał to drzewo podając wszystkie jego krawędzie w postaci par liczb, gdzie pierwsza liczba pary jest wartością wierzchołka rodzica, druga wartością wierzchołka potomka. Tak Jasio nakombinował, że teraz ma poważny kłopot z odtworzeniem tego drzewa.

Napisz program, który pomoże Jasiowi w wykonaniu tego zadania.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą n z zakresu 1..8 - wysokość drzewa. W każdym z kolejnych 2n-2 wierszy zapisano parę liczb całkowitych oddzielonych pojedynczą spacją z zakresu 0..1000 - jedną z krawędzi drzewa.

Wyjście

W kolejnych n wierszach wyjścia należy wypisać wartości wszystkich wierzchołków drzewa od góry do dołu i od lewej do prawej zgodnie z przykładem (bez spacji na końcu linii).

Przykład

Dla danych podanych na wejściu:

4
760 659
563 711
760 317
403 534
534 282
35 403
563 517
796 979
35 18
18 796
18 760
796 988
534 540
403 563

Poprawną odpowiedzią jest wyjście:

35
18 403
760 796 534 563
317 659 979 988 282 540 517 711

Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5

Opcje zadania:

Biblioteki         : iostream iomanip cmath 
Limit czasu        : 0.1 s
Limit pamięci      : 32 MB
Słowa niedozwolone :