Infection Spread in a Grid

You are given a grid (matrix) representing the status of individuals in a community. Each cell in the grid has one of three possible values:

• 0: An empty cell
• 1: A healthy person
• 2: An infected person

The infection spreads in discrete time steps. At each time unit, any healthy person that is 4-directionally adjacent (up, down, left, right) to an infected person becomes infected. The process continues until no more healthy persons can be infected.

Your task is to determine the minimum time required for the virus to infect all healthy persons. If it is impossible to infect every healthy individual, output \( -1 \).

Formally, if \(m\) is the number of rows and \(n\) is the number of columns, you are given a matrix \(G\) where \(G[i][j]\) is one of \(\{0, 1, 2\}\). Let the infection spread to any cell \(G[i'][j']\) where \(|i-i'|+|j-j'|=1\) in one time unit if \(G[i'][j'] = 1\). Compute the minimum number of time units needed until every cell with value \(1\) becomes \(2\). If not all healthy persons can be infected, print \( -1 \).

inputFormat

The first line contains two space-separated integers, (m) and (n), representing the number of rows and columns of the grid respectively. This is followed by (m) lines, each containing (n) space-separated integers (each being (0), (1), or (2)).

outputFormat

Output a single integer: the minimum time required for all healthy persons to become infected. If it is impossible, output ( -1 ).## sample

3 5
2 1 0 2 1
1 0 1 2 1
1 0 0 2 1

2