{"code":"labudovi","name":"Hồ thiên nga","description":"Hai con thiên nga đang ở trong một cái hồ lớn, nhưng chúng lại đang bị chia cắt bởi băng đóng trong hồ nước. \r\nHồ nước có dạng hình chữ nhật được chia thành $r$ dòng $c$ cột. Một số ô trong hồ bị băng đóng. \r\nMùa xuân tới dần, băng trong hồ tan dần – mỗi ngày băng ở tất cả những ô tiếp xúc với nước đang ấm dần trong hồ (tức là kề cạnh một ô không bị đóng băng) sẽ tan ra.\r\n\r\n![enter image description here][1]\r\n\r\n\r\n[1]: https://i.imgur.com/IcjiruZ.png\r\n\r\nThiên nga có thể di chuyển tự do ở những ô chứa nước nhưng không thể đi qua những ô bị đóng băng. Bạn hãy tính xem sau bao nhiêu ngày thì đôi thiên nga của chúng ta có thể gặp nhau\r\n\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa 2 số $r$ và $c$, $1 \\le r, c \\le 1500$.\r\n- Mỗi dòng trong $r$ dòng tiếp theo chứa $c$ kí tự mô tả hồ nước tại thời điểm hiện tại: '.' (dot) thể hiện 1 ô chứa nước, 'X' thể hiện 1 ô bị đóng băng, và 'L' thể hiện ô có thiên nga. Có chính xác 2 ô chữ L.\r\n\r\n

Output

\r\n\r\n- Một dòng duy nhất chứa số ngày đôi thiên nga có thể gặp nhau.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 10 2\r\n .L\r\n ..\r\n XX\r\n XX\r\n XX\r\n XX\r\n XX\r\n XX\r\n ..\r\n .L\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 3\r\n ```","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}