Fading Flower

Consider a connected tree with n nodes (called petals) and n − 1 edges. In this tree the petals are connected arbitrarily. As spring departs, the petals on the tree begin to wither. Specifically, every day one edge is chosen uniformly at random among the remaining (uncut) edges and is removed. The flower is said to have withered once every petal (node) has degree at most 2 (i.e. no petal is incident to more than 2 remaining edges).

Task. Given the tree, determine the expected number of days until the flower withers.

Explanation.
A node with degree ≤ 2 already satisfies the condition. For a node v with degree d (d ≥ 3) the condition is met only after at least d − 2 of the edges incident on v have been removed. Since the process consists of a random permutation of the n − 1 edges, one may show that the day on which node v becomes "satisfied" is exactly the (d − 2)-th smallest removal time among the d incident edges. The flower withers when every node is satisfied – that is, when the maximum (over nodes) of these special order statistics is reached. Your task is to compute the expectation of this number.

Note. It can be shown that the answer can be written as a real number. For the purposes of this problem, it is guaranteed that n is small (n ≤ 10) so that an exact computation via enumeration over all subsets of removed edges is feasible.

inputFormat

The input begins with a single integer n (1 ≤ n ≤ 10), the number of petals (nodes). Then follow n − 1 lines, each containing two integers u and v (1 ≤ u, v ≤ n) which indicate that there is an edge connecting node u and node v.

outputFormat

Output a single real number – the expected number of days until the flower withers. Answers within an absolute or relative error of 1e−6 will be accepted.

sample

4
1 2
1 3
1 4

1.000000