미술관

K 미술관은 벽이 많은 특이한 구조로 유명하다. 내부를 밝히려고 한 벽의 양 끝 모서리에 전등 두 개를 설치했는데, 이 두 전등만으로 건물 내부에 빛이 닿지 않는 곳이 없다. 즉 건물 내부의 모든 지점은 적어도 한 전등에서 빛을 받는다.

정보올림피아드를 준비하는 홍길동은 이 건물을 좋아해서 시간이 날 때마다 관람하러 온다. 하루는 관람하다가 미술관 내부의 두 지점을 잇는 최단 경로는 어떤 모양일까 하는 의문이 떠올랐다. 일반적인 다각형에서 최단 경로 알고리즘을 구현하느라 애먹었던 기억을 떠올리면서, 전등 두 개로 모든 곳을 비추는 이 특이한 구조라면 최단 경로를 쉽게 구할 수 있지 않을까 생각했다.

미술관은 정점이 $n$개인 다각형 $P = (v_0, v_1, \ldots, v_{n-1})$로 나타낸다. 정점 목록은 다각형의 경계를 반시계방향으로 따라가며 정점을 차례로 늘어놓은 것이다. 전등이 설치된 자리는 정점 $v_0$과 $v_1$이다. 변 $(v_0, v_1)$은 수평 선분이고, $v_0$의 $x$좌표는 항상 $v_1$의 $x$좌표보다 작다. $v_0$과 $v_1$을 뺀 나머지 정점은 모두 $y$좌표가 $v_0$의 $y$좌표보다 크다.

미술관 내부의 지점 $q$가 전등 $v$의 빛을 받는다는 말은, 두 점 $q$와 $v$를 잇는 선분이 $P$의 바깥과 만나지 않는다는 뜻이다. $P$의 모든 점이 $v_0$ 또는 $v_1$에서 빛을 받는다는 사실에 유의하라.

그림 1. 다각형의 모든 점이 $v_0$ 또는 $v_1$에서 빛을 받는다.

그림 1의 다각형에서 정점 $v_8$과 $v_{11}$은 $v_1$에서만 빛을 받고, $v_3$과 $v_4$는 $v_0$에서만 빛을 받는다. 나머지 정점은 두 전등 모두에서 빛을 받는다. 두 정점 사이의 최단 경로가 다각형의 정점에서만 꺾인다는 사실은 잘 알려져 있다. 예를 들어 두 정점 $v_4$와 $v_{11}$ 사이의 최단 경로는 $(v_4, v_5, v_9, v_{11})$이고, 두 정점 $v_5$와 $v_1$ 사이의 최단 경로는 선분 하나인 $(v_5, v_1)$이다.

홍길동을 도와서, 다각형 $P$의 두 정점이 주어질 때 두 정점 사이의 최단 경로를 구하는 프로그램을 작성하시오. 경로의 길이는 경로를 이루는 선분들의 유클리드 길이를 모두 더한 값이다.

첫째 줄에 다각형 $P$의 정점 개수를 나타내는 정수 $n$이 주어진다 ($3 \le n \le 100000$). 둘째 줄부터 $n$개 줄에는 $v_0$부터 시작하여 한 줄에 하나씩 $P$의 정점 $v_i$의 좌표를 나타내는 정수 두 개가 주어진다 ($i = 0, 1, \ldots, n-1$). 각 좌표는 $-10^9$ 이상 $10^9$ 이하다.

$P$의 모든 점은 $v_0$ 또는 $v_1$에서 빛을 받는다. $v_0$과 $v_1$의 $y$좌표는 같고, $v_0$은 $v_1$보다 $x$좌표가 작다. $v_0$과 $v_1$을 뺀 나머지 정점은 모두 $v_0$보다 $y$좌표가 크다. $P$의 경계를 따라 연속한 어떤 세 정점도 한 직선 위에 있지 않다.

마지막 줄에는 최단 경로를 구하려는 두 정점 $v_i$와 $v_j$의 번호인 정수 $i$와 $j$가 주어진다 ($i \ne j$). $v_i$가 출발점이고 $v_j$가 도착점이다.

입력으로 주어진 두 정점 $v_i$와 $v_j$를 잇는 최단 경로를 $(w_0, w_1, \ldots, w_{m-1})$이라고 하자. 여기서 $w_0 = v_i$, $w_{m-1} = v_j$이고, $w_k$ ($1 \le k \le m-2$)는 최단 경로가 꺾이는 점이다. 첫째 줄에 $m$을 출력하고, 둘째 줄에 $w_k$에 해당하는 $P$의 정점 번호를 순서대로 출력한다 ($0 \le k \le m-1$). 최단 경로가 어떤 정점을 지나가더라도 그 점에서 꺾이지 않으면 그 번호는 출력하지 않는다.