A crate is a grid of rows rows and cols columns. Each cell holds 0 (empty), 1 (a fresh item), or 2 (a spoiled item).
Every minute, any fresh item that is directly up/down/left/right adjacent to a spoiled item becomes spoiled. Report the number of minutes that pass until no fresh item remains. If at least one fresh item can never become spoiled, report -1. If there are no fresh items to begin with, the answer is 0.
Input format
Line 1: two integers rows and cols.
The next rows lines each contain cols integers (each 0, 1, or 2), the crate.
Output format
A single integer: the minutes elapsed, or -1 if some fresh item can never spoil.
Constraints
- 1 <= rows, cols <= 50
- Each cell is 0, 1, or 2.