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 <= n, m <= 100
• Numele localităţilor sunt formate din maxim 12 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.

Exemple

lgdrum.in	lgdrum.out	Explicaţii
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	2	Gorj -> 402 = 0110010010 Valcea -> 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

autor: Prof. Marinel Şerban

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com