H. Телепорты

На карте есть свободные клетки ., стены # и телепорты T. Ход в соседнюю клетку по стороне стоит единицу, но переход с телепорта на любой другой телепорт бесплатен.

Найдите наименьшую стоимость пути из левой верхней клетки в правую нижнюю. Телепорты проходимы.

Веса нулевые и единичные — это 0-1 BFS: бесплатные переходы кладутся в начало дэка, платные в конец. Чтобы не перебирать пары телепортов, добавьте одну служебную вершину «телепортная сеть»: вход в неё с телепорта стоит ноль и выход из неё на телепорт тоже.

Первая строка содержит числа $n$ и $m$ ($1 \le n, m \le 1000$).

Далее идут $n$ строк по $m$ символов ., #, T.

Одно число — наименьшая стоимость или $-1$.