Zadanie

Furt beh o život

Počet bodov: 45

Conquistador Ferko to má ťažké. To conquistadorovanie Mexika je furt beh o život. Najprv uteká na Mexickej pláni pred pumou na kopec, potom z kopca spolu s pumou uteká pred zosuvom pôdy do Mexického pralesa, potom z Mexického pralesa beží pred nahnevanými Mexičanmi.

Mexičania majú jednu veľkú výhodu, a to že Ferka nemusia dohoniť, stačí ho trafiť šípom. Ferko bude musieť teda pri svojom behu kľučkovať. Nemá však pri behu kapacitu ešte nad tým kľučkovaním rozmýšľať, tak mu s tým budete musieť pomôcť.

Úloha

Ferko uteká z pralesa, a chce dobehnúť za svojimi conquistadorskými kumpánmi. Prales si vieme predstaviť ako mriežku voľných políčok a prekážok, v ktorom sa vie Ferko hýbať v štyroch základných smeroch. Nesmie pritom však spraviť viac ako tri kroky v jednom smere za sebou, inak ho Mexičania trafia šípom. Zistite, na koľko najmenej krokov vie dobehnúť do cieľa.

Vstup a Výstup

V prvom riadku vstupu sú dve čísla \(r\) a \(s\) - počet riadkov a stĺpcov pralesa. Nasleduje mriežka \(r\) krát \(s\) znakov: popis pralesa. S označuje Ferkovu štartovaciu pozíciu, T jeho cieľ, . voľné políčko a # prekážku. Prvý a posledný riadok, ako aj prvý a posledný stĺpec, sú plné prekážok.

Vypíšte jedno číslo - najmenší počet krokov, na ktoré sa vie Ferko dostať z štartu do cieľa, pričom nesmie spraviť viac ako tri kroky v rovnakom smere za sebou. Ak sa to nedá, vypíšte \(-1\).

Vo vstupoch platí \(3 \leq r, s \leq 5000\) a \(12 \leq r \cdot s \leq 10^5\). V prvej z troch sád navyše platí, že prekážky sú len na okrajoch.

Príklady

Input:

3 7
#######
#T...S#
#######

Output:

6

Napríklad tri kroky doľava, jeden doprava, dve doľava.

Input:

8 8
########
#...S..#
#......#
#......#
#......#
#......#
#...T..#
########

Output:

7

Input:

8 8
########
#.....S#
#.######
#...#..#
#......#
#####..#
#T.....#
########

Output:

22

Input:

6 6
######
#...##
#.S#.#
#.#T.#
##...#
######

Output:

-1