Sau khi chạm tay vào viên ngọc trong Lời Nguyền Viên Ngọc Hoàng Kim, nhà thám hiểm An bỗng cảm nhận được một sự rung chuyển kỳ lạ. Mặt đất nứt toác… và cánh cửa đá phía sau anh khép lại.

An không còn ở trong mê cung cũ nữa. Một mê cung mới mở ra - rộng lớn hơn, lạnh lẽo hơn. Những bức tường đá phủ rêu đứng sừng sững, và dưới lòng đất, một âm thanh rì rầm vang lên như lời thì thầm của vực sâu.

Mê cung có dạng một lưới hình chữ nhật kích thước ~m \times n~, nơi mỗi ô đều mang một ký hiệu định mệnh:

• O - khoảng không tĩnh lặng, nơi An có thể bước qua

• X - vách đá chặn lối, không thể xuyên qua

• E - vị trí khởi đầu của An

• S - những điểm rò rỉ của dòng nước đáng sợ

• Trong mê cung có đúng một ô 'E' và ~K~ ô 'S', là các vị trí ban đầu mà nước bắt đầu lan ra.

Thời gian không đứng yên.

Mỗi giây trôi qua:

• An có thể bước sang một ô O kề bên (chung cạnh)

• Đồng thời, nước từ các ô S cũng lan ra các ô O xung quanh

Nhưng quy luật tàn nhẫn nhất là: Nếu An và dòng nước cùng đến một ô tại cùng thời điểm nước sẽ đến trước. Không có cơ hội thứ hai!

Nước dâng lên không ngừng. Bóng tối ngày càng dày đặc. An chỉ còn một hy vọng duy nhất: chạy tới rìa mê cung, nơi có thể nhìn thấy ánh sáng le lói từ bên ngoài - bất kỳ ô O nào nằm trên biên đều có thể là lối thoát.

Nhiệm vụ:

Hãy giúp An tìm con đường thoát hiểm nhanh nhất:

• Chỉ đi qua các ô O

• Tránh bị nước chặn đường

• Số bước đi là ít nhất (tính cả ô bắt đầu)

Nếu không tồn tại con đường nào thì số phận của An sẽ bị chôn vùi mãi mãi trong lòng mê cung.

Input

• Dòng đầu là ~2~ số nguyên dương ~m, n~ ~(5 \le m, n \le 1500)~;

• ~m~ dòng tiếp theo mỗi dòng chứa ~n~ ký tự trong các kí tự O, X, E, S.

Output

Một số nguyên duy nhất là số lượng ô trong hành trình ngắn nhất của nhà thám hiểm; nếu không có cách thoát hiểm thì in ra số ~-1~.

Scoring

Sample Input 1

5 7
XOOXOEO
XOOOOXO
OOOXOXO
OOOOOOX
OOOOOOX

Sample Output 1

1