Indian National Olympiad in Informatics

Related:

Online Programming Contest, 8-9 October 2005

IARCS home > OLYMPIAD

Basic Division

Problem 2: The Canteen, (K Narayan Kumar, CMI)

Indraneel has decided to erect a large square shed in a rectangular piece of land that he owns. However, there are a number of trees on this land and Indraneel does not wish to cut any of them.

Here is a description of a Indraneel's yard as a recangular grid where "." indicates the absence of a tree and "T" indicates the presence of a tree.

. . . . . T . .
. T . . T . . .
. . . . . T . .
T . . . . . . .
. . . . . . . .
. . . . . T . .
. . T . . . . .

In this case, Indraneel can build a 4 ×4 square shed, as indicated below:

. . . . . T . .
. T . . T . . .
. s s s s T . .
T s s s s . . .
. s s s s . . .
. s s s s T . .
. . T . . . . .

You may verify that this is the largest square shed he can put up without cutting any trees. Your task is to help Indraneel determine the size of the largest shed he can put up without cutting any trees.

Input format

The first line of input contains two integers M and N indicating the dimensions of the rectangular yard. This is followed by M lines of input, each containing N letters each of which is a "." or a "T".

Output format

The output consists of a single line with a single integer indicating the dimension of the largest square shed that Indraneel can put up in his yard without cutting any trees.

Test data

You may assume that M ≤60 and N ≤60 in 80% of the inputs. You may assume that M ≤1000 and N ≤1000 in all inputs.

Example

We now illustrate the input and output formats using the above example.

Sample input

7 8 
.....T..
.T..T...
.....T..
T.......
........
.....T..
..T.....

Sample output