Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

XIWTPZH - Podróże pana Jana - podróż dookoła świata

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

Wejście

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

Wyjście

NIE
TAK
NIE

Dodane przez:Michael Suchacz
Data dodania:2010-04-02
Limit czasu wykonania programu:0.805s-1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU NODEJS OBJC PERL6 SQLITE VB.NET
Pochodzenie:XI Wiosenny Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.