Problem description

Na szachownicy rozmiaru N × M stoi skoczek szachowy. Chce on dostać się na pewne inne pole szachownicy. Niestety, niektóre pola są dziurawe i nie można w nie wskoczyć. Skoczek porusza się oczywiście zgodnie z regułami ruchu skoczka szachowego (tj. ma maksymalnie osiem możliwych ruchów do wykonania – każdy z nich polega na przeskoczeniu do pola odległego o dokładnie trzy w metryce miejskiej od tego, na którym aktualnie stoi, to pole to musi być innego koloru niż to, na którym stał uprzednio).

Napisz program, który: wczyta opis szachownicy, początkową pozycję skoczka i jego pozycję docelową, wyznaczy minimalną długość ścieżki skoczka do pola docelowego 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ść szachownicy. W kolejnych N wierszach znajduje się opis szachownicy: litera S oznacza początkową pozycję skoczka, litera K oznacza pozycję końcową, # oznacza pole dziurawe, zaś . oznacza pole dostępne (na które można wskoczyć).

Na wejściu znajduje się zawsze dokładnie jedna litera S i dokładnie jedna litera K.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowitą – minimalną liczbę ruchów niezbędnych do osiągnięcia celu. Jeśli osiągnięcie celu jest niemożliwe, zamiast tego należy wypisać NIE.

Ograniczenia

1 ≤ N, M ≤ 1 000.

Przykład

5 6
S.....
......
.#..#.
...#..
....K.

4