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

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

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

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

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

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

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

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

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