Genotypy

Limit pamięci: 32 MB

Genotypy są skończonymi łańcuchami genów. Opisujemy je za pomocą słów utworzonych z wielkich liter alfabetu angielskiego A–Z. Różne litery oznaczają różne rodzaje genów. Gen może pączkować — zmieniając się w dwójkę nowych genów. Tymi przemianami rządzi skończony zbiór reguł. Każdą regułę pączkowania można zapisać w postaci trójki wielkich liter co oznacza, że gen może się zmienić w dwójkę genów .

Wielką literą oznaczamy specjalny rodzaj genów zwanych supergenami. Hodowla genotypu rozpoczyna się od łańcucha supergenów i polega na sterowanym pączkowaniu wybranych genów zgodnie z ustalonymi regułami.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia skończony zbiór reguł pączkowania genów oraz ciąg słów określających genotypy, jakie należy wyhodować,
• dla każdego z danych genotypów bada, czy można go wyhodować z pewnego skończonego łańcucha supergenów zgodnie z danymi regułami pączkowania i jeśli tak, znajduje minimalną długość takiego łańcucha,
• zapisuje wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita , . W każdym z kolejnych wierszy jest zapisana jedna reguła pączkowania, w postaci słowa złożonego z trzech wielkich liter A–Z. Dopuszczalne są reguły pączkowania, w których na drugim lub trzecim miejscu występuje supergen.

W następnym wierszu jest zapisana jedna liczba całkowita , . W każdym z kolejnych wierszy jest zapisany jeden genotyp w postaci niepustego słowa złożonego z co najwyżej liter A–Z.

Wyjście

W -tym z kolejnych wierszy standardowego wyjścia należy zapisać:

• jedną liczbę całkowitą dodatnią oznaczającą minimalną długość łańcucha supergenów potrzebnego do wyhodowania -tego danego genotypu, albo
• jedno słowo NIE, jeśli tego genotypu nie da się wyhodować.

Przykład

Dla danych wejściowych:

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

poprawną odpowiedzią jest:

3
1
NIE

Autor zadania: Przemysława Kanarek.