题目描述

题目译自 XVI OI Olimpiada Informatyczna – III etap Wyspa

Bajtazar 是幸福洋上岛国拜托西亚的国王。拜托西亚是一座凸形岛屿，所有城市均位于海岸边，其中包括首都拜托城。每对城市通过岛内连接两城市的直线道路相连，不同城市对的道路相交形成路口。

Bajtazar 的王位竞争者 Bitocy 策划了一场邪恶的阴谋。在 Bajtazar 从首都前往邻近城市期间，Bitocy 占领了拜托城。Bajtazar 需尽快返回拜托城夺回王权。不幸的是，部分道路被 Bitocy 的武装队伍巡逻，Bajtazar 无法通行这些道路，但可在路口穿越它们。他只能在路口处转向。

Bajtazar 知晓哪些道路被巡逻。他请求你帮助规划从他所在城市到拜托城的最短安全路径。

输入格式

第一行包含两个整数 $n, m$ $(3 \leq n \leq 100000, 1 \leq m \leq 1000000)$，用单空格分隔，分别表示城市数和被 Bitocy 队伍巡逻的道路数。城市按从 $1$ 到 $n$ 编号，从拜托城（$1$ 号点）开始，沿海岸顺时针编号。Bajtazar 位于城市 $n$。接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ $(-1000000 \leq x_i, y_i \leq 1000000)$，用单空格分隔，表示城市 $i$ 的坐标。

接下来的 $m$ 行，每行包含两个整数 $a_j, b_j$ $(1 \leq a_j < b_j \leq n)$，表示连接城市 $a_j$ 和 $b_j$ 的道路被巡逻。巡逻道路的描述不重复。保证在所有测试数据中，Bajtazar 能到达拜托城。

输出格式

输出一个浮点数，表示从城市 $n$ 到拜托城的最短安全路径长度。输出结果与正确答案的绝对误差不超过 $10^{-5}$。

6 9
-12 -10
-11 6
-4 12
6 14
16 6
18 -2
3 4
1 5
2 6
2 3
4 5
3 5
1 3
3 6
1 6

42.0000000000

Bajtazar 应遵循的路径从城市 $6$ 出发，前往城市 $4$，然后沿连接城市 $2$ 和 $5$ 的道路行进，最后沿连接拜托城与城市 $4$ 的道路到达。总长度为 $42$。