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