Cuvinte

     Se considera o lista avānd un numar cunoscut de cuvinte. Din acesta lista s-au ales doua cuvinte oarecare. Se doreste transformarea primului cu­vānt īn cel de-al doilea, trecānd prin cuvinte in­ter­me­diare, existente īn lista data. Trecerea dintr-un cuvānt īn altul se poate face folosind urmatoarele operatii: schimbarea, adaugarea sau stergerea unui singur caracter.

Cerinta

     Dāndu-se o lista de cuvinte si doua cuvinte din aceasta, gasiti cea mai scurta secventa de operatii care transforma primul cuvānt īn cel de-al doilea folosind operatiile permise.

Date de intrare

Fisierul de intrare: CUVINTE.IN

Linia 1: N P Q
·         trei numere naturale nenule, reprezentānd nu­marul cuvintelor din lista (N), pozitia pri­mu­lui cuvānt īn lista (P), respectiv pozitia celui de-al doilea cuvānt īn lista (Q);

Liniile 2..N+1: cuvant
·         aceste N linii contin fiecare cāte un cuvānt, apartinānd listei.

Date de iesire

Fisier de iesire: CUVINTE.OUT

Linia 1: M
·         numar natural, reprezentānd numarul minim de pasi necesari pentru a ajunge de la primul cuvānt la al doilea;

Liniile 2..M+2: cuvānti
·         pe aceste linii apar īn ordine cuvintele dintr-o secventa ce respecta cerinta problemei (cāte un cuvānt pe linie), inclusiv primul cuvānt al secventei.

Restrictii si precizari
· 2 <= N <= 100
· 1 <= M,P,Q <= 100
· numarul maxim de caractere dintr-un cuvānt este 100;
· daca nu exista solutie, īn fisierul de iesire se va scrie numarul 0 (zero);
· Daca sunt mai multe secvente de lungime mi­­ni­ma, īn fisier se va scrie una singura.

Exemplul 1

    

CUVINTE.IN
7 1 5
car
cer
cerc
mar
mare
rosu
inrosit

CUVINTE.OUT
2
car
mar
mare

Exemplul 2

CUVINTE.IN
7 1 6
car
cer
cerc
mar
mare
rosu
inrosit

CUVINTE.OUT
0

Timp maxim de executare/test: 2 secunde