题目描述

Byteotia 岛屿是一个凸多边形。城市全都在海岸上。按顺时针编号 $1$ 到 $n$。任意两个城市之间都有一条笔直的道路相连。道路相交处可以自由穿行。有一些道路被游击队控制了，不能走，但是可以经过这条道路与未被控制的道路的交点。问从城市 $1$ 到 $n$ 的最短距离。

输入格式

第一行正整数 $n,m$ 表示城市数和被控制的岛屿数。

接下来 $n$ 行每行两个整数 $x,y$ 表示每个城市的坐标。 接下来 $m$ 行描述一条不能走的道路（起点和终点）。 数据保证有解。

输出格式

输出一个实数，为最短距离。

误差在 $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.000000000

数据规模与约定

$3 \le n \le 10^5,1 \le m \le 10^6$

$|x|,|y| \le 10^6$