Largest Square Plot

You are given a rectangular field represented as an M×N matrix where each cell is either 0 (empty) or 1 (plant). Your task is to determine the side length of the largest square sub-matrix that contains only 1s.

This problem can be effectively solved using dynamic programming. Let \(dp[i][j]\) be 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 1, and 0 otherwise. The answer is the maximum value in the \(dp\) table.

inputFormat

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

• The first line contains two space-separated integers \(M\) and \(N\) representing the number of rows and columns of the field.
• This is followed by \(M\) lines, each containing \(N\) space-separated integers (either 0 or 1), representing the field.

outputFormat

Output a single integer to standard output (STDOUT) representing the side length of the largest square sub-matrix that consists entirely of 1s.

## sample

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

2

</p>