Building a Ski Course

Time limit1sMemory limit128 MB

Summary

Find the largest square stamp size that can repaint the given rough and smooth grid when later stamps cover earlier ones.

Level: Medium6 of 10
Topics: Greedy, Prefix sum, Simulation
Solved: No attempts yet

Problem

Farmer John is turning his large field into a ski course for the coming winter Moolympics. The field is $M \times N$ ( $1 \le M, N \le 100$ ), and the finished course is given as an $M \times N$ grid with one character per unit square.

Each character says how the snow in that square must be groomed. 'R' means rough and 'S' means smooth. The Moolympics organizers think a course is more interesting when rough and smooth patches are mixed.

Farmer John modifies his tractor so that one pass stamps any $B \times B$ square of the field with entirely rough snow or entirely smooth snow ( $B \le M$ and $B \le N$ ). He may stamp as often as he likes anywhere on the field, and a later stamp covers an earlier one. Resetting the tractor between stamps takes a long time, so he wants $B$ as large as possible. With $B = 1$ he can stamp every square on its own and always finish the course, but a larger $B$ may make the design impossible. Every square of the course has to be stamped at least once, and none may be left in its default state.

Find the largest $B$ that still lets Farmer John build the course.

Input

The first line contains two integers $M$ and $N$ separated by a space.

Each of the next $M$ lines contains exactly $N$ characters, each 'R' or 'S', describing the desired ski course design.

Output

Print the largest value of $B$ Farmer John can use to build the course.

Hint

The example answer is 3. Farmer John stamps columns 1 to 3 rough, then columns 2 to 4 smooth, then columns 3 to 5 rough, and finally columns 4 to 6 smooth. The grid has only three rows, so a single stamp covers all three of them.

Examples1

Example 1
Input
```
3 6
RSRSSS
RSRSSS
RSRSSS
```
Expected output
```
3
```