Побег из заброшенного дома

<<Клуб неудачников>> под предводительством Билла пытается сбежать из заброшенного дома, в котором на них напал Пеннивайз. Дом можно представить в виде таблицы размера $n \times m$, каждая клетка которой либо свободна, либо занята стенкой. Изначально, компания друзей находится в некоторой свободной клетке, а выход из дома находится в другой свободной клетке. Друзья могут переходить между соседними по стороне свободными клетками.

Чтобы напугать друзей и не дать им успешно убежать, Пеннивайз постоянно меняет температуру воздуха. А именно, каждый раз, когда друзья переходят между двумя клетками, соседними по горизонтали, он уменьшает температуру на 1 градус, а когда переходят между двумя клетками, соседними по вертикали, увеличивает температуру на 1 градус. Температура воздуха может принимать любые целочисленные значения, в том числе, температура может быть отрицательной.

Друзья хотят, чтобы конечная температура воздуха, когда они выберутся из дома, как можно меньше отличалась от исходной температуры воздуха. Помогите им определить минимальное возможное отличие исходной температуры от конечной. Обратите внимание, что значения температуры воздуха во время нахождения друзей в доме, их не интересует. При необходимости, друзья могут несколько раз проходить через любые свободные клетки, в том числе стартовую клетку и клетку с выходом.

В первой строке даны два целых числа $n$ и $m$ --- размеры таблицы ($1 \le n, m \le 1000$). В следующих $n$ строках находится по $m$ символов --- описание таблицы. Описание состоит из символов <<.>>, <<#>>, <<s>> и <<f>>. Если $j$-й символ в $i$-й строке равен <<#>>, то в клетке $(i, j)$ находится стенка, иначе эта клетка свободна. Символ <<s>> обозначает стартовую позицию друзей, а символ <<f>> обозначает клетку, в которой находится выход. Гарантируется, что в таблице содержится ровно один символ <<s>> и ровно один символ <<f>>.

Если друзья не смогут выбраться из дома, выведите -1. Иначе, выведите неотрицательное число --- минимальное возможное отличие исходной температуры от конечной, которого они могут добиться.

В первом тесте друзья могут сначала перейти два раза в клетку сверху, и потом два раза в клетку справа. Тогда, сначала температура увеличится на 2, а после --- уменьшится на 2. В итоге, отличие от исходной будет $0$ градусов.