Find Maximum Distance

You are given a rectangular grid containing S, E, ., and *. A path goes from S to E, moving up, down, left, or right each step without revisiting cells; * is an obstacle but may be passed through. The safety value of a path is the minimum, over the cells on the path, of the Manhattan distance to the nearest obstacle. Find the maximum safety value over all paths.

输入格式

The first line contains rows cols; then rows lines follow, each a string of length cols. Source range: 2≤rows,cols≤200. This site explicitly requires exactly one S, one E, and at least one *, with every other character being . or *.

输出格式

Output the maximum guaranteed minimum Manhattan distance.

样例 1

输入：

2 2
S*
*E

输出：

0

样例 2

输入：

3 3
S..
***
..E

输出：

0

样例 3

输入：

3 3
S..
...
**E

输出：

1