Largest Undamaged Square

You are given a grid representing a garden. Each cell in the grid is either '0' (an undamaged tile) or '1' (a damaged tile). Your task is to determine the side length of the largest contiguous square composed entirely of undamaged tiles.

This problem can be solved using dynamic programming. Define \(dp[i][j]\) as the side length of the largest square whose bottom-right corner is at cell \((i, j)\). The recurrence relation is given by:

\( dp[i][j] = \min\{ dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1] \} + 1 \)

if the cell \((i,j)\) is undamaged (i.e. contains '0'). The answer is the maximum value in the \(dp\) table, which represents the side length of the largest square.

inputFormat

The first line contains two integers \(n\) and \(m\), the number of rows and columns in the garden grid, respectively.

The next \(n\) lines each contain \(m\) space-separated characters (either '0' or '1'), representing the state of each tile in the garden.

outputFormat

Output a single integer representing the side length of the largest contiguous square composed of undamaged tiles.

## sample

4 5
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0

3

</p>