Minimum Steps in a Dangerous Grid

You are given a grid of size \(N \times M\) where each cell represents a building. Some buildings are dangerous and cannot be stepped on. Your task is to determine the minimum number of steps required to travel from the top-left corner (cell (1, 1)) to the bottom-right corner (cell (N, M)), while avoiding the dangerous buildings.

The grid is represented with 1-indexed coordinates. You can move in four directions: up, down, left, or right. If there is no valid path to reach the destination, output \(-1\). The number of steps is equivalent to the number of moves from one cell to an adjacent cell.

Input/Output Guidelines: The problem consists of multiple test cases. For each test case, you will be given the dimensions of the grid, followed by the list of dangerous building coordinates. Your output should be the minimum number of steps required, or \(-1\) if the destination is unreachable.

inputFormat

The input begins with a single integer \(T\) representing the number of test cases. Each test case is described as follows:

• A line containing two integers \(N\) and \(M\): the number of rows and columns in the grid.
• A line containing an integer \(K\), representing the number of dangerous buildings.
• \(K\) lines, each containing two integers \(x\) and \(y\), the 1-indexed coordinates of a dangerous building.

outputFormat

For each test case, output a single line containing the minimum number of steps required to travel from (1, 1) to (N, M). If the destination is unreachable, output \(-1\).

## sample

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

0
4
6
-1
8

</p>