Дано прямокутний лабіринт розміром ~n \times m~ клітинок. Кожна клітинка є або вільною (.), або стіною (#). Крім того, рівно одна клітинка позначена S (старт) і рівно одна клітинка позначена F (фініш) — обидві ці клітинки вважаються вільними для проходу.

За один крок можна перейти з поточної клітинки в одну із сусідніх по стороні (вгору, вниз, ліворуч, праворуч) клітинок, якщо вона не є стіною.

Визначте мінімальну кількість кроків, потрібну, щоб дістатися з S до F. Якщо це неможливо — виведіть ~-1~.

Вхідні дані

• Перший рядок містить два цілих числа ~n~ і ~m~ (~1 \le n, m \le 1000~, ~n \cdot m \le 10^6~) — кількість рядків і стовпців лабіринту.
• Далі йде ~n~ рядків по ~m~ символів у кожному — опис лабіринту. Кожен символ — це ., #, S або F. Гарантується, що символ S зустрічається рівно один раз, і символ F — теж рівно один раз.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість кроків з S до F, або ~-1~, якщо шляху не існує.

Приклади

Приклад 1

Вхідні дані:

3 3
S..
.#.
..F

Вихідні дані:

4

Пояснення: один із найкоротших шляхів — ~(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)~ (рядок, стовпець, нумерація з 1), що займає рівно 4 кроки.

Приклад 2

Вхідні дані:

3 3
S#.
###
.#F

Вихідні дані:

-1

Пояснення: стіни повністю відділяють S від F.

Приклад 3

Вхідні дані:

1 2
SF

Вихідні дані:

1