Largest Open Square

Given an n ( \times ) m grid consisting of characters . and #, find the side length of the largest square subgrid that contains only . characters.

A square subgrid is a contiguous block of cells forming a square. The problem can be solved efficiently using dynamic programming. In particular, if we let (dp[i][j]) denote the size of the largest square with its bottom-right corner at cell ((i, j)) and the cell ((i, j)) is ., then the recurrence is given by:

[ dp[i][j] = \min { dp[i-1][j],; dp[i][j-1],; dp[i-1][j-1] } + 1 ]

If (grid[i][j]) is not ., then (dp[i][j] = 0). Your task is to compute the maximum value in the DP table which represents the side length of the largest open square.

inputFormat

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

1. The first line contains two integers n and m separated by a space, where n is the number of rows and m is the number of columns of the grid.
2. The next n lines each contain a string of length m consisting only of the characters . and #.

outputFormat

Output to standard output (stdout) a single integer: the side length of the largest square subgrid that contains only . characters. If no such square exists, output 0.## sample

5 6
..##..
....#.
.#....
....##
##..##

2