Chochlik

Limit pamięci: 64 MB

W pewnej dziewiętnastowiecznej fabryce energia była przekazywana za pomocą pasów transmisyjnych. Fabryka działała bardzo prężnie, aż kiedyś złośliwy chochlik wdarł się do fabryki i pozamieniał ułożenie niektórych pasów. Właściciel fabryki zastanawia się, czy przy aktualnym ułożeniu pasów fabryka będzie mogła funkcjonować poprawnie.

Istnieją dwa rodzaje połączeń między dwoma różnymi kołami. Jeśli koło kręci się w pewną stronę, to koło połączone z nim sposobem A kręci się w tę samą stronę, zaś połączone sposobem B - w przeciwną.

Dwa sposoby połączeń kół pasami transmisyjnymi.

Dany wydział fabryki może funkcjonować poprawnie, jeśli rozpędzenie w nim dowolnego koła nie będzie wprawiać w ruch żadnego innego koła w dwie przeciwne strony naraz.

Twoim zadaniem jest napisanie programu, który dla każdego wydziału fabryki stwierdzi, czy może on poprawnie działać przy aktualnym rozmieszczeniu pasów transmisyjnych.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę wydziałów fabryki.

W następnych wierszach znajdują się opisy kolejnych wydziałów. W pierwszym wierszu każdego takiego opisu znajdują się dwie liczby całkowite oraz (, ), oznaczające odpowiednio liczbę kół w wydziale i liczbę połączeń między nimi. W każdym z następnych wierszy opisu wydziału znajdują się dwie liczby całkowite , oraz jedna litera , pooddzielane pojedynczymi odstępami (, , ) oznaczające odpowiednio numery połączonych kół oraz rodzaj połączenia między nimi.

Może się zdarzyć, że dwa koła będą połączone więcej niż jednym pasem transmisyjnym.

Możesz założyć, że w ok. przypadków testowych liczba kół w każdym z wydziałów nie przekracza .

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie wierszy. W -tym wierszu powinno znaleźć się jedno słowo:

• "TAK", jeśli -ty wydział fabryki może poprawnie funkcjonować,
• "NIE" w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

2
4 4
1 2 B
2 3 A
3 4 A
4 1 A
2 0

poprawną odpowiedzią jest:

NIE
TAK

Wyjaśnienie do przykładu: Pierwszy wydział nie może działać poprawnie, ponieważ wprawienie w ruch koła numer w prawą stronę spowodowałoby wprawienie w ruch koła numer w prawą i lewą stronę równocześnie, a taki ruch jest niepoprawny. W drugim wydziale nie ma żadnych pasów i jest to poprawna konfiguracja.

Autorzy zadania: Joanna Bujnowska, Jacek Tomasiewicz.