Largest Square in a Binary Matrix

You are given a binary matrix of size m × n where each cell is either 0 or 1. Your task is to compute the area of the largest square submatrix that contains only 1's.

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

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

The answer to the problem is the square of the maximum value in the dp table.

Note: Your solution should read input from standard input (stdin) and print the result to standard output (stdout).

inputFormat

The first line contains two space-separated integers m and n, representing the number of rows and columns of the matrix respectively. This is followed by m lines, each containing n space-separated integers (either 0 or 1) representing the matrix.

outputFormat

Output a single integer representing the area of the largest square submatrix that contains only 1's.

## sample

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

4