시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB96457.143%

문제

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.

입력

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita $d$ ($1 ≤ d ≤ 10$), 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 $k$ oraz $p$ ($1 ≤ k ≤ 100\,000$, $0 ≤ p ≤100\,000$), oznaczające odpowiednio liczbę kół w wydziale i liczbę połączeń między nimi. W każdym z następnych $p$ wierszy opisu wydziału znajdują się dwie liczby całkowite $a_i$, $b_i$ oraz jedna litera $c_i$, pooddzielane pojedynczymi odstępami ($1 ≤ a_i, b_i ≤ k$, $c_i \in \{A, B\}$, $a_i \ne b_i$) 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.

출력

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

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

예제 입력 1

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

예제 출력 1

NIE
TAK

힌트

Wyjaśnienie do przykładu: Pierwszy wydział nie może działać poprawnie, ponieważ wprawienie w ruch koła numer $1$ w prawą stronę spowodowałoby wprawienie w ruch koła numer $2$ 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.