Rotting Oranges

You are given a grid with dimensions \(M \times N\). Each cell of the grid can have one of three possible values:

• 0 representing an empty cell,
• 1 representing a fresh orange,
• 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (up, down, left, or right) to a rotten orange becomes rotten. The process continues until either all oranges are rotten or no more oranges can turn rotten.

Your task is to determine the minimum number of minutes required for all the fresh oranges to become rotten. If it is impossible for all the oranges to rot, return \(-1\).

The problem can be modeled using a breadth-first search (BFS) on the grid. The state transition is given by:

\[ (t+1, i+\Delta_i, j+\Delta_j) \quad \text{if} \quad grid[i][j]=2 \text{ and } grid[i+\Delta_i][j+\Delta_j]=1 \]

where \(\Delta_i, \Delta_j\) can be in \(\{(1,0), (-1,0), (0,1), (0,-1)\}\).

inputFormat

The first line of input contains two integers \(M\) and \(N\), which represent the number of rows and columns in the grid respectively.

This is followed by \(M\) lines, each containing \(N\) space-separated integers (each integer is 0, 1, or 2), representing the grid.

outputFormat

Output a single integer: the minimum number of minutes required to rot all fresh oranges, or \(-1\) if it is impossible.

## sample

3 3
2 1 1
1 1 0
0 1 1

4