Mira is exploring an ancient kingdom whose $n$ rooms are connected by $n-1$ corridors. Every room is reachable from every other room, so the corridors form a tree. The rooms are numbered from $1$ to $n$, and Mira begins in room $1$.

Mira records each room's number the first time she visits it. From every room, she explores its children in a uniformly random order: every permutation of the children is equally likely. The random orders chosen at different rooms are independent.

More precisely, Mira performs the following procedure on the tree rooted at room $1$:

DFS(v):
    append v to p
    shuffle the children of v uniformly at random
    for each child u of v, in that order:
        DFS(u)

After the procedure finishes, the recorded sequence $p$ is a permutation of the integers from $1$ to $n$.

An inversion is a pair of positions $(i,j)$ such that $1 \le i < j \le n$ and $p_i > p_j$.

Find the expected number of inversions in the resulting permutation.

It can be shown that the answer is always an integer or an integer plus $0.5$. Print the exact answer with one digit after the decimal point.

Input

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) --- the number of rooms.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$), representing a corridor between rooms $u$ and $v$.

It is guaranteed that the corridors form a tree, rooted at vertex $1$.

Output

Print the expected number of inversions in the DFS permutation, with exactly one digit after the decimal point.

Example

stdin

4
1 3
3 2
3 4

stdout

1.5

Note

In the example, the only possible DFS orders are $(1, 3, 2, 4)$ and $(1, 3, 4, 2)$. The first one has $1$ inversion: $3 > 2$. The second one has $2$ inversions: $3 > 2$ and $4 > 2$. As these two orders are equally likely, the expected number of inversions is $\frac{1 + 2}{2} = 1.5$.