Spacer po drzewie

Limit czasu: 0.5s | Limit pamięci: 32MB

Dane jest drzewo binarne o $n$ wierzchołkach. Każdy wierzchołek ma identyfikator ID z zakresu od $0$ do $n-1$. Wypisz wszystkie identyfikatory wierzchołków drzewa w porządkach: PREORDER, INORDER i POSTORDER.

Wejście

Pierwszy wiersz wejścia zawiera liczbę $n$, liczbę wierzchołków drzewa. Następne $n$ linii zawiera informacje o kolejnych wierzchołkach drzewa w formacie: $$ \mathrm{id} \quad \mathrm{left} \quad \mathrm{right} $$ $\mathrm{id}$ oznacza identyfikator wierzchołka, $\mathrm{left}$ - identyfikator lewego dziecka, $\mathrm{right}$ - prawego. Jeśli wierzchołek nie posiada lewego dziecka, $\mathrm{left}=-1$. Podobnie, jeśli wierzchołek nie posiada prawego dziecka, $\mathrm{right}=-1$.

Wierzchołki mogą pojawić się na wejściu w dowolnej kolejności.

Wyjście

W pierwszej linii wyjścia wypisz identyfikatory wszystkich wierzchołków drzewa w porządku PREORDER. W drugiej linii - w porządku INORDRER. W trzeciej - w porządku POSTORDER.

Ograniczenia

• $1 \le n \le 25$

Przykłady

Wejście 1

9
6 -1 -1
7 -1 -1
8 -1 -1
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7

Wyjście 1

0 1 2 3 4 5 6 7 8
2 1 3 0 6 5 7 4 8
2 3 1 6 7 5 8 4 0