Tomatoes

Time limit1sMemory limit256 MB

Summary

Given a grid of ripe, unripe, and empty cells, find how many days until every tomato ripens or report -1 if some never can.

Level: Medium4 of 10
Topics: BFS, Graph, Queue, Matrix
Solved: No attempts yet

Problem

Tomatoes are stored in a warehouse inside a grid-shaped box, one tomato per cell. Each cell of the grid holds a ripe tomato, an unripe tomato, or no tomato at all.

Each day, every unripe tomato that is directly adjacent (up, down, left, or right) to a ripe tomato becomes ripe. Diagonally adjacent tomatoes are not affected, and a tomato never ripens on its own.

Given the size of the grid and the initial state of every cell, find the minimum number of days needed for all tomatoes to ripen. Note that some cells may contain no tomato.

Input

The first line contains two integers $M$ and $N$ , the dimensions of the box, where $M$ is the number of columns and $N$ is the number of rows, with $2 \le M, N \le 1{,}000$ .

Each of the next $N$ lines describes one row of the box using $M$ integers: $1$ for a ripe tomato, $0$ for an unripe tomato, and $-1$ for an empty cell.

At least one tomato is guaranteed to be present in the input.

Output

Print the minimum number of days until every tomato is ripe. If all tomatoes are already ripe at the start, print $0$ ; if some tomatoes can never ripen, print $-1$ .

Examples5

Example 1

Input

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

Expected output

Example 2

Input

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

Expected output

-1

Example 3

Input

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

Expected output

Example 4

Input

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

Expected output

Example 5
Input
```
2 2
1 -1
-1 1
```
Expected output
```
0
```