창고지기

매장 바닥은 $n \times m$ 크기의 정사각형 칸으로 나뉜 직사각형이다. 두 칸은 변을 공유하면 인접한다. 어느 한 칸 위에는 소포가 놓여 있고, 나머지 각 칸은 비어 있거나 창고지기가 옮길 수 없을 만큼 무거운 상자로 막혀 있다. 창고지기는 소포를 시작 칸에서 목표 칸으로 밀어서 옮겨야 한다.

창고지기는 빈 칸 위에서만 움직이며, 지금 서 있는 칸에서 인접한 빈 칸으로 한 칸씩 걸어간다. 소포와 인접한 칸에 서 있을 때는 소포를 밀 수 있는데, 그러면 소포는 자신의 반대쪽(소포 건너편) 칸으로 한 칸 이동한다. 단, 그 반대쪽 칸에 무거운 상자가 없어야 한다.

다음을 수행하는 프로그램을 작성하시오.

• 표준 입력에서 매장 배치도, 창고지기의 시작 위치, 소포의 목표 위치를 읽는다.
• 소포를 목표 칸에 놓기 위해 필요한 최소 밀기 횟수(소포가 칸 경계를 넘는 횟수)를 구하거나, 놓는 것이 불가능함을 판정한다.
• 결과를 표준 출력에 쓴다.

첫째 줄에 공백 하나로 구분된 두 양의 정수 $n$, $m$ ($n, m \le 100$)이 주어진다. 이는 매장의 크기이다. 이어지는 $n$개의 각 줄에는 문자 S, M, P, K, w로 이루어진 길이 $m$의 문자열이 하나씩 주어진다. $j$번째 줄의 $i$번째 문자는 좌표 $(i, j)$ 칸의 종류를 나타내며 의미는 다음과 같다.

• S: 무거운 상자
• M: 창고지기의 시작 위치
• P: 소포의 시작 위치
• K: 소포의 목표 위치
• w: 빈 칸

문자 M, P, K는 입력에 각각 정확히 한 번씩 나타난다.

표준 출력에 다음을 출력한다.

• 소포를 목표 칸에 놓을 수 없으면 단어 NIE(폴란드어로 "아니오") 하나만 출력한다.
• 놓을 수 있으면 그에 필요한 최소 밀기 횟수(소포가 칸 경계를 넘는 횟수)와 같은 정수 하나를 출력한다.