Problem Description

Score: $ 800 $ points
You are given a connected graph with $ N $ vertices and $ N-1 $ edges, which is a "tree". Edge $ i $ connects vertex $ u_i $ and $ v_i $.
E869120 repeats the following operation until it can no longer be performed:

• Move to an adjacent vertex. However, you cannot pass through the same vertex twice.
• If there are no vertices to move to, the operation ends.
• The destination is chosen randomly with equal probability. That is, if there are $ p $ vertices to move to next, each vertex is chosen with a probability of $ 1/p $.

Calculate the expected number of moves for E869120 when starting at each vertex $ i $.

5
1 2
2 3
3 4
4 5

```

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

 ```

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

```

2
1 2

## Input Format

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

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

## Output Format

- On the $ i $-th line, output the expected number of moves when starting from vertex $ i $.
- The absolute or relative error must be within $ 10^{-6} $.

## Sample Input and Output

### Sample Input #1

4
1 2
2 3
2 4

### Sample Output #1

2.0
1.0
2.0
2.0

### Sample Input #2

None

### Sample Output #2

3.0
1.5
3.0
1.5

### Sample Input #3

None

### Sample Output #3

4.0
2.0
2.0
2.0
4.0

### Sample Input #4

None

### Sample Output #4

2.000000000000
1.666666666667
1.666666666667
3.000000000000
3.000000000000
3.000000000000
3.000000000000

### Sample Input #5

None

### 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

None

### Sample Output #6

1.0
1.0
```

Notes/Hints

Constraints

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

Subtasks

Subtask 1 \[ $ 190 $ points \]

• The given graph is linear. That is, no vertex has more than $ 2 $ edges.

Subtask 2 \[ $ 220 $ points \]

• $1 \le N \le 1000$

Subtask 3 \[ $ 390 $ points \]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分