Pictorul si cei trei arici mici

Împăratul malefic Kaktus are în posesia sa Butoiul Magic și a inundat Pădurea Fermecată! Pictorul și cei trei arici mici trebuie acum să se întoarcă la Bârlogul Castorului ca sa se fereasca de apă cât mai repede posibil!

Harta Pădurii Fermecate este formată din $L (1 \le L \le 500)$ linii și $C (1 \le C \le 500)$ coloane, asemenea unei matrice. Regiunile uscate sunt reprezentate prin caracterul ., cele inundate prin * și stâncile prin X. În plus, bârlogul Castorului este reprezentat cu D, iar Pictorul, împreuna cu cei trei arici mici, sunt reprezentați cu S. Pictorul și cei trei arici mici se afla mereu în aceeasi regiune și nu se despart unii de ceilalți.

În fiecare minut Pictorul și cei trei arici mici se pot misca în 4 regiuni învecinate uscate(sus, jos, stânga sau dreapta). De asemenea, în fiecare minut, inundația se extinde, iar toate regiunile uscate care au cel puțin o latură comună cu o regiune inundată se inundă. Nici apa, nici Pictorul și cei trei arici mici nu pot trece prin stânci. Desigur, Pictorul și cei trei arici mici nu pot trece prin regiunile inundate, iar apa nu poate inunda Bârlogul Castorului.

Notă: Pictorul și cei trei arici mici nu se pot deplasa într-o regiune care este pe cale să fie inundata (în același minut).

Cerințe

Scrieți un program care, folosind o hartă a Pădurii Fermecate, va găsi cel mai scurt timp necesar pentru ca Pictorul și cei trei arici mici să ajungă în siguranță la Bârlogul Castorului.
Dacă $T$ are valoarea 1, se va rezolva prima cerința, iar dacă $T$ are valoarea 2, se va rezolva a doua cerința.

1. Pentru această cerință se garantează că nu există vreo regiune inundată.
2. Pentru această cerință va există cel puțin o regiune inundată.
   
   Notă: Datele de intrare se citesc de la tastatură, iar datele de ieșire se afișează în consolă.

Date de intrare

Prima linie de intrare va conține un număr $T$ egal cu $1$ sau $2$.
A doua linie de intrare va conține doua numere naturale, $L$ si $C$.
Urmatoarele $L$ linii conțin fiecare câte $C$ caractere(., *, X, D, S)

Date de ieșire

Afișați pe o prima linie timpul minim în care Pictorul și cei trei arici mici pot ajunge în siguranța la Bârlogul Castorului. Dacă nu există un drum care îndeplinește condițiile cerinței, afișați cuvântul KAKTUS pe prima linie.

Restricții și precizări

• Pentru teste în valoare de 30 de puncte, $T = 1$.
• Pentru alte teste în valoare de 40 de puncte, $1 \le L \le 50 \ ; \ 1 \le C \le 50$.
• Pentru restul de 30 de puncte nu exista alte restricții.

Exemplu 1

stdin

1
3 3
D..
...
..S

stdout

4

Exemplu 2

stdin

2
3 3
D.*
...
.S.

stdout

3

Exemplu 3

stdin

2
3 3
D.*
...
..S

stdout

KAKTUS

Exemplu 4

stdin

2
3 6
D...*.
.X.X..
....S.

stdout

6