CF235D.Graph Game

In computer science, there is a method called "Divide And Conquer By Node" to solve some hard problems about paths on a tree. Let's desribe how this method works by function:

solve(t) (t is a tree):

1. Chose a node x (it's common to chose weight-center) in tree t. Let's call this step "Line A".
2. Deal with all paths that pass x.
3. Then delete x from tree t.
4. After that t becomes some subtrees.
5. Apply solve on each subtree.

This ends when t has only one node because after deleting it, there's nothing.

Now, WJMZBMR has mistakenly believed that it's ok to chose any node in "Line A". So he'll chose a node at random. To make the situation worse, he thinks a "tree" should have the same number of edges and nodes! So this procedure becomes like that.

Let's define the variable totalCost. Initially the value of totalCost equal to 0. So, solve(t) (now t is a graph):

1. totalCost = totalCost + (size of t). The operation "=" means assignment. (Size of t) means the number of nodes in t.
2. Choose a node x in graph t at random (uniformly among all nodes of t).
3. Then delete x from graph t.
4. After that t becomes some connected components.
5. Apply solve on each component.

He'll apply solve on a connected graph with n nodes and n edges. He thinks it will work quickly, but it's very slow. So he wants to know the expectation of totalCost of this procedure. Can you help him?

在计算机科学中，有一种被称为“点分治”（Divide And Conquer By Node）的方法，用于解决树上关于路径的一些难题。我们通过如下函数来描述该方法的工作过程：

_solve_(_t_)（其中 _t_ 是一棵树）：

1. 在树 _t_ 中选取一个节点 _x_（通常选取重心）；我们将此步骤称为“第 A 行”。
2. 处理所有经过 _x_ 的路径。
3. 接着从树 _t_ 中删除 _x_。
4. 此后，_t_ 将分裂为若干棵子树。
5. 对每棵子树递归调用 _solve_。

当 _t_ 仅含一个节点时，该过程终止（因为删除该节点后，图中不再剩任何节点）。

现在，WJMZBMR 错误地认为：在“第 A 行”中任意选取节点都是可行的，因此他将随机选取一个节点。更糟糕的是，他还错误地认为“树”应当具有相同数量的节点与边！于是整个过程被改写如下：

我们定义变量 _totalCost_，其初始值为 0。此时 _solve_(_t_) 中的 _t_ 是一个图（而非树）：

1. _totalCost_ = _totalCost_ + (_size_ _of_ _t_)。此处 “=” 表示赋值操作；(_size_ _of_ _t_) 表示图 _t_ 中的节点数。
2. 在图 _t_ 中均匀随机地选取一个节点 _x_（即从 _t_ 的所有节点中等概率选取）。
3. 接着从图 _t_ 中删除 _x_。
4. 此后，_t_ 将分裂为若干个连通分量。
5. 对每个连通分量递归调用 _solve_。

他将对一个含有 n 个节点和 n 条边的连通图执行 _solve_。他以为该过程会很快，但实际上极其缓慢。因此，他希望知道该过程的 _totalCost_ 的期望值。你能帮他求出吗？

The first line contains an integer n (3 ≤ n ≤ 3000) — the number of nodes and edges in the graph. Each of the next n lines contains two space-separated integers a__i, b__i (0 ≤ a__i, b__i ≤ n - 1) indicating an edge between nodes a__i and b__i.

Consider that the graph nodes are numbered from 0 to (n - 1). It's guaranteed that there are no self-loops, no multiple edges in that graph. It's guaranteed that the graph is connected.

第一行包含一个整数 $n$（$3 \leq n \leq 3000$）—— 图中节点和边的数量。接下来的 $n$ 行中，每行包含两个用空格分隔的整数 $a_i$、$b_i$（$0 \leq a_i, b_i \leq n - 1$），表示节点 $a_i$ 和 $b_i$ 之间存在一条边。

假设图中节点编号为 $0$ 到 $n-1$。保证图中不存在自环，也不存在重边。同时保证该图是连通的。

Print a single real number — the expectation of totalCost. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

输出一个实数——即 totalCost 的期望值。只要您的答案的绝对或相对误差不超过 $10^{-6}$，即视为正确。

Consider the second example. No matter what we choose first, the totalCost will always be 3 + 2 + 1 = 6.

考虑第二个例子。无论我们首先选择哪一个，totalCost 始终为 $3 + 2 + 1 = 6$。