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

У Мумиджу есть корневое дерево, состоящее из n вершин. Вершины дерева пронумерованы целыми числами от 1 до n. Корень дерева имеет номер 1. Мумиджу решил поиграть в игру на этом дереве.

Игра состоит из нескольких шагов. На каждом шаге Мумиджу выбирает одну из оставшихся вершин дерева (обозначим ее v) и удаляет из дерева все вершины поддерева с корнем в вершине v. Сама вершина v тоже удаляется. Игра заканчивается, когда в дереве не остается вершин. Другими словами, игра заканчивается после шага, на котором выбрана вершина с номером 1.

Каждый раз Мумиджу выбирает новую вершину равновероятно среди всех оставшихся вершин. Ваша задача — найти математическое ожидание количества шагов в описанной игре.

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

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество вершин дерева. В следующих n - 1 строках заданы ребра дерева. В i-той строке записаны целые числа ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — номера вершин, которые соединены i-тым ребром.

Гарантируется, что заданный граф является деревом.

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

Выведите единственное вещественное число — математическое ожидание количества шагов в описанной игре.

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

Примеры
Входные данные
2
1 2
Выходные данные
1.50000000000000000000
Входные данные
3
1 2
1 3
Выходные данные
2.00000000000000000000
Примечание

В первом тестовом примере возможны два случая. Первый — это сразу удалить корень, второй — удалить корень после одного шага. Таким образом, математическое ожидание количества шагов равно:

1 × (1 / 2) + 2 × (1 / 2) = 1.5

Второй пример более сложный. Два случая из трех приводят нас к задаче, эквивалентной первому тестовому примеру, третий случай — удалить корень на первом шаге. Таким образом, математическое ожидание количества шагов равно:

1 × (1 / 3) + (1 + 1.5) × (2 / 3) = (1 / 3) + (5 / 3) = 2