Лабіринт

Обмеження: 4 сек., 1024 МіБ

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

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

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

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

• Якщо з його поточної вершини \(v\) існує принаймні одне ребро, орієнтоване з \(v\) в сусідню вершину \(u\), він повинен обрати одну з таких вершин та переміститися до неї. Переміщення займає \(1\) секунду.

• Якщо з вершини \(v\) немає жодних вихідних ребер, Зеник змушений чекати \(1\) секунду до наступної переорієнтації ребер.

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

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

Вхідні дані

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

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

Вихідні дані

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

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

Обмеження

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

\(1 \le u_i, v_i \le n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 2 3 2 4	3.5000000000 5.5000000000 5.5000000000

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 1 2	2.0000000