섬

시간 제한1초메모리 제한128 MB

요약

모든 도시가 볼록다각형의 꼭짓점에 있고 모든 대각선과 변이 도로일 때, 일부 도로가 통제된 상황에서 n번 도시에서 1번 도시까지 도로와 교차점만 이용한 최단 경로의 길이를 구한다.

난이도: 어려움10점 중 9점
유형: 그래프, 최단 경로, 기하
정답자: 아직 제출이 없습니다

문제

Byteasar는 행복의 바다에 있는 섬나라 Byteotia의 왕입니다. 섬은 볼록한 모양이고, Byteotia의 모든 마을은 해안선 위에 있습니다. 그중 한 마을이 유명한 수도 Byteburg입니다. 모든 두 마을은 두 마을을 잇는 직선 구간을 따라 놓인 도로로 연결되어 있습니다. 서로 다른 마을 쌍을 잇는 일부 도로는 서로 교차하며, 그런 교차점마다 교차로가 하나씩 생깁니다.

왕위를 노리는 경쟁자 Bitratio가 음모를 꾸몄습니다. Byteasar가 수도에서 이웃 마을로 이동하는 사이에 Bitratio의 무리가 Byteburg를 점령했습니다. Byteasar는 통치를 되찾기 위해 최대한 빨리 Byteburg로 돌아가야 합니다. 그런데 Bitratio의 게릴라가 일부 도로를 장악하고 있습니다. Byteasar는 장악당한 도로 위로는 다닐 수 없지만, 교차로에서 그 도로를 가로질러 건널 수는 있습니다. 그는 항상 도로를 따라 이동하므로, 방향을 바꿀 수 있는 곳은 도로가 만나는 지점, 즉 마을이나 교차로뿐입니다.

충직한 신하들이 어떤 도로가 안전한지 알려 주었습니다. 지금 있는 마을에서 Byteburg까지 가는 가장 짧은 안전한 경로의 길이를 구하세요.

입력

첫 줄에 두 정수 $n$ 과 $m$ ( $3 \le n \le 100000$ , $1 \le m \le 1000000$ )이 공백 하나로 구분되어 주어집니다. 각각 마을의 수와 Bitratio의 게릴라가 장악한 도로의 수입니다. 마을은 Byteburg에서 시작해 해안을 따라 시계 방향으로 $1$ 번부터 $n$ 번까지 번호를 매깁니다. Byteasar는 현재 $n$ 번 마을에 있습니다.

이어지는 $n$ 개의 줄에는 각각 두 정수 $x_i$ 와 $y_i$ ( $-1000000 \le x_i, y_i \le 1000000$ )가 주어지며, 이는 $i$ 번 마을의 좌표입니다.

이어지는 $m$ 개의 줄에는 각각 두 정수 $a_j$ 와 $b_j$ ( $1 \le a_j < b_j \le n$ )가 주어지며, 이는 $a_j$ 번 마을과 $b_j$ 번 마을을 잇는 도로가 게릴라에게 장악되었음을 뜻합니다. 이런 쌍은 모두 서로 다릅니다. 모든 입력에서 $n$ 번 마을에서 Byteburg까지 가는 안전한 경로가 반드시 존재합니다.

출력

$n$ 번 마을에서 Byteburg까지 가는 가장 짧은 안전한 경로의 길이를 가장 가까운 정수로 반올림하여 정수 하나로 출력하세요. 실제 길이가 소수점 아래가 $.5$ 로 끝나는 값과의 차이가 항상 $0.1$ 보다 크도록 데이터가 보장되므로, 반올림 결과는 유일합니다.

힌트

위 그림은 예제 입력을 나타냅니다. 가장 좋은 경로는 $6$ 번 마을에서 $4$ 번 마을 방향으로 출발해, 교차로에서 $2$ 번과 $5$ 번 마을을 잇는 도로로 갈아탄 뒤, 마지막으로 Byteburg와 $4$ 번 마을을 잇는 도로를 따라갑니다. 그 길이는 $10 + 12 + 20 = 42$ 입니다.

예제6

예제 1

입력

예상 출력

예제 2
입력
```
3 1
0 0
6 8
12 0
1 3
```
예상 출력
```
20
```

예제 3

입력

예상 출력

예제 4

입력

예상 출력

예제 5

입력

예상 출력

예제 6

입력

28 165
-5999 119
-5670 -1962
-5030 -3271
-4987 -3336
-3743 -4689
-1884 -5697
-1110 -5896
-480 -5981
-467 -5982
747 -5953
1389 -5837
2402 -5498
4572 -3885
4757 -3657
5991 331
5696 1885
5492 2417
5114 3138
5023 3281
4847 3537
3425 4926
2962 5218
2828 5291
1837 5712
998 5916
-1376 5840
-2398 5500
-3468 4896
1 2
1 6
1 7
1 10
1 12
1 14
1 16
1 24
1 25
1 27
1 28
2 4
2 8
2 12
2 14
2 16
2 17
2 20
2 22
2 23
2 25
2 26
3 4
3 5
3 9
3 14
3 20
3 21
3 22
3 23
3 25
4 7
4 14
4 15
4 16
4 17
4 18
4 20
4 22
4 23
4 25
4 26
5 8
5 10
5 11
5 13
5 16
5 19
5 20
5 21
5 23
5 24
5 25
5 28
6 9
6 10
6 14
6 15
6 17
6 18
6 19
6 21
6 23
6 26
6 27
7 8
7 10
7 11
7 13
7 16
7 17
7 18
7 19
7 21
7 24
7 26
8 16
8 18
8 20
8 21
8 23
8 24
8 26
9 13
9 14
9 18
9 22
9 23
9 24
9 26
9 28
10 13
10 14
10 15
10 17
10 18
10 24
10 25
10 28
11 12
11 14
11 15
11 18
11 19
11 21
11 22
11 23
12 13
12 14
12 15
12 16
12 20
12 21
12 23
12 24
12 26
12 27
13 16
13 17
13 18
13 19
13 22
13 24
13 25
13 26
13 27
14 15
14 17
14 25
14 26
14 28
15 17
15 20
15 26
15 28
16 17
16 22
16 24
17 18
17 19
17 23
17 24
17 27
18 27
19 21
19 23
19 24
20 22
20 23
20 27
20 28
21 22
21 23
21 25
21 26
21 27
21 28
22 23
22 25
23 24
23 27
24 27
24 28
25 27
25 28

예상 출력