Одна частина
Королівство Гоа складається з мережі з n островів (пронумерованих від 1 до n), з'єднаних n - 1 двосторонніми мостами. Ця мережа має структуру дерева. На деяких островах заховані цінні скарби, і Луффі намагається їх знайти.
Щоб полегшити пошуки, він придбав у місцевого торговця детектор. Детектор мав показувати відстань від кожного острова до найближчого скарбу (вимірювану кількістю мостів), але виявився несправним і показує відстань до найдальшого скарбу!
Незважаючи на це, Луффі записав відстані, які показав зламаний детектор для кожного острова, сподіваючись, що це може бути корисним. Тепер він хоче дізнатися, на яких островах найбільша ймовірність знайти скарб.
Ваше завдання — допомогти Луффі, впорядкувавши n островів від найбільшої до найменшої ймовірності наявності скарбів, враховуючи відстані, показані детектором для кожного з n островів. Спочатку вважайте, що на кожному острові незалежно є 50% ймовірність наявності скарбу; іншими словами, будь-яка підмножина островів могла б бути підмножиною островів зі скарбами з однаковою ймовірністю.
Вхідні дані
Перший рядок містить кількість островів n (1 ≤ n ≤ 250000). Наступні n - 1 рядків описують мости. Кожен міст з'єднує два різних острови. Останній рядок містить n цілих невід'ємних чисел — відстані (кількість мостів), показані детектором Луффі для кожного з островів.
Гарантується, що існує хоча б одна непорожня підмножина, яка узгоджується з вхідними даними.
Вихідні дані
Виведіть перестановку розміру n — порядок островів від найбільшої до найменшої ймовірності наявності на них скарбів. Якщо два острови мають однакову ймовірність містити скарби, виведіть їх у порядку зростання їх номерів.