Hôm nay các em ở trường Tiểu học & Trung hoc cơ sở La Ngâu đã tham gia một chuyến dã ngoại cùng các anh chị tình nguyện viên. Vì sơ suất nên các bạn không may đã lạc vào nơi ở của một loài thú dữ. Là một trong số những tình nguyện viên, bạn sẽ hướng dẫn các em đến khu vực an toàn. Bạn biết trước vị trí của các con thú dữ, để di chuyển an toàn thì phải chọn đường đi càng xa chúng càng tốt!

Khu rừng có thể được mô tả bằng một hình chữ nhật kích thước ~N \times M~. Những ô trống được đánh dấu bằng ký hiệu ., những ô có thú dữ là #, vị trí ban đầu của bạn là S và khu vực an toàn là E. Bạn có thể di chuyển từ ô đang đứng sang ~4~ ô chung cạnh xung quanh ô đang đứng.

Nếu bạn đang ở ô ~(R,C)~, và có một con thú dữ ở ô ~(A,B)~, thì khoảng cách được tính theo công thức: ~|R - A| + |C - B|~ . Hãy giúp các em tìm đường đi an toàn nhất để về nhà. Đường đi an toàn nhất được hiểu là đường đi mà khoảng cách bé nhất từ một ô nào đó trên đường đi đến tất cả các con thú dữ là lớn nhất.

Dữ liệu vào

• Dòng đầu Dòng đầu tiên là hai số ~N~, ~M~ (~0 \lt N~, ~M \leq 1000~) là kích thước của khu rừng.
• ~N~ dòng sau, mỗi dòng gồm ~M~ ký tự thuộc tập {#, . , S, E} mô tả khu rừng.
• Input luôn đảm bảo chứa một ký tự S, một ký tự E và ít nhất một ký tự #.

Kết quả ra

• Gồm một dòng duy nhất là khoảng cách lớn nhất tìm được.

Ràng buộc

• Subtask ~1~ (~50 \%~): ~0 \lt N, M \leq 100~.
• Subtask ~2~ (~50 \%~): Không có ràng buộc gì thêm.

Ví dụ 1

Dữ liệu vào

4 4
#...
....
....
S..E

Kết quả ra

3

Giải thích

• Ta có đường đi an toàn là : (~4~,~1~) ~ \to ~ (~4~,~2~) ~\to~ (~4~,~3~) ~\to~ (~4~,~4~).
• Có một ô thú dữ là : (~1~,~1~).
• Khoảng cách của ô (~4~,~1~) đến con thú dữ gần nhất là : ~|4 - 1| + |1 - 1| = 3~.
• Khoảng cách của ô (~4~,~2~) đến con thú dữ gần nhất là : ~|4 - 1| + |2 - 1| = 4~.
• Khoảng cách của ô (~4~,~3~) đến con thú dữ gần nhất là : ~|4 - 1| + |3 - 1| = 5~.
• Khoảng cách của ô (~4~,~4~) đến con thú dữ gần nhất là : ~|4 - 1| + |4 - 1| = 6~.

~ \to ~ Khoảng cách nhỏ nhất của những ô trên đường đi là ~3~.

Ví dụ 2

Dữ liệu vào

4 5
.....
.###.
.#.#.
S#.E#

Kết quả ra

0

Giải thích

• Ta có đường đi an toàn là : (~4~,~1~) ~ \to ~ (~4~,~2~) ~\to~ (~4~,~3~) ~\to~ (~4~,~4~).
• Có 7 ô thú dữ lần lượt là : (~2~,~2~), (~2~,~3~), (~2~,~4~), (~3~,~2~), (~3~,~4~), (~4~,~2~), (~4~,~5~).
• Khoảng cách của ô (~4~,~1~) đến con thú dữ gần nhất là : ~|4 - 4| + |1 - 2| = 1~.
• Khoảng cách của ô (~4~,~2~) đến con thú dữ gần nhất là : ~|4 - 4| + |2 - 2| = 0~.
• Khoảng cách của ô (~4~,~3~) đến con thú dữ gần nhất là : ~|4 - 4| + |3 - 2| = 1~.
• Khoảng cách của ô (~4~,~4~) đến con thú dữ gần nhất là : ~|4 - 4| + |4 - 5| = |4 - 3| + |4 - 4| = 1~.

~ \to ~ Khoảng cách nhỏ nhất của những ô trên đường đi là ~0~.