Гонки

На день рождения юному технику Мише подарили машинку с радиоуправлением. Мише быстро наскучило гонять машинку туда-сюда по комнате, и он соорудил специальную трассу. Для этого он разбил комнату на квадратные ячейки, некоторые из них оставив пустыми, а в некоторые поставив препятствия. Целую неделю Миша каждый день улучшал свой рекорд по прохождению трассы. Но каково же было разочарование Миши, когда к нему в гости пришел Тима со своей машинкой и побил его рекорд. Стало понятно, что машинку необходимо модернизировать.

На пробных испытаниях, которые были произведены через день, Миша обнаружил, что машинка действительно ездит лучше, однако ее поведение несколько изменилось. На пульте теперь функционируют только четыре кнопки: вперед, назад, вправо, влево. При нажатии на них машинка едет по направлению к соответствующей стене комнаты, являющейся одновременно границей трассы, точно перпендикулярно ей. Машинка разгоняется до такой скорости, что перестает реагировать на другие команды, врезается в ближайшее препятствие или стену и отскакивает от нее на половину пройденного расстояния, то есть если между машинкой и стеной было x пустых клеток, то после отскока она остановится на клетке, от которой [x/2] клеток до стены ([x] означает округление вниз, например [4/2] = 2, [7/2] = 3).

Теперь Мише интересно, какое минимальное количество раз необходимо нажать на кнопку пульта, чтобы машинка, начав в клетке старта, остановилась в клетке финиша.

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа n и m – размеры трассы (2 ≤ m, n ≤ 20). Следующие n строк содержат по m символов каждая: символ «.» соответствует пустой клетке, «#» – препятствию, а «S» и «T» – клетке старта и клетке финиша соответственно.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество нажатий на кнопки пульта для проведения машинки по трассе от старта до финиша. Если доехать от старта до финиша невозможно, выведите −1.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!