Лабіринт#12949

Лабіринт

Зеник знаходиться в лабіринті, який можна представити як дерево з вершинами та n - 1 ребрами, де вершини — це кімнати, а ребра — проходи між ними. З кожної кімнати можливо добратися в кожну іншу використовуючи переходи між кімнатами. Вершина є виходом з лабіринту, до якого Зеник прагне потрапити якомога швидше.

Кожну секунду всі ребра незалежно та рівноймовірно отримують нову орієнтацію. Для кожного ребра між двома суміжними вершинами та ребро стає орієнтованим або з в , або з в , з ймовірністю \frac{1}{2} кожне. Ребра ніколи не бувають двонаправленими; вони завжди орієнтовані лише в один бік.

Після зміни орієнтації ребер Зеник знає поточну орієнтацію всіх ребер і приймає рішення про свій наступний крок з метою мінімізувати очікуваний час досягнення вершини .

Зеник діє наступним чином:

Орієнтація ребер змінюється щосекунди, одразу перед тим, як Зеник приймає рішення про свій наступний крок.

Ваша задача — допомогти Зенику визначити для кожної вершини (2 \leq v \leq n) математичне очікування часу (у секундах), необхідного для досягнення вершини , починаючи з вершини , за умови, що він діє оптимально, щоб мінімізувати цей час.

Input

Перший рядок містить одне ціле число — кількість вершин у дереві.

-ий з наступних n-1 рядків містить два цілих числа u_i та v_i, що означає, що між вершинами з цими індексами є ребро.

2 \le n \le 2 \cdot 10^5,

1 \le u_i, v_i \le n.

Output

Виведіть n - 1 чисел. -те число у рядку має означати математичне очікування для вершнини + 1.

Відповідь буде зарахована, якщо її абсолютна чи відносна похибка не буде більшою ніж 10^{-7}.

Examples

Example

Loading
Loading

Example 1

Loading
Loading