#C7677. Largest Square Sub-matrix of Ones

    ID: 51574 Type: Default 1000ms 256MiB

Largest Square Sub-matrix of Ones

Largest Square Sub-matrix of Ones

You are given a binary matrix (a 2D array where each element is either 0 or 1). Your task is to determine the area of the largest square sub-matrix that consists entirely of 1s.

If the side length of the largest square is \(L\), then the area is \(L^2\).

Example:

Input:
6 5
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

Output: 9

</p>

Here, the largest square sub-matrix of 1s has a side length of 3, so its area is \(3^2 = 9\).

inputFormat

The first line of the input 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.

You should read the input from standard input (stdin).

outputFormat

Output a single integer, the area of the largest square sub-matrix composed entirely of 1s. Print the output to standard output (stdout).

## sample
6 5
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
9