#D. 迷阵突围

    Type: Default 1000ms 256MiB

迷阵突围

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

阿Q陷入了坐标系上的一个迷阵,迷阵上有 n 个点,编号从 1 到 n。阿Q在编号为 1 的位置,他想到编号为 n 的位置上。

阿Q当然想尽快到达目的地,但是他觉得最短的路径可能有风险,所以他会选择第二短的路径。现在阿Q知道了 n 个点的坐标,以及哪些点之间是相连的,他想知道第二短的路径长度是多少。

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

输入格式

第一行输入两个整数 n(1n200)n (1\leq n\leq 200 ) 和 m,表示一共有 n 个点和 m 条边。

接下来输入 n 行,每行输入两个整数 xi,yi(500xi,yi500)x_i, y_i (-500\leq x_i,y_i\leq 500),代表第 i 个点的坐标。

接下来输入 m 行,每行输入两个整数 pj,qj(1pj,qjn)p_j, q_j (1\leq p_j,q_j\leq n),表示点 pjp_j 和点 qjq_j 之间相连。

输出格式

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

输出时每行末尾的多余空格,不影响答案正确性

要求使用「文件输入输出」的方式解题,输入文件为 marsh.in,输出文件为 marsh.out

样例输入

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

样例输出

2.41

周六1430+1830

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
4
Start at
2023-12-3 9:00
End at
2023-12-3 18:00
Duration
9 hour(s)
Host
Partic.
8