#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

A jump of a knight on an *N* x *N* chess board consists of two horizontal steps and one vertical step, or one horizontal step and two vertical steps. For example, consider a knight on position *K*=(3,2) in the following 5 x 5 board.

1 2 3 4 5 +---+---+---+---+---+ 1 | | | | X | P | +---+---+---+---+---+ 2 | | | | X | | +---+---+---+---+---+ 3 | | K | | X | | +---+---+---+---+---+ 4 | | | | X | | +---+---+---+---+---+ 5 | | | | | | +---+---+---+---+---+

This knight can jump to positions (1,1), (1,3), (2,4), (4,4), (5,3) and (5,1). The knight can move to position *P*=(1,5) by jumping first to (5,3), then to (3,4) and then to *P*. This is the least number of jumps to get from *K* to *P*.

The board may contain forbidden positions, indicated by X in the above board. The knight may not land on a forbidden position. In the above situation, the only allowed way to get from *K* to *P* with 3 jumps is via (1,1) and (2,3).

Write a program that, given a board size *N*, an initial position *K* of the knight, a target position *P* and a list of forbidden positions, computes the least number of jumps to get from *K* to *P* while not landing on any forbidden positions. The board size *N* in the test data and the number of forbidden positions both range from 5 to 50.

Output the value -1 if there is no way to get from *K* to *P* without landing on any forbidden positions.

## Input

The input contains

- the board size
*N*on the first line, - the initial position
*K*of the knight on the second line, - the target position
*P*on the third line, - the number
*T*of forbidden positions on the fourth line, followed by*T*lines each containing a forbidden position.

The input data corresponding to the chess board shown in the example above is as follows.

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

On the first line is the number 5 of rows and columns. Next is the initial position *K*, which is (3,2). The target position *P* is given on the third line. Next, the number of forbidden positions, 4 in this example, is given. The list of forbidden positions follows, one per line.

## Output

The output should contain an integer which indicates the number of jumps in the shortest move from *K* to *P*. Output -1 if there is no solution.

For the above example, the output will be:

3

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 5 | 1s | 32MB | Average |

2 | 0 | 0 | 1s | 32MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o knightmoves -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512