Second Shortest Path for Wildcat's Birthday

Wildcat, known for his poor sense of direction, always ends up late to gatherings. Fortunately, he can consult Flower to get a route. Given a set of points representing locations and a set of roads (edges) connecting some pairs of these points, Wildcat will normally take the shortest route from his starting point (the first point) to the meeting point (the last point). However, if for some reason the shortest route is not available, he wants to take the second shortest route. In this problem, the second shortest path must be a simple path (i.e. no road is used more than once), even if reusing roads might yield a shorter overall distance.

Each point is given as its coordinates in the plane. The weight of each road is the Euclidean distance between the two connected points. More formally, for two points with coordinates \((x_1, y_1)\) and \((x_2, y_2)\) the road length is defined as \[ d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}. \]

Your task is to find the length of the second shortest path from the start (point 0) to the destination (point n-1). If no such path exists, output -1.

inputFormat

The first line contains two integers n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000) representing the number of points and the number of roads respectively.

The next n lines each contain two integers x and y (|x|,|y| ≤ 10,000) representing the coordinates of each point. The first point (index 0) is the starting point and the last point (index n-1) is the destination.

The following m lines each contain two integers u and v (0 ≤ u, v < n, u \(\neq\) v) indicating that there is an undirected road connecting point u and point v. It is guaranteed that there is at least one path from 0 to n-1.

outputFormat

Output a single number: the length of the second shortest simple path from point 0 to point n-1. If no such path exists, output -1.

sample

4 4
0 0
1 0
1 1
2 1
0 1
1 2
0 2
2 3

3.000000