Thoát khỏi mê cung

me-cungTrung bình

Mê cung là lưới $n \times m$ ô. Ô . đi được, ô # là tường, S là vị trí xuất phát, T là lối ra. Mỗi bước bạn đi sang một ô chung cạnh không phải tường.

Hãy tìm số bước ít nhất để đi từ S đến T.

Input

Dòng đầu gồm $n, m$ ( $2 \le n, m \le 500$ ). $n$ dòng tiếp theo, mỗi dòng $m$ ký tự mô tả mê cung. Có đúng một S và một T.

Output

In ra số bước ít nhất, hoặc -1 nếu không thể đến T.

Sample Input 1

3 4
S.#.
.##.
...T

Sample Output 1

Sample Input 2

2 3
S#T
.#.

Sample Output 2

-1

Nộp bài

Code được lưu nháp tự động trên máy này.