Expected Time of Random Tree Division

Given an undirected tree with (n) vertices, WJMZBMR uses the following recursive algorithm to process the tree:

[ \texttt{Solve(Tree (a)):\ \quad time \mathrel{+}= |a|\ \quad if ; |a| = 1:\ \quad\quad return\ \quad else:\ \quad\quad choose a vertex (x \in a) uniformly at random\ \quad\quad delete vertex (x) from (a) ]

After deleting (x), the tree splits into several connected components. The algorithm is then recursively applied to each component. The algorithm’s cost is the sum of the sizes of the trees processed at every step (i.e. the value added to (time) at each invocation of (Solve)).

It can be shown that the expected total cost of the algorithm is exactly

[ E = \sum_{v \in V};\sum_{u \in V} \frac{1}{d(u,v) + 1}, ]

where (d(u,v)) denotes the distance (the number of edges) between vertices (u) and (v) in the tree.

Your task is to compute and output (E) for a given tree. The answer will be accepted if its absolute or relative error does not exceed (10^{-6}).

inputFormat

The first line contains an integer (n) (1 (\le) (n) (\le) 2000) denoting the number of vertices in the tree. The vertices are numbered from 1 to (n).

Each of the next (n-1) lines contains two integers (u) and (v) (1 (\le) (u,v) (\le) (n)) denoting an edge between vertices (u) and (v). It is guaranteed that the given graph is a tree.

outputFormat

Output a single line containing the expected time consumption (E) of the algorithm. Your answer is considered correct if its absolute or relative error does not exceed (10^{-6}).

sample

1

1.000000