迷阵突围

迷阵突围

描述

Tony老师陷入了坐标系上的一个迷阵,迷阵上有n个点,编号从1到n。Tony在编号为1的位置,他想到编号为n的位置上。Tony当然想尽快到达目的地,但是他总是想得太多,觉得最短的路径可能有风险,所以他会选择第二短的路径(在平坦的路面上曲折前行)。现在Tony知道了n个点的坐标,以及哪些点之间是相连的,他想知道第二短的路径长度是多少。

注意,每条路径上不能重复经过同一个点。

格式

输入

第一行输入两个整数n (1 ≤ n ≤ 200) 和m,表示一共有n个点和m条边。
接下来输入n行,每行输入两个整数xi和yi (-500 ≤ xi、yi ≤ 500),分别表示代表第i个点的坐标。
接下来输入m行,每行输入两个整数pj和qj (1 ≤ pi、qi ≤ n)表示点pj和点qj之间相连。

输出

输出一行,输出包含一个数,表示第二短的路径长度(小数点后面保留两位),如果第一短路径有多条,则答案就是第一最短路径的长度;如果第二最短路径不存在,则输出−1。

格式

输入

3 3
1 1
2 2
3 2
1 2
2 3
1 3

输出

2.41

信息

难度
9
分类
(无)
标签
(无)
递交数
4
已通过
2
通过率
50%
上传者