Một nhà thám hiểm đến mê cung hình chữ nhật kích thước \(m \times n\) gồm các ô vuông đơn vị \((5 \leq m,\ n \leq 1500)\). Trên mỗi ô ghi một trong bốn kí tự:

+ O: Nếu ô đó là ô trống (có thể đi vào được)

+ X: Nếu ô đó có chướng ngại vật (không thể đi vào được)

+ E: Nếu là ô có nhà thám hiểm đang đứng

+ S: Ô xảy ra một vụ rò rỉ nước máy.

Trong mê cung có duy nhất một ô ghi chữ E và có K ô chữ S. Nhà thám hiểm có thể đi sang một trong số các ô trống chung cạnh với ô đang đứng trong thời gian một giây, đồng thời nước cũng lan truyền sang các ô trống chung cạnh với ô đang có nước mất thời gian một giây. Một cách đi thoát khỏi mê cung là một hành trình đi qua các ô trống đến một trong các ô trống ở biên mà không gặp ô có nước (nếu nước và nhà thám hiểm cùng đến một ô trống trong cùng một thời điểm thì nhà thám hiểm sẽ không di chuyển sang ô đó được).

Yêu cầu: Hãy chỉ giúp cho nhà thám hiểm một hành trình thoát ra khỏi mê cung đi qua ít ô nhất kể cả ô xuất phát.

Dữ liệu vào:

+ Dòng đầu là 2 số nguyên dương m, n

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

Kết quả:

+ Ghi 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.

Ví dụ:

Ràng buộc:

+ Có 40% số test ứng với 40% số điểm có K=0

+ Có 40% số test ứng với 40% số điểm có K=1

+ Có 20% số test ứng với 20% số điểm không có ràng buộc gì thêm.