Largest Contiguous Square Block

You are given a grid with M rows and N columns where each cell has a height represented by an integer. Your task is to find the side length of the largest contiguous square block in which all cells have the same height.

To solve the problem, you can use a dynamic programming approach. Let \(dp[i][j]\) provide the side length of the largest square with bottom-right corner at cell \((i, j)\). The recurrence is given by:

[ dp[i][j] = \begin{cases} 1, & \text{if } i = 0 \text{ or } j = 0, \ \min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1, & \text{if } grid[i][j] = grid[i-1][j] = grid[i][j-1] = grid[i-1][j-1], \ 1, & \text{otherwise.} \end{cases} ]

The answer is the maximum value in the \(dp\) table.

inputFormat

The first line contains two space-separated integers \(M\) and \(N\) representing the number of rows and columns of the grid respectively. The next \(M\) lines each contain \(N\) space-separated integers representing the grid values.

outputFormat

Output a single integer which is the side length of the largest contiguous square block where all cells have the same height.

## sample

4 5
1 2 3 4 5
6 1 1 1 2
7 1 1 1 3
8 1 1 1 4

3

</p>