Largest Square of Flowers

You are given a garden represented as an n x m grid. Each cell of the grid contains either a flower (represented by 1) or is empty (represented by 0). Your task is to compute the side length of the largest square sub-grid that contains only flowers.

You can solve this problem using dynamic programming. Let \(dp[i][j]\) represent the side length of the largest square whose bottom-right cell is at \( (i,j) \) and contains only flowers. The recurrence relation is:

[ dp[i][j] = \begin{cases} 1, & \text{if } i=0 \text{ or } j=0 \text{ and } garden[i][j]=1,\ \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, & \text{if } garden[i][j]=1,\ 0, & \text{if } garden[i][j]=0. \end{cases} ]

The answer is the maximum value in the dp table. If no cell contains a flower, output 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
row1
row2
...
rown

Where:

• n and m are integers representing the number of rows and columns of the grid, respectively.
• Each of the next n lines contains m integers (either 0 or 1), separated by spaces, representing one row of the garden.

If n or m is 0, the grid is empty, and the output should be 0.

outputFormat

Output to standard output (stdout) a single integer: the side length of the largest square sub-grid that contains only flowers.

## sample

5 6
1 0 1 0 0 1
1 1 0 1 1 1
1 1 1 1 0 0
1 1 1 1 0 0
0 1 1 1 0 1

3