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
399 516
568 901
516 568
40 792
523 863
792 995
516 559
523 248
399 40
568 266
559 308
792 544
559 379
40 523

Poprawną odpowiedzią jest wyjście:

399
40 516
523 792 559 568
248 863 544 995 308 379 266 901

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 :