### knightmoves

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`

### Submitting .cpp to 'knightmoves'

Time Limit: 1 Seconds
Memory Limit: 1024MB