Grid Traversal

The grid contains empty cells *, walls #, a start S, and an end E. Each move jumps a positive integer distance up, down, left, or right; a jump may pass over walls but cannot land on a wall. If the previous jump had length >1, the next jump must go in the same direction; a jump of length 1 lifts the restriction. E counts as reached only when the last move has length 1 and lands on E. If E cannot be reached, output −1.

输入格式

The first line contains n m, followed by n lines of the grid; 2≤n,m≤100, and there is exactly one S and exactly one E.

输出格式

Output the single integer required by the problem.

样例 1

输入：

2 2
SE
**

输出：

1

样例 2

输入：

2 3
S#E
***

输出：

4

样例 3

输入：

2 2
S#
#E

输出：

-1

样例说明

The answers to the three public examples are, in order: 1; 4; -1. All examples have been verified by independent small-scale enumeration or state search.