Maze Escape

Time limit1sMemory limit512 MB

Summary

On a grid with walls, find the shortest path from start to exit when exactly one wall cell may be removed.

Level: Medium7 of 10
Topics: BFS, Graph, Array
Solved: No attempts yet

Problem

A wizard tricked Hongik and dropped him into an $N \times M$ maze, on cell $(Hx, Hy)$ . Hongik does know where the maze exit is: cell $(Ex, Ey)$ . Walls the wizard put up stand all over the maze, so walking out is not easy.

Hongik carries a wand he stole from the wizard's workshop, and the wand turns one wall cell into an empty cell. The wand works only once.

Hongik moves only to a cell that shares a side with the cell he is on, and every move takes the same amount of time. Breaking a wall takes no time. Decide whether Hongik can escape the maze, and if he can, find $D$ , the number of moves on the fastest route.

Input

N M
Hx Hy
Ex Ey

The maze follows on $N$ lines starting with the fourth line. Each line holds $M$ integers separated by spaces, where 0 is an empty cell and 1 is a wall.

$2 \le N \le 1000$ , $2 \le M \le 1000$
$1 \le Hx, Ex \le N$ , $1 \le Hy, Ey \le M$ . $Hx$ and $Ex$ are row numbers, $Hy$ and $Ey$ are column numbers, and the top left cell is $(1, 1)$ .
$(Hx, Hy) \neq (Ex, Ey)$
The start cell and the exit cell are always empty.

Output

Print $D$ , the smallest number of moves that reaches the exit cell, on one line. If the exit cell stays out of reach even after one use of the wand, print -1.

Hint

In the first example, break the wall at $(3, 2)$ to get from the top left cell to the bottom right cell.

Examples3

Example 1

Input

5 6
1 1
5 6
0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 0 0 1 1 0

Expected output

Example 2
Input
```
2 2
1 1
2 2
0 0
0 0
```
Expected output
```
2
```
Example 3
Input
```
2 2
1 1
2 2
0 1
1 0
```
Expected output
```
2
```