NINJA GAME

Time Limit : 8 sec, Memory Limit : 262144 KB

NINJA GAME

新作ゲーム "NINJA GAME" がついに発売となった.このゲームではプレイヤーは二次元マップ上の忍者を操作して移動を行う.二次元マップは x 軸,または y 軸のどちらか一方に平行な辺のみからなる,自己交差のない多角形で表される.いま,多角形の内部に存在するスタート地点からゴール地点へと移動する必要がある.

移動は上下左右と斜め45°の8方向が可能で,いずれかの対応するコマンドを入力すると,指定した方向に自動で進み続ける.この自動移動の最中の任意のタイミングで別のコマンドを入力した場合,即座に移動方向の転換が可能である.あなたの目標は,このゲームでの実績を解除するため,最小のコマンド入力回数でスタート地点からゴール地点に移動することである.

ここで気を付ける必要があるのは,キャラが忍者であるので,壁伝いの移動が可能であるということだ.ここで壁伝いの移動するとは,多角形の辺上を移動することである.ただし,もちろん多角形の外部に出ることはできない.壁伝いの移動中にその壁に対し垂直方向に移動しようとする場合はそれ以上移動できずに止まるのだが,一方で壁伝いの移動中に斜め方向に移動しようとする場合,壁と平行な方向への壁伝いの自動移動が続き,壁がなくなったところで元の斜め方向にまた自動移動を続ける.例えば下図のように y 軸に平行な壁に x 軸正方向と y 軸負方向からなる斜め方向からぶつかった場合,ぶつかった後は壁に沿って y 軸負方向に進み,壁がなくなったところでまた x 軸正方向と y 軸負方向からなる斜め方向へと進み始める.

ここで,斜め方向に移動しながら角にぶつかったときの挙動は以下のようになる.(a) のように両方向に壁が囲まれている場合はそこで止まり,方向転換をしなければ動けない.(b) や (c) のように角を通り過ぎてそのまま進める場合は,斜め方向に自動移動を続ける.(d) のように両方向に進める場合,好きな方向を選んで進めるものとしてよい.図では移動を表す矢印で壁が隠れるため少し内部側に寄せて図示しているが,これも実際には辺上を移動することを表す図である.

また,上下左右方向の移動中に角にぶつかったときの挙動は以下のようになる.(e), (f), (g) のような場合はそのままの方向に自動移動を続ける.(h) のように壁に垂直にぶつかった場合はそこで止まり,方向転換をしなければ動けない.ただし,同様に移動を表す矢印を壁から少し内部側に寄せているが,実際には辺上を移動することを表す図である.

上記の移動に関する挙動に従った上で,スタート地点からゴール地点に到達するために入力する必要があるコマンドの数の最小値を求めるプログラムを作成してほしい.例えば下図における最小のコマンド入力回数は,図中に示すように2である.これは3つ目のサンプル入力に対応している.

Input

入力は複数のデータセットからなる. データセットの数は最大で 100 である. 各データセットは,次の形式で表される.

N sx sy gx gy x1 y1 ... xN yN

データセットの 1 行目はマップを表す多角形の頂点数を表す1つの整数 N (4 ≤ N ≤ 100) からなる.2行目は4つの整数 sx, sy, gx, gy (-10,000 ≤ sx, sy, gx, gy ≤ 10,000) からなり,スタート地点の座標が (sx, sy),ゴール地点の座標が (gx, gy) であることを表している.続く N 行では多角形の各頂点が反時計回り順に与えられる.このうち i 行目は2つの整数 xi, yi (-10,000 ≤ xi, yi ≤ 10,000) からなり,i 番目の頂点の座標が (xi, yi) であることを表す.ここで,与えられるスタート地点,ゴール地点,多角形は以下の制約を満たす.

  • 全ての辺は x 軸か y 軸のいずれか一方に対して平行である.
  • 与えられる多角形は自己交差を持たない.すなわち,各辺は端点以外で他の辺と交差せず,異なる i, j について (xi, yi) ≠ (xj, yj) である.
  • (sx, sy)(gx, gy) はともにこの多角形の内部 (辺上を含まない) にあることが保証される.
  • スタートとゴールは異なる,すなわち (sx, sy) ≠ (gx, gy) であることが保証される.

入力の終わりは 1 つのゼロからなる行で表される.

Output

各データセットに対し,スタート地点からゴール地点に辿り着くために必要な最小のコマンド入力の回数を 1 行で出力せよ.

Sample Input

8
1 1 2 2
0 2
0 0
2 0
2 1
3 1
3 3
1 3
1 2
12
-9 5 9 -9
0 0
0 -13
3 -13
3 -10
10 -10
10 10
-1 10
-1 13
-4 13
-4 10
-10 10
-10 0
12
3 57 53 2
0 0
64 0
64 18
47 18
47 39
64 39
64 60
0 60
0 44
33 44
33 30
0 30
0

Output for the Sample Input

1
1
2

1つ目の入力は下図 (1),2つ目の入力は下図 (2) に対応する.