Komputery Trzybitowe kontratakują

Limit pamięci: 32 MB

Po ogromnej klapie, jaką okazały się Komputery Trzybitowe (KTB), naukowcy Bajtlandii mają nowy wspaniały pomysł: Kwantowe Komputery Trzybitowe (KKTB). Komputery KTB należy potraktować jako zwyczajną rozgrzewkę przed prawdziwym wyzwaniem - KKTB.

Przewiduje się, że nowe komputery kwantowe będą miały niespotykaną dotąd moc, bla, bla, bla, wiele głupawych problemów na olimpiady, bla, bla, bla. Do rzeczy.

Tak jak poprzednio, podstawową trudnością jest inicjalizacja pamięci. W przypadku komputerów kwantowych problemy są jednak zupełnie innej natury. Wszystkie operacje wykonywane na elementach KKTB mają efekty uboczne, tzn. wpływają na inne elementy komputera. Neutralizowanie tych efektów jest bardzo kosztowne, dlatego inicjalizacja pamięci bit po bicie nie jest możliwa. Istnieje jednak inne podejście do problemu, a mianowicie sterowane impulsy o średnim zasięgu (SISZ). Naukowcy potrafią wygenerować impulsy, których wpływ na każdy z bitów pamięci KKTB może być dokładnie obliczony. Impulsy te można emitować bardzo szybko, więc użycie nawet dużej liczby impulsów jest bardziej opłacalne niż inicjalizacja pamięci bit po bicie. Powstaje pytanie, czy da się wyzerować całą pamięc przy pomocy SISZ. Twoim zadaniem jest napisanie programu, który odpowie na to pytanie.

Bardziej formalnie, każdy bit pamięci może być w jednym z stanów ponumerowanych . Impuls SISZ oddziaływuje na wszystkie bity w ten sam sposób, a zatem można go traktować jak funkcję . Na przykład, oznacza, że po wyemitowaniu impulsu , wszystkie bity będące w stanie przejdą w stan . Naukowcy potrafią emitować pewną liczbę impulsów . Twoim zadaniem jest stwierdzić, czy istnieje ciąg impulsów, który sprowadza wszystkie bity do stanu (zeruje je), niezależnie od ich stanu początkowego.

Zadanie

Napisz program, który:

• wczytuje opis dostępnych impulsów,
• sprawdza, czy możliwe jest wyzerowanie pamięci,
• zapisuje odpowiedź do pliku wyjściowego.

Wejście

Każdy test składa się z pewnej liczby zestawów danych. Pierwszy wiersz standardowego wejścia zawiera pojedynczą liczbę naturalną , , liczbę zestawów danych. W dalszej części wejścia znajdują się zestawy danych. Opis pojedynczego zestawu danych rozpoczyna się wierszem zawierającym dwie liczby naturalne , , (, ), gdzie jest liczbą różnych stanów bitu, a liczbą dostępnych impulsów. Kolejnych wierszy zawiera opisy impulsów, -ty wiersz zawiera opis -tego impulsu. Opis impulsu jest ciągiem liczb całkowitych , opisujących wpływ na stan każdego z bitów pamięci. Liczby te są pooddzielane pojedynczymi odstępami.

Wyjście

Na standardowe wyjście należy wypisać wierszy, po jednym dla każdego zestawu danych. -ty wiersz powinien składać się z pojedynczego słowa TAK, jeśli wyzerowanie pamięci jest dla -tego testu możliwe, lub NIE w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

2
5 2
1 2 3 4 0
2 3 4 0 1
5 2
1 2 3 4 0
3 3 4 0 1

poprawną odpowiedzią jest:

NIE
TAK

Zapożyczenie z CPSPC: Marcin Mucha.