Wall Maria 탈출

Wall Maria가 뚫렸다! Eren은 타이탄이 몰려오기 전에 집에서 최대한 빨리 대피해야 한다. 그는 Wall Maria 안에서 밖으로 나가는 가장 빠른 경로를 찾아야 한다. Wall Maria는 $N \times M$ 격자이며, Eren은 가로 또는 세로로 이동할 수 있다.

불타는 집과 건물은 Eren이 지나갈 수 없으며, '1'로 표시한다. 불타지 않은 안전한 칸은 '0'으로 표시한다. 일부 칸은 들어갈 수 있지만 특정 방향에서만 들어갈 수 있다. 이런 칸은 'U', 'D', 'L', 'R' 중 하나로 표시한다. 예를 들어 'R' 칸은 오른쪽에 인접한 칸에서만 들어갈 수 있다. 마찬가지로 'U' 칸은 위에서, 'D' 칸은 아래에서, 'L' 칸은 왼쪽에서만 들어갈 수 있다.

칸 하나(격자의 한 칸)를 지나는 데 1의 시간이 걸린다. Eren이 Wall Maria의 테두리 어느 곳이든 도달하면 그는 안전하다. 시간 $t$ 이하에 탈출하면 안전하다.

첫째 줄에 세 정수 $t$($1 \le t \le 200$), $N$($1 \le N \le 100$), $M$($1 \le M \le 100$)이 주어진다. 이어지는 N줄에 격자가 주어진다. 각 문자는 '1', '0', 'S', 'U', 'D', 'L', 'R' 중 하나이다. 입력에는 'S'가 정확히 하나 있다.

Eren이 탈출할 수 있다면, 밖으로 나가기까지 지나야 하는 칸 수의 최솟값을 출력한다. 탈출할 수 없다면 NOT POSSIBLE을 출력한다.