Description

Every time there is a big hangout, everyone gets together no matter if it is at Haoledi, Bifengtang, or Tangmuxiong, and we all have a blast. We still remember Xinyu and Hua'er’s passion and release on the dance machine, remember how amazing Caocao’s basketball shooting was, remember how Gougou’s aim was always S... and we must not forget that Pangzi’s singing always made us scream in surprise!

Today is Wildcat’s birthday, so it’s normal to think of all this. It’s just a school day, so we can’t go out together. But recalling those sweet times is still a kind of happiness.

However, every time we meet up, there is a problem! Wildcat is a recognized “road-blind” person. Wildcat knows this well, always leaving early, yet still often arriving late, which leaves everyone helpless. Later, before each trip, Wildcat would consult Hua'er about the route. Based on known routes, he could finally arrive on time.

Now here is the problem: given the coordinates of $n$ points, where the first one is Wildcat’s starting position and the last one is the group’s meeting position, and given which positions are connected. From the start to the meeting point, Wildcat will always choose a shortest route. If Wildcat does not find the shortest route, he will take the second-shortest route. Please help Wildcat find the length of this second-shortest path.

In particular, the chosen second-shortest path will not visit the same vertex more than once, even if allowing repeated visits to the same vertex could make it shorter.

Input Format

The first line contains two integers $n$ ($1 \le n \le 200$) and $m$ ($1 \le m \le 10000$), indicating there are $n$ points and $m$ roads in total. The next $n$ lines each contain two numbers $x_i$, $y_i$ ($-500 \le x_i, y_i \le 500$), representing the coordinates of the $i$-th point. The following $m$ lines each contain two integers $p_j$, $q_j$ ($1 \le p_j, q_j \le n$), indicating that there is a road between these two points. There are no multiple edges in the testdata; self-loops may exist.

Output Format

Output a single line containing one number: the distance of the second-shortest route (keep two decimal places). If there are multiple shortest paths, then the answer is the shortest-path length. If no second-shortest path exists, output -1.

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

2.83

Hint

Translated by ChatGPT 5