도둑과 사냥개

공작부인이 아끼던 루비 목걸이를 훔친 것은 아무래도 좋은 생각이 아니었다. 성문 쪽으로 걸음을 옮기던 중 가장 듣기 싫은 소리가 들렸다. 날카로운 휘파람, 그리고 그에 답하는 개 짖는 소리. 경관이 아끼는 사냥개를 데리고 나와 수색을 시작했다는 뜻이다. 경관은 성문으로 곧장 갈 수도 있고, 오는 길에 흔적을 찾으려 할 수도 있다. 어느 쪽인지는 짐작할 수 없다. 다만 경관이 성문에 먼저 닿으면 붙잡힌다. 경관이 흔적을 밟으면 사냥개가 냄새를 맡는다. 개는 이미 냄새를 안다. 이번이 처음 저지른 일이 아니기 때문이다. 쫓아갈 흔적이 생기면 경관은 개를 풀어주고, 개는 빠르게 달린다.

선택을 해야 한다. 경관보다도 사냥개보다도 먼저 성문에 닿는다고 확신한다면 목걸이를 그대로 가지고 간다. 확신하지 못한다면 지금 당장 가까운 쓰레기 더미에 목걸이를 버리고 태연히 걸어 나가야 한다. 붙잡히더라도 손에 목걸이가 없으면 결국 풀려난다.

목걸이를 가지고 갈 것인가, 버릴 것인가?

도시는 정사각형 칸으로 이루어진 직사각형 미로다. 도시는 성벽으로 둘러싸여 있고, 성벽에는 출구가 하나 이상 있다. 자신의 위치를 알고 있고, 경관과 사냥개가 출발하는 개집의 위치도 알고 있다.

1. 매 턴(시간 단위)마다 나와 경관과 사냥개가 동시에 움직인다.
2. 나는 한 턴에 상하좌우로 한 칸 움직이거나 제자리에 머문다.
3. 처음에 경관과 사냥개는 함께 움직이며, 마찬가지로 한 턴에 상하좌우로 한 칸 움직이거나 제자리에 머문다.
4. 함께 움직이는 경관과 사냥개가 내가 앞서 지나간 칸에 도달하면 사냥개가 냄새를 맡고, 경관은 개를 풀어준다. 그다음 턴부터 사냥개는 내 흔적을 따라 한 턴에 1칸 또는 2칸씩 나아간다.
5. 경관이나 사냥개가 내가 있는 칸에 들어오면 붙잡힌다. 빠져나가려면 경관보다도 사냥개보다도 최소 한 턴 먼저 출구에 도착해야 한다.

입력은 미로 하나 이상으로 이루어진다. 각 미로는 미로의 너비 W와 높이 H를 나타내는 두 정수가 있는 줄로 시작한다. 두 값 중 하나라도 3보다 작으면 입력이 끝난다. 두 값 모두 50을 넘지 않는다.

이어서 H개의 줄이 주어지고, 각 줄은 W개의 문자로 이루어진다. 문자의 뜻은 다음과 같다.

1. 공백 문자(스페이스)는 빈 칸이다.
2. K는 경관과 사냥개가 출발하는 개집이 있는 빈 칸이다. 미로마다 정확히 하나 있다.
3. T는 도둑, 곧 나의 처음 위치인 빈 칸이다. 미로마다 정확히 하나 있다.
4. X는 벽이다.
5. E는 출구, 곧 성문인 빈 칸이다. 모든 출구는 W와 H가 정하는 미로의 바깥 둘레에 있다.

모든 미로의 바깥 둘레는 X와 E로만 완전히 둘러싸여 있다. 개집과 나 사이에는 경로가 하나 이상 있고, 나와 각 출구 사이에도 경로가 하나 이상 있다.

미로마다 한 줄씩 출력한다. 경관과 사냥개가 어떤 경로로 움직이든 반드시 빠져나갈 수 있는 경로가 있으면 KEEP IT을 출력하고, 그런 보장을 주는 경로가 없으면 DROP IT을 출력한다.

예제의 첫 번째 미로에서 경관과 사냥개는 도둑이 4번째 턴에 서 있던 칸을 7번째 턴에 발견한다. 사냥개가 풀려나 10번째 턴에 도둑을 따라잡는다. 도둑이 되돌아가면 그보다 일찍 잡힌다.

두 번째 미로에서 도둑은 13번째 턴에 성문에 닿고, 바로 그 순간 경관과 사냥개가 흔적을 발견한다. 그래도 도둑은 사냥개에게 잡히기 전에 도시를 빠져나간다.