Sau khi cơn bão Yagi đi qua, một khu dân cư \(Codera\) bị ngập lụt nghiêm trọng. Bản đồ khu dân cư được mô tả dưới dạng một lưới ô vuông kích thước \(R \times C\).

Các đội cứu hộ cần vận chuyển lương thực từ trạm chỉ huy (vị trí S) đến khu vực tập trung người dân (vị trí E). Tuy nhiên, một số ô trên bản đồ đã bị ngập quá sâu hoặc vật cản đổ chắn ngang (ký hiệu là #), không thể đi qua được. Các ô còn lại là đường đi an toàn (ký hiệu là .).

Trưởng thôn p2o2HuaGiaBao và tất cả mọi người đã gặp vấn đề về sức khoẻ và mất khả năng tính toán. Là những coder tương lai của đất nước, hãy giúp họ giải quyết bài toán này nhé.

Yêu cầu: Hãy tìm độ dài quãng đường ngắn nhất để đội cứu hộ đi từ S đến E. Biết rằng từ một ô, đội cứu hộ chỉ có thể di chuyển sang \(4\) ô kề cạnh (lên, xuống, trái, phải) và mỗi bước di chuyển tính là \(1\) đơn vị độ dài.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(R, C\) là số hàng và số cột của bản đồ.
• \(R\) dòng tiếp theo, mỗi dòng chứa một chuỗi ký tự có độ dài \(C\) mô tả bản đồ, chỉ gồm các ký tự:
  • .: Đường đi an toàn.
  • #: Khu vực nguy hiểm (vật cản).
  • S: Điểm bắt đầu (xuất hiện đúng \(1\) lần).
  • E: Điểm kết thúc (xuất hiện đúng \(1\) lần).

Output

• In ra một số tự nhiên duy nhất là chi phí ít nhất để đi từ điểm S đến điểm E. Nếu không thể đến được đích, in ra -1.

Constraints

• \(1 \leq R, C \leq 10^3\)

Example

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

7