No submission language available for this problem.

题目描述

在一个古老而神秘的王国里，有一座高耸入云的山峰，名为“迷雾山”。迷雾山山势陡峭，山路蜿蜒曲折，许多勇士曾试图攀登迷雾山，但无一不是在山路崎岖中迷失了方向，最终被迷雾山深处的可怕生物所吞噬。

为了让更多的勇士能够安全地攀登迷雾山，国王特地派遣了你和你的团队前往迷雾山进行探险和地图绘制。在探险中，你们发现山中有许多隐藏的洞穴和秘密通道，这些通道之间的距离可以用平面上两点之间的直线距离来表示。为了让攀登迷雾山的勇士能够更加顺利地通过这些通道，你们需要编写一个程序，用于计算任意两个洞穴的最短路径长度。

迷雾山里面有 $n$ 个洞穴，其中的一些洞穴之间有 $m$ 条通道。

如果两个洞穴之间有通道，则表示这两个洞穴之间可以到达，通路的距离为两洞穴间的直线距离。现在的任务是找出从一个洞穴到另一个洞穴之间的最短路径。

注意：这里的每个洞穴有一个唯一的编号和坐标，编号从 $1$ ~ $n，n ≤ 100$。每个洞穴的横纵坐标均在 $-10000$ ~ $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

limitations

编号 $1$ ~ $n，n ≤ 100$

每个洞穴的坐标均在 $-10000$ ~ $10000$ 之间。