Contest Duration: ~ (local time)
D - Driving on a Tree

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score: $800$ Points

### Problem Statement

There is an undirected connected graph with $N$ vertices and $N-1$ edges. The i-th edge connects u_i and v_i.

E869120 the coder moves in the graph as follows:
• He move to adjacent vertex, but he can't a visit vertex two or more times.
• He ends move when there is no way to move.
• Otherwise, he moves randomly. (equal probability) If he has $p$ way to move this turn, he choose each vertex with $1/p$ probability.
Calculate the expected value of the number of turns, when E869120 starts from vertex i, for all i (1 ≤ i ≤ N).

### Input

The input is given from standard input in the following format.

N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}


### Output

In i-th (1 ≤ i ≤ N) line, print the expected vaule of the number of turns E869120 moves.
The relative error or absolute error of output should be within 10^{-6}.

### Constraints

• $1 \le N \le 150,000$
• The graph is connected.

Subtask 1 [ $190$ points ]

• There is no vertex which degree is more than 2.
• This means the graph looks like a list.

Subtask 2 [ $220$ points ]

• 1 ≤ N ≤ 1000.

Subtask 3 [ $390$ points ]

• There are no additional constraints.

### Sample Input 1

4
1 2
2 3
2 4


### Sample Output 1

2.0
1.0
2.0
2.0


### Sample Input 2

4
1 2
2 4
4 3


### Sample Output 2

3.0
1.5
3.0
1.5


### Sample Input 3

5
1 2
2 3
3 4
4 5


### Sample Output 3

4.0
2.0
2.0
2.0
4.0


### Sample Input 4

7
1 2
1 3
2 4
2 5
3 6
3 7


### Sample Output 4

2.000000000000
1.666666666667
1.666666666667
3.000000000000
3.000000000000
3.000000000000
3.000000000000


### Sample Input 5

12
1 2
2 3
2 4
4 5
5 6
5 7
6 8
8 9
2 10
10 11
11 12


### Sample Output 5

3.666666666667
2.250000000000
3.666666666667
2.833333333333
2.555555555556
2.666666666667
4.333333333333
2.666666666667
5.333333333333
2.500000000000
2.500000000000
5.000000000000


### Sample Input 6

2
1 2


### Sample Output 6

1.0
1.0


### 問題文

$N$頂点$N-1$辺の連結であるグラフ、つまり、「木」が与えられます。辺 i は頂点 u_iv_i を結んでいます。
E869120は以下のような操作を行えなくなるまで繰り返します。
• 隣り合った頂点に動く。ただし、同じ頂点を2度通ってはいけない。
• 動ける頂点がない場合、そこで操作は終了となる。
• どこに動くかは等確率にランダムに選ぶ。つまり、次に動ける頂点が$p$個である場合、それぞれの頂点に$1/p$の確率で動くことになる。

### 入力

N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}


### 出力

• $i$行目に、頂点$i$から出発した場合の動く回数の期待値を出力しなさい。
• ただし、絶対誤差もしくは相対誤差は$10^{-6}$以内でなければなりません。

### 制約

• $1 \le N \le 150,000$
• 与えられるグラフは連結である。

### 小課題

• 与えられるグラフは線のようになっている。つまり、どの頂点からも辺が$3$本以上出ていることはない。

• $1 \le N \le 1000$

• 追加の制約はない。

### 入力例1

4
1 2
2 3
2 4


### 出力例1

2.0
1.0
2.0
2.0


### 入力例2

4
1 2
2 4
4 3


### 出力例2

3.0
1.5
3.0
1.5


### 入力例3

5
1 2
2 3
3 4
4 5


### 出力例3

4.0
2.0
2.0
2.0
4.0


### 入力例4

7
1 2
1 3
2 4
2 5
3 6
3 7


### 出力例4

2.000000000000
1.666666666667
1.666666666667
3.000000000000
3.000000000000
3.000000000000
3.000000000000


### 入力例5

12
1 2
2 3
2 4
4 5
5 6
5 7
6 8
8 9
2 10
10 11
11 12


### 出力例5

3.666666666667
2.250000000000
3.666666666667
2.833333333333
2.555555555556
2.666666666667
4.333333333333
2.666666666667
5.333333333333
2.500000000000
2.500000000000
5.000000000000


### 入力例6

2
1 2


### 出力例6

1.0
1.0