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 (1\leq n\leq 200 )$ 和 m，表示一共有 n 个点和 m 条边。

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

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

输出格式

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

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

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

样例输入

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

样例输出

2.41