2663 - 抢鸡蛋

老太太经常去市场抢鸡蛋。市场里有 n(n ≤ 100)个摊位,每个摊位的坐标均在 -10000 至 10000 之间。市场中有 m 条路连接摊位。如果有一条路,则表示可以从一个摊位走到另一个摊位,路的距离为两点间的直线距离。现在老太太要找出从一个摊位到另一个摊位之间的最短距离。你能帮老太太算出吗?

输入

n+m+3 行:

第一行:整数 n

接下来 n 行:每行两个整数 xy,描述了一家店的坐标。

接下来一行:整数 m

接下来 m 行:每行描述一条通路,由两个整数 ij 组成,表示第 i 家店和第 j 家店之间有通路。

接下来一行:两个整数 st,分别表示原点和目标店。

输出

仅一行:一个实数(保留两位小数),表示从 st 的最短路径长度。

样例

输入

5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5

输出

3.41

提示

对于 100 \% 的数据:2 \le n \leq 1001 \le i, j, s, t \le n1 \le m \leq 1000

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题