Зеник знаходиться в лабіринті, який можна представити як дерево з вершинами та n - 1 ребрами, де вершини — це кімнати, а ребра — проходи між ними. З кожної кімнати можливо добратися в кожну іншу використовуючи переходи між кімнатами. Вершина є виходом з лабіринту, до якого Зеник прагне потрапити якомога швидше.
Кожну секунду всі ребра незалежно та рівноймовірно отримують нову орієнтацію. Для кожного ребра між двома суміжними вершинами та ребро стає орієнтованим або з в , або з в , з ймовірністю \frac{1}{2} кожне. Ребра ніколи не бувають двонаправленими; вони завжди орієнтовані лише в один бік.
Після зміни орієнтації ребер Зеник знає поточну орієнтацію всіх ребер і приймає рішення про свій наступний крок з метою мінімізувати очікуваний час досягнення вершини .
Зеник діє наступним чином:
Якщо з його поточної вершини існує принаймні одне ребро, орієнтоване з в сусідню вершину , він повинен обрати одну з таких вершин та переміститися до неї. Переміщення займає секунду.
Якщо з вершини немає жодних вихідних ребер, Зеник змушений чекати секунду до наступної переорієнтації ребер.
Орієнтація ребер змінюється щосекунди, одразу перед тим, як Зеник приймає рішення про свій наступний крок.
Ваша задача — допомогти Зенику визначити для кожної вершини (2 \leq v \leq n) математичне очікування часу (у секундах), необхідного для досягнення вершини , починаючи з вершини , за умови, що він діє оптимально, щоб мінімізувати цей час.
Перший рядок містить одне ціле число — кількість вершин у дереві.
-ий з наступних n-1 рядків містить два цілих числа u_i та v_i, що означає, що між вершинами з цими індексами є ребро.
2 \le n \le 2 \cdot 10^5,
1 \le u_i, v_i \le n.
Виведіть n - 1 чисел. -те число у рядку має означати математичне очікування для вершнини + 1.
Відповідь буде зарахована, якщо її абсолютна чи відносна похибка не буде більшою ніж 10^{-7}.
Приклад
Приклад 1