CF839C.Journey

There are n cities and n - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads.

Theon and Yara Greyjoy are on a horse in the first city, they are starting traveling through the roads. But the weather is foggy, so they can’t see where the horse brings them. When the horse reaches a city (including the first one), it goes to one of the cities connected to the current city. But it is a strange horse, it only goes to cities in which they weren't before. In each such city, the horse goes with equal probabilities and it stops when there are no such cities.

Let the length of each road be 1. The journey starts in the city 1. What is the expected length (expected value of length) of their journey? You can read about expected (average) value by the link https://en.wikipedia.org/wiki/Expected_value.

七国境内有 $n$ 座城市和 $n-1$ 条道路，每条道路连接两座城市，且任意两座城市之间均可通过道路相互到达。

席恩与亚拉·葛雷乔伊共乘一匹马，从第 1 号城市出发，开始沿道路旅行。但当时大雾弥漫，他们无法看清马匹将带他们前往何处。每当马匹抵达一座城市（包括起点城市 1），它便会随机选择一个此前未曾访问过的、与当前城市直接相连的城市继续前进。这是一匹奇特的马：它绝不会返回已访问过的城市；在所有满足条件的可选城市中，它以相等的概率选择其中一个；当不存在任何满足条件的城市时，旅程即告终止。

设每条道路的长度均为 1。旅程始于第 1 号城市。求他们整个旅程的期望长度（即路径总长度的期望值）。关于期望值（平均值）的定义，请参阅链接：https://en.wikipedia.org/wiki/Expected_value。

The first line contains a single integer n (1 ≤ n ≤ 100000) — number of cities.

Then n - 1 lines follow. The i-th line of these lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — the cities connected by the i-th road.

It is guaranteed that one can reach any city from any other by the roads.

第一行包含一个整数 $n$（$1 \leq n \leq 100000$）—— 城市的数量。

接下来是 $n - 1$ 行。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$）—— 表示由第 $i$ 条道路连接的两座城市。

保证通过道路可以从任意一座城市到达其他任意一座城市。

Print a number — the expected length of their journey. The journey starts in the city 1.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

输出一个数字——即他们旅程的期望长度。旅程从城市 1 开始。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

具体而言：假设你的答案为 $a$，评测组的答案为 $b$。当满足 时，评测程序将判定你的答案正确。

In the first sample, their journey may end in cities 3 or 4 with equal probability. The distance to city 3 is 1 and to city 4 is 2, so the expected length is 1.5.

In the second sample, their journey may end in city 4 or 5. The distance to the both cities is 2, so the expected length is 2.

在第一个样例中，他们的旅程可能以相等的概率在城市 3 或城市 4 结束。到城市 3 的距离为 1，到城市 4 的距离为 2，因此期望长度为 $1.5$。

在第二个样例中，他们的旅程可能在城市 4 或城市 5 结束。到这两个城市的距离均为 2，因此期望长度为 $2$。