from collections import deque


def min_minutes_to_rot(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    rotten_queue = deque()
    fresh_oranges = 0
    minutes = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 2:
                rotten_queue.append((row, col))
            elif grid[row][col] == 1:
                fresh_oranges += 1

    while rotten_queue:
        current_minute_oranges = len(rotten_queue)

        for _ in range(current_minute_oranges):
            current_rotten_row, current_rotten_col = rotten_queue.popleft()
            for dx, dy in directions:
                neighbor_row, neighbor_col = current_rotten_row + dx, current_rotten_col + dy
                if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols and grid[neighbor_row][neighbor_col] == 1:
                    grid[neighbor_row][neighbor_col] = 2
                    fresh_oranges -= 1
                    rotten_queue.append((neighbor_row, neighbor_col))

        minutes += 1

    return -1 if fresh_oranges > 0 else max(0, minutes - 1)


# Driver code
def main():
    inputs = [
                [[2, 1, 0],
                 [1, 1, 1],
                 [1, 0, 0]],

                [[2, 0, 2, 0],
                 [2, 0, 2, 0],
                 [2, 0, 2, 0],
                 [2, 0, 2, 0]],

                [[1, 1, 1, 1, 1],
                 [1, 0, 0, 1, 0],
                 [0, 1, 2, 1, 1],
                 [0, 0, 1, 1, 0],
                 [1, 1, 1, 0, 0]],

                [[2, 1, 1, 1, 1, 1, 1],
                 [0, 0, 0, 0, 0, 0, 1],
                 [1, 1, 1, 1, 1, 1, 1],
                 [1, 0, 0, 0, 0, 0, 0],
                 [1, 1, 1, 1, 1, 1, 1],
                 [0, 0, 0, 0, 0, 0, 1],
                 [1, 1, 1, 1, 1, 1, 1]],

                [[2, 0, 1],
                 [1, 0, 2],
                 [0, 1, 1]]
    ]

    for i in range(len(inputs)):
        print(i + 1, ".\t Original grid: ", inputs[i], sep="")
        print("\t Number of minutes to rot all oranges: ",
              min_minutes_to_rot(inputs[i]), sep="")
        print("-" * 100)


if __name__ == "__main__":
    main()