题目描述

Caesar远征高卢回来后，对你大加赞赏，他亲自来到Genoa视察。

Genoa在你的建设下变得无比繁荣，由于财政收入的增加，你为城市修建了交通系统。古罗马的交通系统由两部分组成——Dirt Road和Rome Road。两个路口间只可能是其中一种道路。在Rome Road上可以驾驶马车，而在Dirt Road上则不行。由于修建道路是一项浩大的工程，使得你无法将整个城市用Rome Road连接起来。

现在Caesar已经到达码头，他要求去你家参观。Caesar由一个癖好，喜欢坐车而不喜欢走路。所以Caesar走Dirt Road时的不满值要比走Rome Road时大。

为了不让Caesar过于不满而罢免你的职位，请设计路线使得Caesar的不满值最小。

输入格式

输入数据第一行有两个实数，分别表示走Dirt Road和Rome Road一个单位长度时Caesar的不满值。接下来是一个整数N（N<=1000），代表路口总数。接下来有N行，每行一组实数(x,y)分别描述这N个路口的坐标。接下来有若干行，每行一组整数（i,j），表示第i个路口与第j个路口间为Rome Road，以0 0结束。最后两行，每行一对实数，分别描述码头和你家的坐标。

输出格式

输出Caesar从码头到你家的最小不满值，保留4位小数

100.0 2.0
2
1.0 0.0
2.0 1.0
1 2
0 0
0.0 0.0
2.0 2.0

202.8284