Swan Lake

Two swans live on a rectangular lake. Part of the lake is frozen, so at first the swans may not be able to reach each other.

The lake is an R by C grid. Each cell is either water or ice.

Each day, every ice cell that is horizontally or vertically adjacent to water melts into water. Diagonal contact does not count.

The diagram below shows three stages of the melting process.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      initial            day 1              day 2

A swan can move only through water cells, and only to a horizontally or vertically adjacent water cell. Diagonal movement is not allowed.

Determine the minimum number of days that must pass before the two swans can meet.

The first line contains integers R and C. (1 ≤ R, C ≤ 1500)

Each of the next R lines contains one string of length C. . means water, X means ice, and L means a cell containing a swan. A cell containing a swan is treated as water.

Print the minimum number of days needed until the two swans can meet.