B. Puzzles
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Барни живет в USC (United States of Charzeh). USC состоит из n городов с номерами от 1 до n и n - 1 дорог между ними. Города и дороги в USC формируют корневое дерево (и Барни понятия не имеет, почему оно корневое). Корню дерева соответствует город номер 1. Таким образом, начиная в городе 1, по дорогам можно добраться до любого другого города.

Незнакомка завладела сердцем Барни, и теперь он хочет ее найти. Он начинает поиски в городе номер 1, и, (так как он Барни Стинсон, а не кто-то еще), и для поисков использует случайный поиск в глубину. Этот алгоритм можно описать с помощью следующего псевдокода:


let starting_time be an array of length n
current_time = 0
dfs(v):
current_time = current_time + 1
starting_time[v] = current_time
shuffle children[v] randomly (each permutation with equal possibility)
// children[v] is vector of children cities of city v
for u in children[v]:
dfs(u)

Как было сказано ранее, Барни начинает свое путешествие в корне дерева (что эквивалентно вызову dfs(1)).

Теперь Барни нужно собрать рюкзак, и поэтому он хочет знать больше о предстоящем путешествии: для каждого города i Барни хочет знать математическое ожидание величины starting_time[i]. Барни — друг Джона Сноу, и поэтому ничего не знает, в связи с чем просит вас ему помочь.

Входные данные

В первой строке содержится единственное целое число n (1 ≤ n ≤ 105) — число городов в USC.

Во второй строке содержится n - 1 число p2, p3, ..., pn (1 ≤ pi < i), где pi — номер города, являющегося предком города i в дереве, другими словами, в USC есть дорога между городами pi и i.

Выходные данные

В единственной строке выведите n чисел, значение i-го из которых равно математическому ожиданию величины starting_time[i].

Ответ для каждого города будет засчитан, если его абсолютная или относительная погрешность не превосходит 10 - 6.

Примеры
Входные данные
7
1 2 1 1 4 4
Выходные данные
1.0 4.0 5.0 3.5 4.5 5.0 5.0 
Входные данные
12
1 1 2 2 4 4 3 3 1 10 8
Выходные данные
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0