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
237 631
685 502
237 306
565 237
326 503
297 685
306 677
631 40
306 969
297 326
631 144
685 467
326 437
565 297

Poprawną odpowiedzią jest wyjście:

565
237 297
306 631 326 685
677 969 40 144 437 503 467 502

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 :