Maze

Limits: 4 sec., 1024 MiB

This statement was translated automatically from Ukrainian.

Zenyk is in a maze, which can be represented as a tree with \(n\) vertices and \(n - 1\) edges, where vertices are rooms and edges are passages between them. From each room, it is possible to reach any other room using the passages. Vertex \(1\) is the exit from the maze, which Zenyk wants to reach as quickly as possible.

Every second, all edges independently and equiprobably receive a new orientation. For each edge between two adjacent vertices \(u\) and \(v\), the edge becomes oriented either from \(u\) to \(v\) or from \(v\) to \(u\), with a probability of \(\frac{1}{2}\) each. Edges are never bidirectional; they are always oriented in only one direction.

After the edge orientations change, Zenyk knows the current orientation of all edges and decides on his next move in order to minimize the expected time to reach vertex \(1\).

Zenyk acts as follows:

• If from his current vertex \(v\) there is at least one edge oriented from \(v\) to an adjacent vertex \(u\), he must choose one of such vertices and move to it. The movement takes \(1\) second.

• If there are no outgoing edges from vertex \(v\), Zenyk is forced to wait \(1\) second until the next edge reorientation.

The edge orientations change every second, right before Zenyk makes a decision about his next move.

Your task is to help Zenyk determine for each vertex \(v\) (\(2 \leq v \leq n\)) the mathematical expectation of the time (in seconds) required to reach vertex \(1\), starting from vertex \(v\), assuming that he acts optimally to minimize this time.

Input

The first line contains a single integer \(n\) — the number of vertices in the tree.

The \(i\)-th of the next \(n-1\) lines contains two integers \(u_i\) and \(v_i\), meaning that there is an edge between the vertices with these indices.

Output

Output \(n - 1\) numbers. The \(k\)-th number in the line should represent the mathematical expectation for vertex \(k + 1\).

The answer will be accepted if its absolute or relative error does not exceed \(10^{-7}\).

Constraints

\(2 \le n \le 2 \cdot 10^5\),

\(1 \le u_i, v_i \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 2 2 3 2 4	3.5000000000 5.5000000000 5.5000000000

Input (stdin) сopy	Output (stdout) сopy
2 1 2	2.0000000