Problem Description

One day, WJMZBMR learned a magical algorithm: centroid decomposition on a tree.

The core idea of this algorithm is as follows:

time = 0
Solve(Tree a) {
  time += a.size;
  if (a.size == 1) return;
  else {
    select x in a;
    delete a[x];
  }
}

Time cost = 0
Solve(tree a)
  Time cost += size of a
  If there is only 1 node in a
    Exit
  Otherwise
    Choose a node x in a
    Delete node x from a

Then $a$ becomes several smaller trees, and Solve is called recursively on each subtree.

We notice that the time complexity of this algorithm is closely related to the chosen node $x$. If $x$ is the centroid of the tree, then the time complexity is $O(n \log n)$.

WJMZBMR decides to choose a node in $a$ uniformly at random as $x$. Sevenkplus tells him that the worst-case complexity of doing this is $O(n^2)$, but WJMZBMR does not believe it. So Sevenkplus spent a few minutes writing a program to prove it. You can try it too.

Now you are given a tree. Can you tell WJMZBMR the expected time cost of his algorithm (using the definition in the given Solve function as the standard)?

Input Format

The first line contains an integer $n$, the size of the tree. The next $n-1$ lines each contain two integers $a, b$, meaning there is an edge between $a$ and $b$.

The nodes of the tree are numbered starting from $0$.

Output Format

Output one line with a floating-point number, the answer rounded to $4$ digits after the decimal point.

3
0 1
1 2

5.6667

Hint

For all testdata, it is guaranteed that $1\leq n\leq 30000$.

Translated by ChatGPT 5