Taco Shortest Path Problem

You are given an n x n grid in which some cells contain obstacles. The robot starts at a given cell and must reach the target cell using the minimum number of moves. The robot can only move one step at a time in one of four directions: up, down, left, or right. It is not allowed to move into a cell with an obstacle.

Note:

• The grid rows and columns are numbered from 0 to n-1.
• If no valid path exists, output -1.

The task is to compute the shortest path length from the start position to the target position using a breadth-first search algorithm.

Mathematically, if \( \mathcal{P} \) is the set of all valid paths from the start to the target, you are asked to find:

[ d = \min_{p \in \mathcal{P}} { \text{number of moves in } p} ]

If \( \mathcal{P} = \emptyset \), then output -1.

inputFormat

The input is read from stdin and has the following format:

n m
x1 y1
x2 y2
... (m lines of obstacles)
sx sy
tx ty

Where:

• n is the size of the grid.
• m is the number of obstacles.
• Each of the next m lines contains two integers xi and yi denoting the obstacle positions (0-indexed).
• sx sy represent the starting cell coordinates.
• tx ty represent the target cell coordinates.

outputFormat

Output a single integer to stdout representing the minimum number of moves required to reach the target. If no valid path exists, output -1.

## sample

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

8