Vraja

Gigel vrea sa se înscrie în Academia de Lingvistică și trebuie să treacă printr-o proba specială. Podeaua sălii de testare este o matrice cu $n$ rânduri și $m$ coloane unde fiecare celula conține un cuvânt format din litere mici ale alfabetului englez.

Gigel pleacă din celula de pe prima linie și prima coloană și vrea să ajungă în celula $(n, m)$. El se poate deplasa dintr-o celulă în alta folosind o vrajă magică a echilibrului doar în cele patru direcții: sus, jos, stângă, dreapta și poate trece prin fiecare celula o singură dată.

Vraja funcționează astfel: Gigel construiește un șir de caractere T inițial gol. La fiecare mutare către o celula care conține cuvântul X, vraja spune ca T devine T + X (concatenare de cuvinte). Vraja va fi reușită doar daca pentru fiecare caracter care există în T și pentru fiecare caracter care există în T + X (noua vrajă) diferența de frecventă este cel mult 1. Dacă condiția nu e respectată, vraja nu va reuși și Gigel nu poate trece în celula următoare din direcția din care a pornit.

Cerință

Ajută-l pe Gigel să stabilească dacă poate ajunge în celula $(n,m)$ și care este numărul minim de vrăji pe care trebuie să le facă. Daca reușește, își va îndeplini visul de a fi membru al Academiei de Lingvistică și își va face familia mandra.

Date de intrare

Pe prima linie a fișierului de intrare vraja.in se găsesc două numere întregi, $n$ și $m$. Pe următoarele n linii se vor citi cuvintele din fiecare celula separate printr-o virgula și un număr aleator de spații.

Date de ieșire

Pe prima linie a fișierului de ieșire vraja.out se va găsi $DA$ sau $NU$ ce reprezintă dacă Gigel dacă poate ajunge în celula $(n,m)$. Dacă răspunsul este $DA$, pe a doua line se va găsi numărul minim de pași.

Restricții și precizări

$1 ≤ n, m ≤ 100$
$1 ≤ \text{lungimea fiecărui cuvânt} ≤ 26$
Numarul maxim de caractere de pe o linie a fisierului este $10000$

Exemplu

vraja.in

3 3
ab,       a, cd
a, ab,        fg
abcdef,  c, e

vraja.out

DA
4

Explicație

Plecam din $ab$ spre $a$ vraja devine $aba$. Comparam cuvintele $ab$ și $aba$ iar fiecare diferența de frecvență a fiecărei litere este $≤ 1$.
$| freqT(a) - freqT+X(a) | = 1$
$| freqT(b) - freqT+X(b) | = 0$
Un drum optim este $(1,1) ab → (1,2) a → (1,3) cd → (2,3) fg → (3,3) e$