Farmer John đã đưa đàn bò đi nghỉ ngoài biển! Đàn bò đang sống trên \(N\) hòn đảo (\(1 \le N \le 15\)), nằm trên một lưới \(R \times C\) (\(1 \le R, C \le 50\)). Một hòn đảo là một nhóm tối đại các ô được đánh dấu X và liên thông trên lưới, trong đó hai ô X liên thông nếu chúng có chung một cạnh. (Do đó, hai ô X chung một góc không nhất thiết liên thông.)

Tuy nhiên, Bessie đến muộn nên cô đang cùng FJ bay đến bằng trực thăng. Vì thế, ban đầu cô có thể hạ cánh trên bất kỳ hòn đảo nào mình chọn. Cô muốn ghé thăm tất cả những con bò ít nhất một lần, nên sẽ di chuyển giữa các hòn đảo cho đến khi đã ghé thăm cả \(N\) hòn đảo ít nhất một lần.

Trực thăng của FJ không còn nhiều nhiên liệu, vì vậy ông không muốn sử dụng nó cho đến khi đàn bò quyết định về nhà. May mắn thay, một số ô trên lưới là vùng nước nông, được ký hiệu bằng S. Bessie có thể bơi qua các ô này theo bốn hướng chính (bắc, đông, nam, tây) để di chuyển giữa các hòn đảo. Cô cũng có thể di chuyển (theo bốn hướng chính) từ một hòn đảo sang vùng nước nông và ngược lại.

Hãy tìm quãng đường tối thiểu Bessie phải bơi để ghé thăm tất cả các hòn đảo. (Quãng đường Bessie phải bơi là số lần cô đứng trên một ô được đánh dấu S.) Sau khi xem bản đồ khu vực, Bessie biết rằng điều này là khả thi.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(R\) và \(C\), cách nhau bởi dấu cách.
• \(R\) dòng tiếp theo: dòng thứ \(i\) chứa \(C\) ký tự mô tả hàng thứ \(i\) của lưới. Các ô nước sâu được đánh dấu ., các ô thuộc đảo được đánh dấu X, và các ô nước nông được đánh dấu S.

Dữ liệu ra

In ra một số nguyên duy nhất biểu thị quãng đường tối thiểu Bessie phải bơi để ghé thăm tất cả các hòn đảo.

Ví dụ

5 4
XX.S
.S..
SXSS
S.SX
..SX

3

Nguồn

USACO 2013 January Contest, Gold — Problem 2: Island Travels

Tác giả đề: Neal Wu, 2007.