Лабіринт

Limits: 4 sec., 1024 MiB

Зеник знаходиться в лабіринті, який можна представити як дерево з $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$, за умови, що він діє оптимально, щоб мінімізувати цей час.

Input

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

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

Output

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

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

Constraints

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

$1 \le u_i, v_i \le n$.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 2 2 3 2 4	3.5000000000 5.5000000000 5.5000000000

Input (stdin) сopy	Output (stdout) сopy
2 1 2	2.0000000