Wyrównywanie słów

Limit pamięci: 32 MB

Dane są dwa słowa i oraz skończony ciąg słów . Operacja polega na połączeniu (konkatenacji) słowa ze słowem , czyli — mówiąc inaczej — na dopisaniu do słowa , z prawej jego strony, słowa .

Chcemy sprawdzić, czy słowa i można wyrównać za pomocą słów z danego ciągu. To znaczy, czy można po wykonaniu skończonej liczby operacji dopisywania do słów i odpowiednio wybranych wyrazów danego ciągu, otrzymać w obu przypadkach to samo słowo.

Przykład

Słowa abba oraz ab można wyrównać za pomocą wyrazów ciągu: baaabad aa badccaa cc. Wystarczy w tym celu do słowa abba dopisać: aa oraz badccaa, zaś do słowa ab — najpierw baaabad, potem cc, a następnie aa. W obu przypadkach otrzymamy to samo słowo: abbaaabadccaa.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia długość danego ciągu słów, a następnie opisy dwóch słów i oraz opisy kolejnych słów ciągu ,
• sprawdza, czy słowa i można wyrównać za pomocą słów z danego ciągu i jeśli tak, znajduje minimalną liczbę operacji , jakie trzeba w tym celu wykonać,
• zapisuje tę liczbę na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana liczba całkowita dodatnia , . Jest to długość ciągu słów . W drugim i trzecim wierszu znajdują się opisy słów i . W następnych wierszach znajdują się opisy kolejnych słów ciągu — każdy opis w osobnym wierszu. Opis słowa składa się z liczby naturalnej, będącej długością tego słowa, oraz z samego słowa w postaci ciągu znaków. Liczba jest oddzielona od słowa pojedynczym odstępem. Każde słowo składa się wyłącznie z małych liter alfabetu angielskiego od a do z i ma długość nie większą niż . Suma długości wszystkich danych słów jest nie większa niż .

Wyjście

Na standardowe wyjście należy zapisać:

• jedną liczbę całkowitą nieujemną, to jest minimalną liczbę operacji , jakie trzeba wykonać, aby wyrównać dane słowa i ,
• albo jedno słowo NIE, jeśli słów nie można wyrównać.

Przykład

Dla danych wejściowych:

4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc

poprawną odpowiedzią jest:

5

natomiast dla danych:

4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa

poprawnym wynikiem jest:

NIE

Autor zadania: Wojciech Rytter.