Problem E
Knight Fly

You are given a $2\, 000\, 000\, 000$ by $2\, 000\, 000\, 000$ chessboard. The bottom-left most cell has coordinates ($1$, $1$). The board is full of blocked cells, and no chess piece may be placed on those cells. Because there are so many blocked cells on the chessboard, instead of being told which cells are blocked, you will be told which cells are clear (not blocked). A knight piece is initially at cell ($X_ s$, $Y_ s$), and your goal is to move the knight piece to cell ($X_ t$, $Y_ t$) with as few knight fly(s) as possible. Both of those cells are guaranteed to be clear.

A knight fly is defined as a sequence of $3$ flying-steps given below. There are $8$ types of knight fly(s):

• $2$ flying-steps up, then $1$ flying-step left

• $2$ flying-steps up, then $1$ flying-step right

• $2$ flying-steps right, then $1$ flying-step up

• $2$ flying-steps right, then $1$ flying-step down

• $2$ flying-steps down, then $1$ flying-step right

• $2$ flying-steps down, then $1$ flying-step left

• $2$ flying-steps left, then $1$ flying-step down

• $2$ flying-steps left, then $1$ flying-step up

A flying-step is defined as a continuous movement in that direction until the next clear cell is reached. A knight piece at cell ($X_ a$, $Y_ a$) can move to ($X_ b$, $Y_ b$) if he can do so using any of the knight fly(s) above.

The upwards direction is defined as the positive Y direction, and the rightwards direction is defined as the positive X direction.

Input

The first line of the input consists of an integer $1 \leq N \leq 200\, 000$ the number of clear cells. The second line of the input contains $4$ integers $X_ s$, $Y_ s$, $X_ t$ and $Y_ t$. The following $N$ lines contains $2$ integers $X$ and $Y$, the coordinates of a clear cell. All cell coordinates are within the board, and all $N$ cells are unique.

Output

Output a single integer- the minimum number of knight fly(s) required. If there is no way for the knight to get from cell ($X_ s$, $Y_ s$) to cell ($X_ t$, $Y_ t$) using knight fly(s), output $-1$ instead.

Subtasks

1. ($3$ Points): Sample.

2. ($7$ Points): There are $N = 10$ clear cells, all with coordinate values $X \in [1..10]$ and $Y = 1$.

3. ($20$ Points): There are $N = 100$ clear cells, all with coordinate values $X, Y \in [1..10]$.

4. ($30$ Points): All $N$ clear cells will have coordinate values $X, Y \leq 100$.

5. ($20$ Points): There are at most $100$ columns and $100$ rows containing clear cells.

6. ($20$ Points): No additional constraint.

Warning

The I/O files are large. Please use fast I/O methods.

4
1 1 3 3
1 1
2 1
3 1
3 3

1

4
1 1 10 3
1 1
2 1
10 1
10 3

1

4
1 1 4 1
1 1
2 1
3 1
4 1

-1