ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Internal Contest March'2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. By the Underground or by Foot?

Time limit: 1.0 second
Memory limit: 64 MB
Imagine yourself in a big city. You want to get from point A to point B. To do that you may move by foot or use the underground. Moving by the underground is faster but you may enter and exit it only at the stations. To save your time you decided to write a program to find the fastest route.

Input

The first line contains two floating point numbers. First of them is the speed of traveling by foot. The second one is the speed of traveling by the underground. Both speeds lie in limits from 0.5 to 10000. The second speed is always greater than or equal to the first one.
Then description of the underground follows. It starts with an integer N in the first line that is the number of the underground stations (2 ≤ N ≤ 200). The following N lines contain two floating point numbers each (i-th line contains the coordinates of i-th station). Then the description of the connections between stations follows. Each connection is determined by the pair of integers, i.e. by the numbers of connected stations. All connections in the list are different. There are no more than 400 connections. The list of connections is terminates with a pair of zeroes.
We assume that all underground connections are straight. So the time we need to travel between stations is equal to the distance between these stations divided by the speed of traveling by the underground. You may travel between connected stations to both directions. The time of traveling by foot between two points is equal to the distance between them divided by the speed of traveling by foot.
It should be mentioned also that entering and exiting the underground and changing trains are possible at the stations only and takes no time.
At last the coordinates of the points A and B are given, tha pair of coordinates in a line.

Output

The first line should contain the minimal time needed to get from the point A to the point B. Time should be given with the precision of 10−6. The second line describes the use of the underground while traveling. It starts with the number of visited stations with tha following list of visited stations in the order they should be visited.

Sample

inputoutput
1 100
4
0 0
1 0
9 0
9 9
1 2
1 3
2 4
0 0
10 10
10 0
2.6346295
4 4 2 1 3
Problem Author: Alexander Klepinin
Problem Source: USU Internal Contest, March 2002
To submit the solution for this problem go to the Problem set: 1205. By the Underground or by Foot?