Having nearly completed their logging scheme, The Logging Company now wants to ship all logs collected at their logging station to some sawmills in the region. However, shipping logs with trucks costs money which can be better spent elsewhere (like in cutting more trees). To this end, The Company has devised a scheme where they will utilize the region's unique geography and abundant river networks for free shipping.
The geography of the land consists of some lakes and some rivers connecting them. Curiously, the latitudes of all the lakes are unique, and they are numbered from to from north to south. Even more strange are the facts that all the rivers between lakes only flow south, and there may be multiple rivers between the same two lakes. But thanks to this, logs the Company collects from up north can be moved south to their sawmills, for free!
The Logging Company has strategically built their collection point and sawmills next to lakes, the collection point being next to the lake numbered and one sawmill next to each lake with no river flowing south from it.
The Company has built more than one sawmill because free transportation comes with a degree of unpredictability. At any lake which doesn't have a sawmill next to it, a log may randomly flow down one river that leads south, with all possible southbound rivers being chosen with uniform probability. Knowing this, The Company would like to know how many resources to allocate to each sawmill, based on the probability of a log reaching that sawmill. For this, they've hired you to calculate the probability of a log from the collection point arriving at each sawmill.
First line: two space-separated integers and .
Next lines: two space separated integers and , representing a river flowing south from lake to lake . There will always be at least one river flowing south from lake .
For each sawmill, output the probability of a log reaching it as a real number . Your answer will be accepted as correct if it is within an absolute or relative error of no more than .
Sample Input 1
6 5 1 2 2 3 2 4 4 5 4 6
Sample Output 1
0.5 0.25 0.25
Explanation of Output for Sample Input 1
The given scheme can be represented by the following image.
A log starting at has a 1/2 chance of going into the sawmill at lake 3, and a 1/4 chance of reaching sawmills at lake 5 or 6.
Sample Input 2
5 4 1 2 1 3 2 4 3 4
Sample Output 2
Explanation of Output for Sample Input 2
The lake network may be disconnected. In Sample Input 2, lake 5 has no incoming rivers and no outgoing rivers. However, there is a sawmill on lake 5. No wonder the Logging Company is losing money!