Shortest Path with Obstacles

In this problem, you are given a city grid with N horizontal streets and M vertical avenues. The intersections in the grid are identified by their coordinates. You have a starting intersection (\(S_x, S_y\)) and a destination intersection (\(D_x, D_y\)). Moreover, there are \(K\) obstacles placed at specified intersections that you must avoid.

Your task is to compute the shortest path from the starting point to the destination while avoiding obstacles. Movements are allowed only in the four cardinal directions (up, down, left, right) and each move has a unit cost. If the start or destination is blocked by an obstacle, or if there exists no valid path, return -1.

The grid boundaries are defined as:

[ 0 \leq x < N \quad \text{and} \quad 0 \leq y < M. ]

Read the input from standard input (stdin) and output the shortest distance to standard output (stdout).

inputFormat

The first line contains 7 integers: N M S_x S_y D_x D_y K, where N and M are the dimensions of the grid, (S_x, S_y) is the start coordinate, (D_x, D_y) is the destination coordinate, and K is the number of obstacles.

The following K lines each contain two integers x y representing the coordinate of an obstacle.

outputFormat

Output a single integer representing the length of the shortest path from the start to the destination. If no such path exists, output -1.

## sample

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

8

</p>