Autopilot System

Farmer John has just purchased a car equipped with an autopilot system. He is so excited about this high-tech product and can’t wait to try it. John plans to travel to another city this weekend, so he decides to let the autopilot system lead the way.

There are $N$ cities numbered from 1 to $N$ inclusively. John lives in city 1 and he plans to travel to city $N$. The cities are connected by $N-1$ highways. Any two cities are reachable to each other via the highways. Every time John passes through a high way, he needs to pay 1 unit of money as the toll fee.

Obviously, such a road system is very busy, since there is only one path between two cities. To solve this problem, $M$ cities are selected as transport hubs. For each city $i$ (including the hubs), $M$ new one-way roads are constructed, each of which allows travelling from city $i$ to one of the hubs, but travelling from the hub back to the city is not allowed. More importantly, they are free of charge!

Now Farmer John has started the autopilot system, waiting for it to lead him from city 1 to city $N$. Unfortunately, something goes wrong with its software, so it would pilot at random. When the car is located in a city, the system will pick the next destination as the following. For the $i-th$ transport hub, the system will select it as the next destination with probability $q_i$, and travel to the hub via the free one-way road. If none of the transport hubs is selected, it drives the car to one of the neighboring city through a highway with uniform probability. In other words, denoting the sum of $q_i$ as $Q$ and the city has $K$ neighbors, the probability of traveling to one of the neighboring cities is $\frac{(1-Q)}{K}$. The only good news is that the system will stop piloting immediately when the car arrives in city $N$.

Farmer John is aware of this malfunctioning now. He wants to know the expected amount of money that he needs to pay for the toll fee, if he lets the car travel at random as described above.

The first line of input contains a number $T$ indicating the number of test cases ($T≤150$).

Each test case starts with a line containing two integers $N$ and $M$ ($2≤N≤20000,0≤M≤200$). The $i-th$ of the next $M$ lines contains two numbers $u_i$ and $q_i$, indicating that $u_i$ is a transport hub and the probability of travelling to it from any city is $q_i$. It is guaranteed that all transport hubs are distinct and the sum of $q_i$ is not greater than 1. Each of the next $N-1$ lines contains two integers $x$ and $y$, indicating that there is a highway between city $x$ and city $y$.

For each test case, output a single line consisting of “Case #X: Y”. $X$ is the test case number starting from 1. $Y$ is the expected units of money that is payed as toll fee. Your answer is considered correct if either of its relative error or absolute error is less than $10^{-6}$. If it is impossible to travel to city N, you should output “impossible” instead.

3
6 3
2 0.2
3 0.3
4 0.1
1 2
1 3
2 4
2 5
2 6
6 3
1 0.2
3 0.1
6 0.1
1 2
1 3
2 4
2 5
2 6
3 2
1 0.5
2 0.5
1 2
1 3

Case #1: 13.176471
Case #2: 4.694250
Case #3: impossible

2015ACM/ICPC亚洲区合肥站-重现赛（感谢中科大）