描述

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