#K5961. Largest Empty Square in a Garden

    ID: 30903 Type: Default 1000ms 256MiB

Largest Empty Square in a Garden

Largest Empty Square in a Garden

You are given a garden represented as a grid with N rows and M columns. Each cell is either empty (represented by '0') or contains a tree (represented by '1'). Your task is to determine the area of the largest square that can be formed such that all its cells are empty. The area is the square of the side length of this maximal square.

For example, if the garden is as follows:

10010
00000
11110
01001

Then the largest square of empty cells has side length 2, and its area is 4.

The solution should read the input from standard input and print the output to standard output.

inputFormat

The first line contains two space-separated integers N and M denoting the number of rows and columns of the garden respectively. Each of the next N lines contains a string of length M consisting of the characters '0' and '1', where '0' indicates an empty cell and '1' indicates a tree.

For example, the following input:

4 5
10010
00000
11110
01001

represents a garden with 4 rows and 5 columns.

outputFormat

Output a single integer which is the area of the largest square consisting only of empty cells.

## sample
4 5
10010
00000
11110
01001
4

</p>