【题目描述】
平面上有 $ n $ 个点( $ n<=100 $ ),每个点的坐标均在 $ -10000 \sim 10000 $ 之间。
其中的一些点之间有连线。
若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。
现在的任务是找出从一点到另一点之间的最短路径。
【输入】
共 $ n+m+3 $ 行,其中:
第一行为整数 $ n $ 。
第 $ 2 $ 行到第 $ n+1 $ 行(共 $ n $ 行) ,每行两个整数 $ x $ 和 $ y $ ,描述了一个点的坐标。
第 $ n+2 $ 行为一个整数 $ m $ ,表示图中连线的个数。
此后的 $ m $ 行,每行描述一条连线,由两个整数 $ i $ 和 $ j $ 组成,表示第 $ i $ 个点和第 $ j $ 个点之间有连线。
最后一行:两个整数 $ s $ 和 $ t $ ,分别表示源点和目标点。
【输出】
一行,一个实数(保留两位小数),表示从 $ s $ 到 $ t $ 的最短路径长度。
【输入样例】
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