Problem K: Move on Ice

Problem

ペンギンのフロロは無限に広い氷の上のマス($sx$,$sy$)にいる。
マス($tx$,$ty$)に穴があり、そこから水に入ることができる。
氷の上に$n$個の氷の塊があり、それぞれマス($x_i$,$y_i$)にある。

フロロは上下左右の4方向に移動できる。
氷の上は滑りやすいので、移動すると氷の塊にぶつかるまで動き続ける。
氷の塊にぶつかると氷の塊のあるマスの1マス手前で止まる。
穴のマスを通過することで穴に入ることができる。

フロロは1度だけ全力で踏ん張ることにより途中で止まることができる。

氷の塊にぶつかると痛いのでできるだけぶつかる回数を少なくしたい。
穴のあるマス($tx$,$ty$)へ移動するまでにぶつかる回数の最小値を求めよ。
辿り着けない場合は$-$1を出力せよ。

Input

入力は以下の形式で与えられる。

$sx$ $sy$
$tx$ $ty$
$n$
$x_1$ $y_1$
...
$x_n$ $y_n$

入力はすべて整数で与えられる。
1行目にフロロがいるマスの座標が空白区切りで与えられる。
2行目に穴があるマスの座標が空白区切りで与えられる。
3行目に氷の塊の数$n$が与えられる。
続く$n$行目に氷の塊があるマスの座標が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $0 \leq n \leq 10^5$
• $0 \leq sx$,$sy$,$tx$,$ty$,$x_i$,$y_i \leq 10^9$
• 与えられる座標はすべて異なる

Output

穴に移動するまでにぶつかる回数の最小値を出力せよ。
辿り着けない場合は$-$1を出力せよ。

Sample Input 1

0 0
13 33
2
0 34
14 0

Sample Output 1

0

Sample Input 2

0 1
5 0
4
2 1
1 3
4 2
3 0

Sample Output 2

4

Sample Input 3

0 0
0 2
1
0 1

Sample Output 3

-1

Note

Link

 

---