Grid Propagation Time

You are given an m x n integer grid grid where each cell holds one of three values:

• 0 is an empty cell,
• 1 is a clean cell, or
• 2 is an infected cell.

Each step, every infected cell infects its 4-directionally adjacent (up, down, left, or right, never diagonally) clean cells. Infection travels only from cell to cell through clean cells: an empty cell is never infected and the infection can't pass through it, so empty cells block the spread like walls.

Return the minimum number of steps that must pass until no cell in the grid is clean. If this is impossible because some clean cell can never be reached, return -1 instead. If there are no clean cells to begin with, return 0.

Examples

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The clean cell in the bottom-left (row 2, column 0) is never infected: infection only spreads up/down/left/right, and no such path reaches it.

Example 3

Input: grid = [[0,2]]
Output: 0
Explanation: There are no clean cells to begin with, so zero steps pass.