얼음판 위의 소

문제

베시는 거대한 얼어붙은 호수에서 스케이트를 탄다. 호수는 2차원 격자이며, 두 축의 좌표는 모두 $-10^9$부터 $10^9$까지이다. 격자 칸 중 $N$개($1 \le N \le 20000$)에는 바위가 있고 각각 $1$번부터 $N$번까지 번호가 매겨져 있다. 나머지 칸은 모두 미끄러운 얼음이다.

베시는 스케이트 실력이 좋지 않아서, 지금 있는 칸(항상 어떤 바위의 바로 옆이다)에서 한 방향으로 몸을 밀어 다른 바위에 부딪힐 때까지 미끄러지는 방식으로만 이동한다. 그리고 부딪히기 직전 칸에서 멈춘다. 밀 수 있는 방향은 정확히 북, 동, 남, 서뿐이며 바위를 뚫고 지나갈 수는 없으므로, 보통 쓸 수 있는 방향은 많아야 세 개다.

미끄러지려면 그 방향 앞쪽 어딘가에 자신을 멈춰 줄 바위가 반드시 있어야 한다. 앞에 바위가 없으면 영원히 미끄러지므로, 밀 때마다 방향을 신중히 골라야 한다.

예를 들어 베시(B)가 자신의 바로 동쪽에 있는 목표 지점(G) $(x = 5, y = 1)$로 가려 한다(. = 얼음, * = 바위, B = 베시, G = 목표). 곧바로 동쪽으로 미끄러지면 바위에 부딪혀야만 멈출 수 있으므로 목표를 지나쳐 버린다. $(5, 1)$에 도달하는 한 가지 방법은 다음과 같다.

   (a)              (b)             (c)              (d)
4 .....*.         .....*.         .....*.          .....*.
3 ..*....  slide  ..*....  slide  ..*....   slide  ..*....
2 ......*  north  ..B...*  east   .....B*   south  ......*
1 .*B..G. ------> .*...G. ------> .*...G.  ------> .*...B.
0 *....*.         *....*.         *....*.          *....*.
  0123456

상황 (a)에서는 북, 동, 남으로 시도할 수 있지만 멈춰 줄 바위가 있는 방향은 북쪽뿐이다. 상황 (b)에서는 동쪽으로 미끄러질 때만 멈춰 줄 바위가 있다.

$i$번 바위는 $(X_i, Y_i)$에 있으며 각 좌표는 $-10^9$ 이상 $10^9$ 이하이고, 두 바위가 같은 칸에 있지 않다. 베시는 항상 어떤 바위의 바로 옆인 $(B_x, B_y)$에서 출발하고 목표는 $(G_x, G_y)$이다. 모든 좌표는 같은 범위 안에 있으며, 목표에는 항상 도달할 수 있다.

미끄러지는 것 자체는 힘들지 않지만 바위에서 몸을 미는 것은 매우 지치는 일이다. 베시가 목표에 도달하기 위해 필요한 최소 밀기 횟수를 구하여라.

입력

첫째 줄: 공백으로 구분된 다섯 정수 $N$, $B_x$, $B_y$, $G_x$, $G_y$.
둘째 줄부터 $N + 1$째 줄까지: $i + 1$째 줄에는 $i$번 바위의 위치를 나타내는 두 정수 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다.

출력

첫째 줄: 베시가 목표에 도달하기 위한 최소 밀기 횟수를 나타내는 정수 하나.