탈출

숲에 홍수가 나기 시작했다. 숲에는 고슴도치 한 마리가 있고, 고슴도치는 가장 가까운 친구인 비버의 굴로 최대한 빨리 도망가려고 한다.

숲의 지도는 R행 C열 격자로 주어진다. 빈 칸은 .으로, 물이 차 있는 칸은 *로, 돌은 X로 표시한다. 비버의 굴은 D, 고슴도치의 시작 위치는 S로 표시한다.

매 분마다 고슴도치는 현재 칸과 변을 공유하는 네 칸 중 하나로 이동할 수 있다. 물도 매 분마다 변을 공유하는 빈 칸으로 퍼진다. 고슴도치와 물은 돌을 지나갈 수 없고, 물은 비버의 굴로 들어가지 않는다.

고슴도치는 이미 물이 찬 칸으로 이동할 수 없으며, 다음 시간에 물이 찰 칸으로도 이동할 수 없다. 그런 칸으로 이동하면 도착하는 순간 물에 빠지기 때문이다.

지도가 주어졌을 때, 고슴도치가 비버의 굴까지 안전하게 이동하는 데 필요한 최소 시간을 구하라.

첫째 줄에 자연수 R과 C가 주어진다. 두 값은 모두 50 이하이다.

다음 R개 줄에는 숲의 지도가 주어진다. 지도에는 위에서 설명한 문자만 등장하며, D와 S는 각각 정확히 하나씩 주어진다.

고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 안전하게 도착할 수 없다면 KAKTUS를 출력한다.