U219730 瓜皮旅行团(初级)

为了参加“瓜皮自有黄金屋”比赛，瓜皮们都十分拼命，导致大家都非常的劳累与辛苦。小杨(原名“ziruiya”)作为一名有素质的赛事主办方，十分理解各位瓜皮的辛苦，于是决定带大家到全世界的瓜皮景点散散心。

小杨从抽屉中取出了一张瓜皮地图。 地图上有 $n$ 个瓜皮景点 （$n\le100$） ，每个景点的坐标均在 $(0,0)$ $\sim$ $(10000,10000)$ 之间。其中的一些景点之间有通路。 若有通路，则表示可从一个景点到达另一个景点，即两个景点间有双向路，通路的距离为两个景点间的直线距离。 现在的任务是找出从一个景点到另一个景点之间的最短路径。 由于小杨被要求马上写出方案，又不想浪费太多内存（其实电脑只剩下 $1$ MB内存），所以请你在 $10ms$ 的时间和 $1$MB 的内存下完成。

共 $n+m+q+3$ 行，其中: 　　第一行为整数 $n$ 。 　　第 $2$ 行到第 $n+1$ 行（共 $n$ 行） ，每行两个整数 $x$ 和 $y$ ，描述了一个景点的坐标。 　　第 $n+2$ 行为一个整数 $m$ ，表示地图中通路的个数。 　　此后的 $m$ 行，每行描述一条通路，由两个整数 $i$ 和 $j$ 组成，表示第 $i$ 个景点和第 $j$ 个景点之间有通路。 　　第 $n+m+3$ 行为一个整数 $q$ 。 　　最后 $q$ 行，每行两个整数 $s$ 和 $t$ ，分别表示从第 $s$ 个景点出发，第 $t$ 个景点结束。

共 $q$ 行，每行一个实数（保留两位小数），表示对于每一组数据，从第 $s$ 个景点到第 $t$ 个景点的最短路径长度。 如果结果大于 $2147483647$ 或无法到达，输出 “$Nonsense!$”。

$1 ≤ n ≤ 100$ $1 ≤ m ≤ 5050$ $1 ≤ q ≤ 1000000$ $1 ≤ s,t ≤ n$ ### 本题为[yzc20100218](https://www.luogu.com.cn/user/510713)原创，未经允许，禁止改编、套用