问题描述

上白泽慧音为了让寺子屋评上乡文明单位，决定对她的学生进行家访。

我们把这些地点抽象成 $n$ 个点，有 $n-1$ 条无向边连接这些点，且保证这些点两两可达。寺子屋在第 1 号点。慧音从寺子屋开始移动。每次移动，她会等概率地选择一个跟她当前处在的点相连的并且没有走过的点，然后移动到那里。

假设每条边的长度是 1，请你告诉慧音，她家访的期望移动距离是多少。

如果你不知道什么是期望，请搜索“数学期望”。

输入格式

第一行一个整数 $n$，代表点的数量。

下来 $n$ 行每行两个整数 $u,v$，代表点 $u$ 和点 $v$ 之间有一条无向边。

输出格式

一个小数，是慧音家访的期望移动距离。

样例一

input

4
1 2
1 3
2 4

output

1.500000

样例二

input

5
1 2
1 3
3 4
2 5

output

2.000000

数据范围与约定

对于 $100\%$ 的数据，$n \leq 100000$。

你的答案会被接受当且仅当你的答案和标准答案误差小于 $10^{-5}$。

时间限制： $1\mathrm{s}$

内存限制： $256\mathrm{MB}$

来源

cf 839c