Представьте себя в большом городе. Вы хотите попасть из точки A в точку B. Для этого вы можете идти пешком или использовать метро. Перемещение с помощью метро быстрее, но входить в метро и выходить из него можно только на станциях. Чтобы сэкономить время, вы решили написать программу нахождения самого быстрого пути.

Первая строка содержит два вещественных числа: скорость ходьбы и скорость перемещения с помощью метро. Скорости лежат в пределах от 0.5 до 10000. Вторая скорость всегда не меньше первой.

Затем следует описание метро. В первой строке описания находится целое число N — количество станций метро (2 ≤ N ≤ 200). Следующие N строк содержат по два вещественных числа каждая (i-я строка содержит координаты i-й станции). Затем следует описание соединений между станциями. Каждое соединение определяется парой целых чисел — номерами соединённых станций. Соединения в списке не повторяются. Общее количество соединений не превышает 400. Список соединений завершает пара нулей.

Можно считать, что станции соединяются по прямой, так что время перемещения между станциями равно расстоянию между ними, делённому на скорость перемещения с помощью метро. Перемещаться между станциями можно в любую сторону. Время перемещения пешком между двумя точками равно расстоянию между ними, делённому на скорость ходьбы.

Отметим, что вход и выход из метро, а также смена поезда возможны только на станциях и не требуют дополнительного времени.

Последними даны координаты точек A и B по паре координат в строке.

Первая строка должна содержать минимальное время, необходимое, чтобы попасть из точки A в точку B. Время должно быть выведено с точностью 10⁻⁶. Вторая строка описывает использование метро при передвижении. Она начинается количеством станций, которые нужно посетить, затем следует список номеров станций в порядке, в котором их нужно посетить.