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.