Задача Soldier. У деякій (здогадайтесь самі, у якій) войовничій країнi солдати-призовники роблять дві справи: - фарбують травичку та ходять строєм. I якщо з фарбуванням все легко, то стройова підготовка потребує багато часу та сил, особливо за умов, коли ось-ось черговий військовий парад...

Плац, по якому крокуватимуть солдати нашого героїчного взводу, являє собою прямокутник N×M(2≤N,M≤700) (якщо прийняти розмір «коробки» взводу солдат за квадрат з одиничною стороною), деякі клітинки якого зайняті іншими підрозділами, тож взводу ходити через цi клітинки забороняється. Відомі також початковий та кінцевий пункти руху взводу. Сержант Pupkin добре знає - солдати відмінно ходять по прямій, а ось команди «наліво», «направо» i «кругом» виконують іноді з помилками, тож він хоче, щоб на святковому проходженні взвод зробив якомога менше поворотів. Допоможіть сержанту знайти маршрут з найменшою кількістю поворотів.

Технічні умови. Програма Soldier читає з пристрою стандартного введення у першому рядку N - кількість рядків у схема плацу. У другому рядку M - кількість стовпчиків. Далі N рядків по M символів у кожному. Символ «.» означає вільну клітинку, символ «X» зайняту. Також існує рівно один символ «S» та один символ «F», що позначають відповідно початкову та кінцеву точки проходу взводу. Хоча б один маршрут між S та F завжди існує.

Програма виводить на пристрій стандартного виведення єдине число - мінімальну кількість поворотів взводу на маршруті. Перед початком маршу сержант може вишикувати взвод обличчям у будь-яку сторону – як йому це зручно.

Приклад

Введення

3
4
S...
.XXF
....

Виведення

1

 

© LIKT 1998-2018