Самый дальний квартал

В городе нарисовали карту из клеток. По некоторым клеткам можно ходить, а некоторые клетки заняты зданиями и через них пройти нельзя.

В нескольких клетках стоят отделения полиции. Для каждой проходимой клетки определим расстояние до ближайшего отделения как длину самого короткого пути по клеткам (ходить можно только вверх, вниз, влево, вправо).

Нужно найти, какое самое большое такое расстояние встречается в городе. Если существует хотя бы одна проходимая клетка, из которой нельзя добраться ни до одного отделения, выведите -1.

Формат ввода

В первой строке записаны два целых числа R и C — число строк и столбцов карты. Далее идут R строк по C символов в каждой:

• # — здание, прохода нет;
• . — улица, по ней можно ходить;
• S — отделение полиции (это тоже проходимая клетка).

Формат вывода

Выведите одно целое число — максимальное расстояние до ближайшего S среди всех проходимых клеток, либо -1, если есть проходимая клетка, не достижимая ни от одного S.

Ограничения

• 1 ≤ R ≤ 1000, 1 ≤ C ≤ 1000
• хотя бы одна клетка — S

Пример

Ввод

3 5
S...#
.##..
...#.

Вывод

6