Cover the Garden with Trees

You are given a rectangular garden represented as a grid with \(N\) rows and \(M\) columns. Each cell in the grid is either empty (denoted by .) or contains a tree (denoted by T). Initially, only the cells marked with T have trees. At every step, every tree spreads to its adjacent cells (up, down, left, and right). Your task is to determine the minimum number of steps required for the trees to cover the entire garden.

Note: It is guaranteed that the grid has at least one cell with a tree.

Mathematical formulation: Define the Manhattan distance between two cells \((i,j)\) and \((x,y)\) as \(|i-x|+|j-y|\). The minimum number of steps required is given by:

[ \text{steps} = \max_{0 \leq i < N,; 0 \leq j < M} \min_{grid[x][y]='T'} (|i-x|+|j-y|) ]

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of rows and columns of the garden, respectively.

The following \(N\) lines each contain a string of \(M\) characters, where each character is either . (empty cell) or T (cell containing a tree).

outputFormat

Output a single integer representing the minimum number of steps required for the trees to cover the entire garden.

## sample

3 3
.T.
..T
.T.

2

</p>