lgdrum

Aşa cum se cunoaşte de la geografie, pe harta României este trasat un caroiaj care împarte întreaga suprafaţă a ţării în careuri. Să presupunem că acestea sunt reprezentate printr-un tablou bidimensional cu $n$ linii şi $m$ coloane, fiecare celulă a tabloului conţinând numele localităţii principale din zona respectivă.
Numelui fiecărei localităţi i se asociază un cod care se obţine prin însumarea codurilor ASCII ale caracterelor din nume. De exemplu, Bacau are codul $66+97+99+97+117=476$.
Două localităţi sunt considerate vecine dacă celulele tabloului în care se află numele lor se învecinează pe direcţiile $N$, $E$, $S$, $V$.
Ana şi Bogdan învaţă la geografie jucându-se pe hartă. Ei stabilesc următoarea regulă: este posibilă deplasarea de la localitatea cu codul $A$ către localitatea cu codul $B$ dacă cele două localităţi sunt vecine şi dacă există cel puţin o poziţie pe care în reprezentarea binară a lui $A$ pe care se află $1$, iar în reprezentarea binară a lui $B$ se află $0$.
De exemplu, din localitatea Bacau, codificată $476$ se poate trece în localitatea vecină Iasi, având codul $73+97+115+105=390$, deoarece
$476 = 111011100$
$390 = 110000110$
Jocul este simplu: Ana spune numele a două localităţi de pe hartă, iar Bogdan trebuie să determine lungimea minimă a unui drum de la prima localitate specificată de Ana către cea de a doua. Prin lungimea unui drum ei înţeleg numărul de localităţi prin care trece drumul respectiv (inclusiv cele de plecare şi sosire).
Problema este cu atât mai complicată cu cât numele localităţilor de pe hartă nu sunt distincte. De exemplu, localitatea Deleni ar putea apărea de foarte multe ori.

Cerinţă

Dată fiind o hartă necodificată şi numele a două localităţi, să se determine lungimea minimă a unui drum între prima localitate şi cea de a doua localitate specificată, în condiţiile din enunţ.

Date de intrare

Fişierul de intrare lgdrum.in conţine pe prima linie două numere naturale $n$ şi $m$ separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale hărţii. Pe următoarele două linii sunt scrise numele localităţilor spuse de Ana, câte un nume pe o linie. Ultimele $n$ linii conţin fiecare câte $m$ nume separate prin câte un spaţiu, reprezentând numele localităţilor de pe hartă.

Date de ieşire

Fişierul de ieşire lgdrum.out va conţine o singură linie pe care va fi scrisă lungimea minimă a unui drum de la prima localitate spusă de Ana către cea de a doua.

Restricţii

• $2 \leq n, m \leq 100$
• Numele localităţilor sunt formate din maxim $10$ litere mari sau mici ale alfabetului englez. Se face distincţie între literele mari şi literele mici.
• Numele localităţilor spuse de Ana pot apărea de maxim $20$ de ori.
• Pentru datele de test există întotdeauna soluţie.

Exemplu

lgdrum.in

6 5
Gorj
Valcea
Cluj Bistrita Suceava Iasi Valcea
Oradea Zalau Mures Neamt Vrancea
Arad Alba Brasov Harghita Braila
Timis Hunedoara Sibiu Covasna Galati
Caras Gorj Valcea Arges Dambovita
Gorj Dolj Olt Teleorman Giurgiu

lgdrum.out

2

Explicație

Gorj $\rightarrow 402 = 0110010010$
Valcea $\rightarrow 588 = 1001001100$
deci se poate trece din Gorj în Valcea pe un drum de lungime $2$. Se observă faptul că există două localităţi Gorj şi două localităţi Valcea