Królestwo Goa to sieć $n$ wysp (identyfikowanych numerami od $1$ do $n$), połączonych $n - 1$ dwukierunkowymi mostami. Sieć ma strukturę drzewa. Niektóre wyspy zawierają cenne skarby, a Luffy wyrusza na poszukiwanie skarbów ze wszystkich wysp.

Aby ułatwić poszukiwania, kupił od lokalnego kupca wykrywacz. Wykrywacz powinien pokazywać odległość od każdej wyspy do najbliższego skarbu (w liczbie mostów); wydaje się jednak, że jest on poważnie uszkodzony i zamiast tego pokazuje odległość od każdej wyspy do najdalszego skarbu!

Mimo to zachował odległości, które pokazał jego zepsuty wykrywacz dla każdej z wysp, mając nadzieję, że może nie wszystko stracone. Zastanawia się teraz, które wyspy mają większą szansę na posiadanie skarbu.

Twoim zadaniem jest pomóc Luffy'emu, układając $n$ wysp w kolejności od najwyższego do najniższego prawdopodobieństwa posiadania skarbu, wiedząc, że zna on odległości pokazane przez wykrywacz dla każdej z $n$ wysp. Początkowo można założyć, że każda z wysp niezależnie miała 50% szans na posiadanie skarbu; innymi słowy, każdy podzbiór wysp był równie prawdopodobny jako podzbiór wysp ze skarbami.

Wejście

Pierwsza linia wejścia zawiera $n$ ($1 \le n \le 250\,000$), liczbę wysp. Następne $n - 1$ linii opisuje mosty. Każdy most łączy dwie różne wyspy. Ostatnia linia zawiera $n$ nieujemnych liczb całkowitych, odległości (w liczbie mostów) pokazane na wykrywaczu Luffy'ego dla każdej z wysp.

Gwarantuje się, że istnieje co najmniej jeden niepusty podzbiór, który jest zgodny z danymi wejściowymi.

Wyjście

Wypisz permutację rozmiaru $n$, będącą kolejnością wysp od najwyższego do najniższego prawdopodobieństwa posiadania skarbu. Jeśli dwie wyspy mają takie samo prawdopodobieństwo posiadania skarbu, wypisz je w kolejności rosnącej ich identyfikatorów.

Przykład

Wejście 1

5
1 2
1 3
2 4
2 5
2 2 3 3 3

Wyjście 1

3 4 5 1 2

Wejście 2

4
2 1
3 2
3 4
1 0 1 2

Wyjście 2

2 1 3 4

Uwagi

W pierwszym przykładzie wyspa 3 musi zawierać skarb, ponieważ jest jedyną w odległości 2 od wyspy 2. Wyspy 4 i 5 mają prawdopodobieństwo 2/3 każda, podczas gdy wyspy 1 i 2 mają prawdopodobieństwo 1/2.

W drugim przykładzie jedynym możliwym scenariuszem jest sytuacja, w której tylko wyspa 2 zawiera skarb.