У Мумиджу есть корневое дерево, состоящее из n вершин. Вершины дерева пронумерованы целыми числами от 1 до n. Корень дерева имеет номер 1. Мумиджу решил поиграть в игру на этом дереве.
Игра состоит из нескольких шагов. На каждом шаге Мумиджу выбирает одну из оставшихся вершин дерева (обозначим ее v) и удаляет из дерева все вершины поддерева с корнем в вершине v. Сама вершина v тоже удаляется. Игра заканчивается, когда в дереве не остается вершин. Другими словами, игра заканчивается после шага, на котором выбрана вершина с номером 1.
Каждый раз Мумиджу выбирает новую вершину равновероятно среди всех оставшихся вершин. Ваша задача — найти математическое ожидание количества шагов в описанной игре.
Выходные данные
Выведите единственное вещественное число — математическое ожидание количества шагов в описанной игре.
Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает 10 - 6.
Примечание
В первом тестовом примере возможны два случая. Первый — это сразу удалить корень, второй — удалить корень после одного шага. Таким образом, математическое ожидание количества шагов равно:
1 × (1 / 2) + 2 × (1 / 2) = 1.5Второй пример более сложный. Два случая из трех приводят нас к задаче, эквивалентной первому тестовому примеру, третий случай — удалить корень на первом шаге. Таким образом, математическое ожидание количества шагов равно:
1 × (1 / 3) + (1 + 1.5) × (2 / 3) = (1 / 3) + (5 / 3) = 2
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
1.50000000000000000000
|
|
2
|
3
1 2
1 3
|
2.00000000000000000000
|