D. Игра с Графом
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В информатике есть метод под названием «Разделяй и властвуй по вершине», используемый для решения тяжелых задач про пути на дереве. Опишем принцип работы этого метода функцией:

solve(t) (t — дерево):

  1. Выберите вершину x (обычно выбирается взвешенный центр) в дереве t. Назовем этот шаг алгоритма «строка A».
  2. Проделайте нужную работу с путями, проходящими через вершину x.
  3. Затем удалите x из дерева t.
  4. После этого t превращается в некоторое количество поддеревьев.
  5. Примените solve к каждому поддереву.

Этот процесс завершается, когда у t есть только одна вершина, потому что после ее удаления не остается ничего.

WJMZBMR ошибочно подумал, что можно выбрать любую вершину в «строке A». То есть, он выбирает вершину в «строке A» наугад. Ситуацию осложняет то, что по мнению юноши, у «дерева» должно быть одинаковое количество ребер и вершин! Таким образом, функция меняется следующим образом.

Определим переменную totalCost. Изначально значение totalCost равняется 0. Итак, solve(t) (теперь t — граф) выглядит так:

  1. totalCost = totalCost + (size of t). Операция «=» означает присвоение. (Size of t) означает количество вершин в t.
  2. Выберите наугад (равновероятно среди всех вершин t) вершину x в графе t.
  3. Затем удалите x из графа t.
  4. После этого t превратится в некоторое количество связных компонент.
  5. Примените solve к каждой компоненте.

Юноша применит solve к связному графу с n вершинами и n ребрами. Он думает, что функция будет работать быстро, но она очень медленная. Теперь юноша хочет узнать матожидание значения totalCost после выполнения этой процедуры. Можете ли Вы помочь ему?

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

В первой строке записано целое число n (3 ≤ n ≤ 3000) — количество вершин и ребер в графе. Каждая из следующих n строк содержит два целых числа ai, bi (0 ≤ ai, bi ≤ n - 1), записанных через пробел — они указывают на то, что между вершинами ai и bi есть ребро.

Считайте, что вершины графа пронумерованы от 0 до (n - 1). Гарантируется, что граф не содержит петель и кратных ребер. Гарантируется, что граф связный.

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

Выведите единственное вещественное число — матожидание totalCost. Ваш ответ будет признан корректным, если его абсолютная или относительная погрешность не будет превышать 10 - 6.

Примеры
Входные данные
5
3 4
2 3
2 4
0 4
1 2
Выходные данные
13.166666666666666
Входные данные
3
0 1
1 2
0 2
Выходные данные
6.000000000000000
Входные данные
5
0 1
1 2
2 0
3 0
4 1
Выходные данные
13.166666666666666
Примечание

Рассмотрим первый пример. Что бы мы ни выбрали в первую очередь, totalCost всегда будет равна 3 + 2 + 1 = 6.