Rotting Oranges

You are given a grid of size m<em>x</em>n where each cell 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, right) to a rotten orange becomes rotten. The process continues until no fresh orange can be rotten by the adjacent infection.

Your task is to determine the minimum number of minutes that must elapse until no cell has a fresh orange. If it is impossible for all the fresh oranges to become rotten, return \( -1 \).

Formally, if after the process there exists any fresh orange (cell with 1), output \( -1 \); otherwise, output the minimum number of minutes required to rot all oranges.

inputFormat

The input is read from standard input and consists of:

1. The first line contains two integers m and n, representing the number of rows and columns respectively.
2. The next m lines each contain n space-separated integers. Each integer is either 0, 1, or 2 representing an empty cell, a fresh orange, or a rotten orange, respectively.

outputFormat

Output to standard output a single integer, which is the minimum number of minutes required for all fresh oranges to become rotten. If it is impossible, output -1.

3 3
2 1 1
1 1 0
0 1 1

4