Alan is bored, so he decided he would go for a walk through his mansion. Since Alan is a computer science expert, he modelled his mansion as a tree with nodes, where nodes are rooms and edges are corridors.
Since Alan is indecisive, he will use randomness to determine where he starts, and to where he proceeds from each room. Specifically:
He will generate an integer uniformly at random from to , and start at the node.
When standing in a room, Alan can choose to stop at this room or to go to any unvisited node adjacent to this room (he doesn't like to be repetitive). Out of all these choices, he will pick one uniformly at random. For example if there are adjacent unvisited nodes, he travels to each of them with a chance, and has a chance of stopping at the current node.
It can be proven that this process will always stop.
Alan now wants to know what the chance is that he will end up at each room from to , after the walk. Can you help him?
Input Specification
The first line will contain one integer , the number of rooms in Alan's mansion.
The next lines will contain integers and , indicating a corridor between rooms and .
It is guaranteed the input forms a tree.
Output Specification
On one line you are to print decimal numbers, the chance that Alan will end up in room for each . Your answer will be judged as correct if all of your values are within absolute error.
Subtasks
Subtask 1 (30%)
Subtask 2 (70%)
No further constraints.
Sample Input 1
3
1 2
2 3
Sample Output 1
0.36111111111 0.27777777778 0.36111111111
Sample Explanation
If we start at , there is a chance we stop at . Thus the chance of taking the walk (1) is .
If we start at , there is a chance we go to , from which there is a chance we stop at . Thus the chance of taking the walk is .
If we start at , there is a chance we go to , from which there is a chance we go to , from which we are guaranteed to stop. Thus the chance of taking the walk is .
If we start at , there is a chance we stop at . Thus the chance of taking the walk is .
If we start at , there is a chance we go to , from which we are guaranteed to stop. Thus the chance of taking the walk is .
If we start at , there is a chance we go to , from which we are guaranteed to stop. Thus the chance of taking the walk is .
If we start at , there is a chance we stop at . Thus the chance of taking the walk is .
If we start at , there is a chance we go to , from which there is a chance we stop at . Thus the chance of taking the walk is .
If we start at , there is a chance we go to , from which there is a chance we go to , from which we are guaranteed to stop. Thus the chance of taking the walk is .
Thus, the chance of stopping at is , the chance of stopping at is , and the chance of stopping at is .
Sample Input 2
5
1 2
2 3
3 5
2 4
Sample Output 2
0.22222222222 0.15555555556 0.17500000000 0.22222222222 0.22500000000
Comments