Тура у лабіринті
Тура - це шахова фігура, яка за один хід може переміститися на будь-яку кількість клітин по горизонталі або вертикалі. При цьому вона не може "перестрибувати" через фігури, які стоять на її шляху.
Вася нещодавно спорудив на шаховій дошці своєрідний лабіринт - у деякі клітини дошки він поставив пішака (сама "слабка" шахова фігура). Тепер він хоче знати, за яку мінімальну кількість ходів тура може дістатися з однієї клітини в іншу.
Він розмірковує над цим питанням вже декілька днів, однак знайти відповідь не може. Тому він звернувся за допомогою до Вас. Напишіть програму, яка знаходить відповідь до Васіної задачі.
Вхідні дані
Перший рядок вхідного файлу містить два натуральних числа: n і m (1 ≤ n, m ≤ 500) - розміри лабіринту.
Кожен з наступних n рядків містить m символів. j-ий символ i-ого з цих рядків відповідає клітці з координатами (i, j). Він дорівнює "." (точка), якщо клітина порожня, P, якщо зайнята пішаком, S, якщо це початкова клітина для тури, F, якщо це кінцева клітина.
Вихідні дані
У вихідний файл виведіть мінімальну кількість ходів, необхідну турі для того, щоб з початкової клітини потрапити у кінцеву. Якщо кінцева клітина недосяжна з початкової - виведіть -1.