While decorating her house for Diwali, Anne noticed a rice light shaped like a rooted tree. We represent the lighting elements as the vertices of the tree and the wires that connect them as the edges. It was hanging from a firm support on the ceiling which we call the root of the rice light. The vertices are numbered to with as the root.
The probability of any wire breaking is directly proportional to its distance from the support. The distance of a wire joining lighting elements and is considered as the maximum of the distance of or from the support (root).
If a wire breaks, the portion of the rice light that got disconnected from the support shatters on the floor, while the other portion remains intact and still hanging from the ceiling.
This image illustrates the case where the wire joining lighting elements and breaks. In this case, three elements (, , ) shatters and four elements (, , , ) remain connected to the ceiling.
Given that exactly one of the wires randomly breaks, find the expected number of vertices still connected to the ceiling.
Input Format
The first line contains a single integer denoting the number of vertices in the tree. The vertices are numbered to , with as the root.
The next lines each contains two space-separated integers and denoting that there is an edge between vertex and .
Constraints
- It is guaranteed that the graph is a tree.
Output Format
Print a single line containing a single real number denoting the answer. Your answer is considered correct if its absolute error doesn't exceed .
Sample Input 0
3
1 2
1 3
Sample Output 0
2.0000000000
Explanation 0
Since there are only two edges and both are the same distance from the root, each edge breaks with the same probability. In both cases, the size of the remaining tree containing the root is . Therefore, the expected size is .
Sample Input 1
7
1 2
1 3
2 4
2 5
3 6
3 7
Sample Output 1
5.6000000000
Explanation 1
This is a full binary tree. The figure in the problem statement illustrates it.