Drzewa

Limit pamięci: 64 MB

Ostatnio Bajtek zobaczył w Bajternecie drzewo bajnarne. Drzewem bajnarnym nazywamy dowolne ukorzenione drzewo, w którym każdy wierzchołek ma lub synów. Wysokością drzewa nazywamy liczbę wierzchołków na najdłuższej ścieżce od korzenia do pewnego z liści; drzewo puste ma wysokość 0. Na drzewach bajnarnych zdefiniowany jest porządek leksykograficzny. Drzewo jest leksykograficznie mniejsze od drzewa , gdy:

• wysokość drzewa jest mniejsza od wysokości drzewa lub
• wysokości drzew i są równe oraz:
  • lewe poddrzewo jest leksykograficznie mniejsze niż lewe poddrzewo lub
  • lewe poddrzewo jest równe lewemu poddrzewu i prawe poddrzewo jest leksykograficznie mniejsze od prawego poddrzewa .

Jeśli dany wierzchołek nie posiada lewego syna, to jego lewe poddrzewo uznajemy za drzewo puste; analogicznie w przypadku braku prawego syna.

Jeśli drzewa i są różne i drzewo nie jest leksykograficznie mniejsze niż drzewo , to drzewo jest leksykograficznie większe niż drzewo .

Twoje zadanie polega na wczytaniu opisu drzewa i obliczeniu numeru tego drzewa w porządku leksykograficznym. Drzewo składające się z jednego wierzchołka ma numer .

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita () będąca liczbą drzew. W kolejnych wierszach znajduje się opisów drzew. W pierwszym wierszu opisu drzewa znajduje się jedna liczba całkowita () będąca liczbą wierzchołków, z których składa się drzewo. Wierzchołki drzewa numerujemy liczbami od do , przy czym wierzchołek jest korzeniem. Kolejne wierszy opisuje krawędzie drzewa. -ty z nich zawiera dwie liczby całkowite i () będące numerami lewego i prawego syna wierzchołka . W przypadku gdy wierzchołek nie ma lewego syna, , a gdy nie ma prawego, .

Wyjście

Na standardowe wyjście należy wypisać dokładnie wierszy zawierających jedną liczbę całkowitą będącą numerem odpowiedniego drzewa w zadanym porządku modulo .

Przykład

Dla danych wejściowych:

4
1
-1 -1
2
-1 2
-1 -1
2
2 -1
-1 -1
3
2 3
-1 -1
-1 -1

poprawną odpowiedzią jest:

1
2
3
4

Autorzy zadania: Bartosz Górski i Jakub Pawlewicz.