Minimum Moves to Reach Destination on a Grid

You are given a grid of size \(N \times M\). Starting at the cell \((sx, sy)\), your task is to reach the destination cell \((dx, dy)\) in the minimum number of moves. You can only move in the four cardinal directions (up, down, left, right). Some cells in the grid are forbidden, and you cannot traverse them.

The grid is indexed from \(0\) to \(N-1\) for rows and \(0\) to \(M-1\) for columns. A move is defined as a step from one cell to an adjacent cell in one of the four directions. If the destination cell is blocked or it is impossible to reach it due to forbidden cells, output \(-1\).

Note: The forbidden cells are given as a list of coordinates, and each coordinate represents a cell that cannot be used in your path. The input and output are handled via standard input/output (stdin/stdout).

inputFormat

The input is provided via standard input (stdin) in the following format:

1. The first line contains two integers \(N\) and \(M\), representing the number of rows and columns of the grid.
2. The second line contains two integers \(sx\) and \(sy\), the starting cell coordinates.
3. The third line contains two integers \(dx\) and \(dy\), the destination cell coordinates.
4. The fourth line contains an integer \(K\), the number of forbidden cells.
5. The next \(K\) lines each contain two integers that represent the row and column indices of a forbidden cell.

outputFormat

Output via standard output (stdout) a single integer: the minimum number of moves required to reach the destination. If it is impossible to reach the destination, output \(-1\).

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

8