Spacer

Limit pamięci: 256 MB

Nazwy miast w Bajtocji mają postać ciągów bitów. Oczywiście różne miasta mają różne nazwy. Wszystkich miast w Bajtocji jest . Tak więc tylko różnych ciągów bitów nie jest nazwami miast.

Niektóre pary miast w Bajtocji są połączone drogami. Drogi te nie krzyżują się ze sobą poza miastami. Dwa miasta są połączone bezpośrednio drogą wtedy i tylko wtedy, gdy ich nazwy różnią się tylko jednym bitem.

Bajtazar wybiera się na spacer - chce przejść z miasta do miasta , korzystając jedynie z istniejących dróg. Twoim zadaniem jest napisanie programu, który sprawdzi, czy taki spacer jest możliwy.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie liczby całkowite i oddzielone pojedynczym odstępem (, , , ). Oznaczają one odpowiednio liczbę bitów w nazwach miast oraz liczbę różnych ciągów bitów, które nie są nazwami żadnych miast. W drugim wierszu znajdują się dwa napisy oddzielone pojedynczym odstępem, każdy złożony z znaków 0 i/lub 1. Są to nazwy miast i . W kolejnych wierszach są wymienione wszystkie ciągi bitów, które nie są nazwami miast, po jednym w wierszu. Każdy taki ciąg bitów ma postać napisu złożonego z znaków 0 i/lub 1. Możesz założyć, że nazwy miast i nie pojawiają się wśród tych ciągów bitów.

W testach wartych łącznie 25% punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście słowo TAK, jeżeli możliwe jest przejście z miasta do miasta , a w przeciwnym przypadku powinien wypisać słowo NIE.

Przykład

Dla danych wejściowych:

4 6
0000 1011
0110
0111
0011
1101
1010
1001

poprawną odpowiedzią jest:

TAK

a dla danych wejściowych:

2 2
00 11
01
10

poprawnym wynikiem jest:

NIE

Wyjaśnienie do pierwszego przykładu: Oto przykładowe trasy prowadzące z 0000 do 1011:

• 
• .

Testy "ocen":

• test 1ocen: , , zabronione są wszystkie miasta o liczbie zer podzielnej przez 5, chcemy wykonać spacer z do ; odpowiedź NIE;
• test 2ocen: , , miasta i są połączone bezpośrednio drogą; odpowiedź TAK;
• test 3ocen: ładny test z ; odpowiedź TAK.

Autor zadania: Wojciech Rytter.