Trong một chuyến thực địa, Tuấn bị mắc kẹt giữa khu rừng đang xảy ra hỏa hoạn. Khu rừng được mô hình hóa thành một bảng gồm ~N~ hàng và ~M~ cột. Mỗi ô mang một trong các ký hiệu:

• .: Đất trống, người và lửa đều có thể đi qua;
• #: Chướng ngại vật, người và lửa đều không thể đi qua;
• S: Vị trí xuất phát duy nhất của Tuấn;
• E: Trạm cứu hộ duy nhất;
• F: Một điểm bùng phát lửa ban đầu.

Quá trình di chuyển của Tuấn và sự lan truyền của lửa diễn ra đồng thời. Trong mỗi giây:

• Từ mỗi ô đang cháy, lửa lan sang tất cả các ô chung cạnh không phải #. Lửa có thể lan vào cả S và E;
• Tuấn được di chuyển sang một ô chung cạnh không phải #.

Tuấn không được bước vào một ô nếu lửa đã đến đó trước hoặc đến cùng lúc. Vì vậy, tại mọi ô thông thường, thời điểm Tuấn đến phải nhỏ hơn nghiêm ngặt thời điểm lửa đến. Riêng tại E, nếu Tuấn và lửa đến cùng lúc thì Tuấn vẫn thoát hiểm thành công.

Yêu cầu

Hãy tìm thời gian ngắn nhất để Tuấn đi từ S tới E an toàn.

Input

Từ tệp văn bản ESCAPE.INP:

• Dòng đầu tiên chứa hai số nguyên ~N, M~ ~(1 \le N, M \le 1000)~;
• ~N~ dòng tiếp theo, mỗi dòng chứa đúng ~M~ ký tự thuộc tập {., #, S, E, F} mô tả khu rừng. Dữ liệu bảo đảm có đúng một ô S và đúng một ô E.

Output

Ghi vào tệp văn bản ESCAPE.OUT:

• Một số nguyên duy nhất là thời gian ngắn nhất để Tuấn thoát hiểm;
• Nếu không tồn tại lộ trình an toàn, in ra -1.

Ràng buộc

• Subtask 1 (20% số điểm): ~N, M \le 10~;
• Subtask 2 (20% số điểm): Không có ô F;
• Subtask 3 (20% số điểm): Có đúng một ô F;
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

3

Giải thích

Tuấn lần lượt đi qua các ô ~(1,1), (2,1), (3,1), (4,1)~ và tới trạm cứu hộ sau ~3~ giây. Lửa gần nhất chỉ tới E ở giây thứ ~4~, nên Tuấn thoát hiểm an toàn.