Labirintdə doğru yol
Top - şahmat fiquru, bir gedişdə üfüqi və ya şaquli olaraq istənilən sayda xanaya hərəkət edə bilər. Lakin, o, yolundakı fiqurların üzərindən "atlayaraq" keçə bilməz.
Vasya yaxınlarda şahmat taxtasında özünəməxsus bir labirint qurdu - taxtanın bəzi xanalarına piyada (ən "zəif" şahmat fiquru) qoydu. İndi o, topun bir xanadan digərinə ən az neçə gedişlə çata biləcəyini bilmək istəyir.
O, bu məsələ üzərində bir neçə gündür düşünür, lakin cavab tapa bilmir. Buna görə də sizdən kömək istəyir. Vasya'nın məsələsinə cavab tapan bir proqram yazın.
Giriş məlumatları
Giriş faylının ilk sətiri iki natural ədəd ehtiva edir: n və m (1 ≤ n, m ≤ 500) - labirintin ölçüləri.
Sonrakı n sətirin hər biri m simvol ehtiva edir. Bu sətirlərin i-ci sətirinin j-ci simvolu (i, j) koordinatlı xanaya uyğundur. Xana boşdursa, "." (nöqtə), piyada ilə doludursa, P, topun başlanğıc xanadırsa, S, son xanadırsa, F simvoluna bərabərdir.
Çıxış məlumatları
Çıxış faylında topun başlanğıc xanasından son xanaya çatması üçün lazım olan minimal gediş sayını göstərin. Əgər son xana başlanğıc xanasından əlçatmazdırsa, -1 çıxarın.