Knight

Problem Statement

You are playing chess on an $n \times m$ board with a friend.

Your opponent only has a king left; and fortunately for you, your opponent has left for a bathroom break. You can have as many turns as you want before he returns!

However, for you, you only have a knight left on the board that can move. Furthermore, there are a total of $b$ positions on the board that your knight cannot move to (let's say there are landmines buried under those positions or something).

Even though you're already cheating by taking consecutive moves, you would like to only make legal moves with your knight; that is, knights can only move to positions that are $1$ position away in one axis and $2$ positions away in another.

What is the minimum number of times you have to move your knight legally to capture the opponent's king?

Input

Your first line will contain $n$, $m$, and $b$ as space-separated integers. $n$ and $m$ represents the size of the chess board, and $b$ represents the amount of positions your knight cannot move to.

Your next line will contain two numbers, $x_\text{knight}$ and $y_\text{knight}$, representing the position of your knight on the chess board.

Your next line will contain two numbers, $x_\text{king}$ and $y_\text{king}$, representing the position of the opponent's king on the chess board.

Your next $b$ lines will contain two numbers, $x_i$ and $y_i$, representing a position that the knight cannot hop onto.

Output

A single integer representing the minimum number of moves it would take your knight to capture the king, or $-1$ if it is impossible.

Constraints

For all test cases:

• $1 \le n,m \le 500$
• $0 \le b \le \left(nm-2\right)$
• $0 \le x \le \left(n-1\right)$ for all $x$
• $0 \le y \le \left(m-1\right)$ for all $y$
• All pairs of $x$ and $y$ are unique.

Example 1

5 7 5
2 1
2 6
0 2
1 3
2 4
3 3
4 2

7

Example 2

8 8 24
0 0
7 7
0 2
1 5
1 6
1 7
2 0
2 1
2 4
2 5
2 6
2 7
3 1
3 3
3 5
4 4
4 6
5 0
5 3
5 4
5 5
6 1
6 3
6 4
7 2
7 3

14

Example 3

37 29 8
15 16
15 14
13 15
13 17
14 14
14 18
16 14
16 18
17 15
17 17

-1

Python Template

n, m, b = map(int, input().split())
knight = tuple(map(int, input().split()))
king = tuple(map(int, input().split()))
landmines = [tuple(map(int, input().split())) for _ in range(b)]

# print(...)