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.