Minimum Time to Exit

You are given a grid with dimensions \(m \times n\). Each cell in the grid can be one of three types:

• \(0\): empty cell
• \(1\): an occupant
• \(2\): an exit

An occupant can move in four directions: up, down, left, or right. Each move costs 1 unit of time. The task is to compute the minimum time \(T\) such that all occupied cells can reach an exit. In other words, if \(d(x, y)\) is the minimum distance from occupant \(x\) to any exit, then

[ T = \max_{x \text{ is an occupant}} d(x, \text{exit}) ]

If any occupant cannot reach an exit, output \(-1\). You can assume that there is at least one exit in the grid.

inputFormat

The input is given in the following format:

r c
row1
row2
... 
rowr

Here, the first line contains two integers \(r\) and \(c\) representing the number of rows and columns. Each of the following \(r\) lines contains \(c\) integers separated by spaces representing the grid. Each integer is one of 0, 1, or 2.

outputFormat

Output a single integer representing the minimum time required for all occupants to reach an exit. If it is impossible for all occupants to reach an exit, output \(-1\).

## sample

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

3