#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
int R, C; // R 세로 C 가로
char map[51][51];
int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 };
queue <pair<pair<int, int>, int> > q;
queue <pair<int, int> > w;
void bfs() {
while (!q.empty()) {
int x, y, cnt;
int wx, wy, ws;
x = q.front().first.second;
y = q.front().first.first;
cnt = q.front().second;
q.pop();
ws = w.size();
for (int i = 0; i < ws; i++) {
wx = w.front().second;
wy = w.front().first;
w.pop();
for (int i = 0; i < 4; i++) {
int wdx, wdy;
wdx = wx + dx[i];
wdy = wy + dy[i];
if (wdy >= 0 && wdy < R && wdx >= 0 && wdx < C && map[wdy][wdx] != 'X' && map[wdy][wdx] != 'D' && map[wdy][wdx] != '*') {
map[wdy][wdx] = '*';
w.push({ wdy,wdx });
}
}
}
for (int i = 0; i < 4; i++) {
int nx, ny;
nx = x + dx[i];
ny = y + dy[i];
if (nx >= 0 && nx < C && ny >= 0 && ny < R && map[ny][nx] != '*' && map[ny][nx] != 'X') {
if (map[ny][nx] == 'D') {
cout << cnt + 1 << endl;
return ;
}
else {
map[ny][nx] = 'S';
q.push({ { ny,nx }, cnt + 1 });
}
}
}
}
cout << "KAKTUS" << endl;
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> map[i][j];
if (map[i][j] == 'S') q.push({ { i,j }, 0 });
if (map[i][j] == '*') w.push({ i,j });
}
}
bfs();
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxjc3RkaW8+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBSLCBDOyAvLyBSIOyEuOuhnCBDIOqwgOuhnApjaGFyIG1hcFs1MV1bNTFdOwppbnQgZHhbXSA9IHsgMCwwLDEsLTEgfTsgaW50IGR5W10gPSB7IDEsLTEsMCwwIH07CnF1ZXVlIDxwYWlyPHBhaXI8aW50LCBpbnQ+LCBpbnQ+ID4gcTsKcXVldWUgPHBhaXI8aW50LCBpbnQ+ID4gdzsKdm9pZCBiZnMoKSB7Cgl3aGlsZSAoIXEuZW1wdHkoKSkgewoJCWludCB4LCB5LCBjbnQ7IAoJCWludCB3eCwgd3ksIHdzOwoJCXggPSBxLmZyb250KCkuZmlyc3Quc2Vjb25kOwoJCXkgPSBxLmZyb250KCkuZmlyc3QuZmlyc3Q7CgkJY250ID0gcS5mcm9udCgpLnNlY29uZDsKCQlxLnBvcCgpOwoJCXdzID0gdy5zaXplKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCB3czsgaSsrKSB7CgkJCXd4ID0gdy5mcm9udCgpLnNlY29uZDsKCQkJd3kgPSB3LmZyb250KCkuZmlyc3Q7CgkJCXcucG9wKCk7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgNDsgaSsrKSB7CgkJCQlpbnQgd2R4LCB3ZHk7CgkJCQl3ZHggPSB3eCArIGR4W2ldOwoJCQkJd2R5ID0gd3kgKyBkeVtpXTsKCQkJCWlmICh3ZHkgPj0gMCAmJiB3ZHkgPCBSICYmIHdkeCA+PSAwICYmIHdkeCA8IEMgJiYgbWFwW3dkeV1bd2R4XSAhPSAnWCcgJiYgbWFwW3dkeV1bd2R4XSAhPSAnRCcgJiYgbWFwW3dkeV1bd2R4XSAhPSAnKicpIHsKCQkJCQltYXBbd2R5XVt3ZHhdID0gJyonOwoJCQkJCXcucHVzaCh7IHdkeSx3ZHggfSk7CgkJCQl9CgkJCX0KCQl9CgkJZm9yIChpbnQgaSA9IDA7IGkgPCA0OyBpKyspIHsKCQkJaW50IG54LCBueTsKCQkJbnggPSB4ICsgZHhbaV07CgkJCW55ID0geSArIGR5W2ldOwoJCQlpZiAobnggPj0gMCAmJiBueCA8IEMgJiYgbnkgPj0gMCAmJiBueSA8IFIgJiYgbWFwW255XVtueF0gIT0gJyonICYmIG1hcFtueV1bbnhdICE9ICdYJykgewoJCQkJaWYgKG1hcFtueV1bbnhdID09ICdEJykgewoJCQkJCWNvdXQgPDwgY250ICsgMSA8PCBlbmRsOwoJCQkJCXJldHVybiA7CgkJCQl9CgkJCQllbHNlIHsKCQkJCQltYXBbbnldW254XSA9ICdTJzsKCQkJCQlxLnB1c2goeyB7IG55LG54IH0sIGNudCArIDEgfSk7CgkJCQl9CgkJCX0KCQkJCgkJfQoJfQoJY291dCA8PCAiS0FLVFVTIiA8PCBlbmRsOwp9CmludCBtYWluKCkgewoJY2luID4+IFIgPj4gQzsKCWZvciAoaW50IGkgPSAwOyBpIDwgUjsgaSsrKSB7CgkJZm9yIChpbnQgaiA9IDA7IGogPCBDOyBqKyspIHsKCQkJY2luID4+IG1hcFtpXVtqXTsKCQkJaWYgKG1hcFtpXVtqXSA9PSAnUycpIHEucHVzaCh7IHsgaSxqIH0sIDAgfSk7CgkJCWlmIChtYXBbaV1bal0gPT0gJyonKSB3LnB1c2goeyBpLGogfSk7CgkJfQoJfQoJYmZzKCk7Cn0=
NTAgNTAKRC4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4KLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLlMK
50 50
D.................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
.................................................S