POLSKI SPOJ

Opis

Jako ostatnią podróż w swoim życiu pan Jan postanowił odbyć podróż dookoła świata. Jednak jego poznańskie korzenie nie pozwalają mu na taką rorzutność, by wydać oszczędności swojego życia (niemałe zresztą) na wycieczkę. Dlatego też postanowił, że będzie korzystał tylko z tanich środków lokomocji:

• Tanie Linie Samolotowe(TLS),
• Tanie Linie Pociągowe(TLP),
• Tanie Linie Łodziowe(TLL).

Co więcej, jedno z zaprzyjaźnionych biur podróży zaoferowało, że jeżeli pan Jan tak zaplanuje podróż, że będzie korzystał tylko z dwóch różnych środków lokomocji, to zaoferuje mu dodatkową zniżkę, na co pan Jan przystał z ochotą.

Twoim zadaniem jest sprawdzenie, czy istnieje możliwość zaplanowania takiej podróży tanimi przewoźnikami. Spółki oferujące tani transport nie oferują jednak podróży w obie strony (na przykład wyjazd do kraju ogarnietego dżumą jest tanii, jednak za powrót trzeba zapłacić "odrobinę" więcej). Podróż nie musi obejmować wszystkich miejsc i może rozpoczynać się w dowolnym punkcie, ważne tylko, aby kończyła się i zaczynała w tym samym miejscu.

Specyfikacja wejścia

W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.

W pierszwej linii każdego zestawu danych będą podane 2 liczby: N (1 ≤ N ≤ 1000) określająca liczbę miejsc oraz M (0 ≤ M ≤ 3*N*(N-1)), oznaczająca liczbę oferowanych przejazdów. W kolejnych M liniach podane będą oferowane przejazdy w postaci x y s, gdzie x,y będą określały punkt początkowy oraz końcowy transportu (1 ≤ x, y ≤ N, x ≠ y) zaś s będzie jednym z ciągów znaków "TLS", "TLP", "TLL" na oznaczenie środka transportu.

Specyfikacja wyjścia

Dla każdego przypadku testowego wypisać TAK, jeśli podróż można zaplanować zgodnie z zachciankami pana Jana (w szczególności, koniecznie ze zniżką!) lub NIE w przeciwnym wypadku.

Przykład

3
3 3
1 2 TLS
2 3 TLP
3 1 TLL
3 6
1 2 TLS
2 3 TLP
3 1 TLL
1 2 TLP
2 3 TLL
3 1 TLS
3 3
1 2 TLL
1 3 TLL
2 3 TLL

NIE
TAK
NIE