Siege of Leningrad
By Marcio T. I. Oshiro, USP 
Brazil
By Marcio T. I. Oshiro, USP Brazil
The city of St. Petersburg was renamed after the Russian revolution in 1914 to Petrograd. After the death of Lenin, in tribute of the great leader the name of the city change again to Leningrad in 1924, and remained so until the end of the Soviet Union. In 1991, the city again had its old name. During second World War the city of Leningrad suffered a siege of the German troops that lasted about 900 days. It was a terrible time, a lot of hunger and loss of life, which ended on January 27, 1944 with the victory of the Soviets. It is considered one of the most costly victories in history in terms of lives lost.
At the height of the German offensive, in 1942, several snipers were scattered throughout city, including in some strategic points of the city more of a shooter waiting soldiers enemies. The Russian spy had detailed information of these skills shooters, but their hideouts were excellent, making the task of a Soviet soldier who wished to cross the city extremely difficult. The Soviet soldiers were well trained, but over time and the continued siege of the city, the best soldiers were being decimated, since if they missed the target at the first attempt were certainly killed by German soldiers in ambush.
Knowing the likelihood of a soldier killing a German sniper and also knowing the number of bullets he had at his disposal, we want to know the likelihood of that soldier to reach a strategic point of destination, from a strategic point of origin. The soldier, being very experienced, always wore a way that maximized the likelihood of success. Note that the soldier must kill all the gifts in the way shooters used, including those who are in strategic points of origin and destination.
The entry consists of various instances and ends with the end of file (EOF). The first line in each instance contains three integers N (2 ≤ N ≤ 1000), M, and K (0 ≤ K ≤ 1000) and the probability P (0 ≤ P ≤ 1) that the soldier killing a sniper. The integers N, M, and K represent respectively the numbers of strategic points, strategic roads connecting points and bullets loaded by Soviet soldier. The strategic points are numbered from 1 to N.
Each one of the next M lines contains a pair of integers i and j indicating that there is a road linking point i to j. Then there's a line containing an integer A, corresponding the number of shooters in town, followed by A integers indicating the position of each shot. The last line of each instance contains two integers indicating the starting point and the destination Soldier.
For each instance print a line containing the probability of success of the Soviet soldier. The probability must be printed with 3 decimal places.
| Sample Input | Sample Output |
|
3 2 10 0.1 |
0.000 |