Королевство Гоа представляет собой сеть из $n$ островов (пронумерованных от $1$ до $n$), соединенных $n - 1$ двунаправленными мостами. Сеть имеет структуру дерева. На некоторых островах спрятаны ценные сокровища, и Луффи отправился на поиски, чтобы найти сокровища на всех островах.

Чтобы облегчить поиски сокровищ, он купил детектор у местного торговца. Детектор должен был показывать расстояние от каждого острова до ближайшего сокровища (в количестве мостов); однако, по-видимому, он ужасно сломан и вместо этого показывает расстояние от каждого острова до самого дальнего сокровища!

Тем не менее, он сохранил расстояния, которые показал его сломанный детектор для каждого из островов, надеясь, что, возможно, еще не все потеряно. Теперь он хочет узнать, на каких островах вероятность наличия сокровища выше.

Ваша задача — помочь Луффи, расположив $n$ островов в порядке убывания вероятности наличия на них сокровища, учитывая, что теперь ему известны расстояния, показанные детектором для каждого из $n$ островов. Изначально можно предположить, что каждый из островов независимо имел 50% шанс содержать сокровище; иными словами, любое подмножество островов с равной вероятностью могло быть подмножеством островов с сокровищами.

Входные данные

Первая строка входных данных содержит $n$ ($1 \le n \le 250\,000$), количество островов. Следующие $n - 1$ строк описывают мосты. Каждый мост соединяет два различных острова. Наконец, последняя строка содержит $n$ неотрицательных целых чисел — расстояния (в количестве мостов), показанные на детекторе Луффи для каждого из островов.

Гарантируется, что существует по крайней мере одно непустое подмножество, согласующееся с входными данными.

Выходные данные

Выведите перестановку размера $n$ — порядок островов от наибольшей к наименьшей вероятности наличия сокровища. Если два острова имеют одинаковую вероятность наличия сокровища, выведите их в порядке возрастания их идентификаторов.

Примеры

Входные данные 1

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

Выходные данные 1

3 4 5 1 2

Примечание

В первом примере остров 3 обязательно должен содержать сокровище, так как это единственный остров на расстоянии 2 от острова 2. Острова 4 и 5 имеют вероятность $2/3$ каждый, в то время как острова 1 и 2 имеют вероятность $1/2$.

Входные данные 2

4
2 1
3 2
3 4
1 0 1 2

Выходные данные 2

2 1 3 4

Примечание

Во втором примере единственным возможным сценарием является тот, при котором сокровище находится только на острове 2.