Problem description

Dany jest labirynt złożony z kropek i haszy, po którym można poruszać się pionowo lub poziomo.

Napisz program, który: wczyta labirynt, wyznaczy długość najkrótszej ścieżki ze startu do mety w zadanym labiryncie i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i określające kolejno wysokość i szerokość labiryntu.

W kolejnych N wierszach znajduje się po M znaków – opis labiryntu zgodny z poniższym formatem:

• # – ściana,
• . – wolne pole,
• S – start,
• M – meta.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowitą – długość najkrótszej ścieżki ze startu do mety w podanym labiryncie.

Jeśli ścieżka w ogóle nie istnieje, należy wypisać tylko jedno słowo NIE.

Gwarantowane jest, że na planszy znajduje się dokładnie jedna litera S i jedna litera M.

Ograniczenia

1 ≤ N, M ≤ 1 000.

Przykład

7 9
S##......
....#.#.#
.#.#..#..
.##..#.##
.#.#.....
.#..#.##.
...#M.#..

16