Problem 1132: cuvinte

Se considera o listă având un număr cunoscut de cuvinte. Din această listă s-au ales două cuvinte oarecare. Se dorește transformarea primului cuvânt în cel de-al doilea, trecând prin cuvinte intermediare, existente în lista dată. Trecerea dintr-un cuvânt în altul se poate face folosind urmatoarele operații: schimbarea, adaugarea sau ștergerea unui singur caracter.

Cerință

Dându-se o listă de cuvinte și două cuvinte din aceasta, găsiți cea mai scurtă secvență de operații care transformă primul cuvânt în cel de-al doilea folosind operațiile permise.

Date de intrare

Fișier de intrare: cuvinte.in

Linia $1$ : $N$ , $P$ , $Q$ , trei numere naturale nenule, reprezentând numărul cuvintelor din lista ( $N$ ), poziția primului cuvânt în listă ( $P$ ), respectiv poziția celui de-al doilea cuvânt în listă ( $Q$ );

Liniile $2 \ldots N+1$ : $cuvant$ , aceste $N$ linii conțin fiecare câte un cuvânt, apartinând listei.

Date de ieșire

Fișier de ieșire: cuvinte.out

Linia $1$ : $M$ , numar natural, reprezentând numărul minim de pași necesari pentru a ajunge de la primul cuvânt la al doilea;

Liniile $2 \ldots M+1$ : $cuvant_i$ , pe aceste linii apar în ordine cuvintele dintr-o secvență ce respectă cerinta problemei (câte un cuvânt pe linie), inclusiv primul cuvânt al secventei.

Restricții și precizări

$2 \leq N \leq 100$
$1 \leq M, P, Q \leq 100$
numarul maxim de caractere dintr-un cuvânt este $100$
daca nu există soluție, în fișierul de ieșire se va scrie cifra $0$ (zero)
dacă sunt mai multe secvențe de lungime minimă, în fișier se va scrie una singură
Testele nu sunt aceleași precum cele din concurs (nu le-am găsit)

Exemplul 1

cuvinte.in

7 1 5
car
cer
cerc
mar
mare
rosu
inrosit

cuvinte.out

2
car
mar
mare

Exemplul 2