Problem description

Jasio dostał ostatnio na urodziny nową, intrygującą zabawkę, tak zwane Magnesy Rubika. Teraz głowi się nad tym jak ją rozwiązać…

Zabawka ta składa się z N guzików, z których każdy ma inny kolor, oraz M elektromagnesów, mających dwa różnokolorowe końce. Elektromagnesy są przyczepione końcami do guzików w taki sposób, że każdy z dwóch końców elektromagnesu przylega do pewnego z guzików, ale pomiędzy żadną parą guzików nie ma jednocześnie dwóch magnesów. Pierwotnie kolory końców magnesów przylegały do guzików o odpowiadających im kolorach. Jasiu zauważył dodatkowo, że zabawka jest spójna, czyli każda para guzików jest połączona ze sobą poprzez pewien ciąg magnesów.

Ale zabawa dopiero się zaczyna! Okazuje się, że w momencie wciśnięcia któregoś z guzików, obraca się on wokół własnej osi, a razem z nim wszystkie magnesy do niego przylegające. Dokładniej, przyjmując że magnesy przylegają do guzika w kolejności a₁, a₂, …, a_k (każdy guzik ma zdefiniowaną kolejność przylegających do niego magnesów), to magnes a₁ przeskakuje na miejsce a₂, ten przeskakuje na miejsce a₃ i tak dalej, aż ostatecznie magnes a_k przeskoczy na miejsce a₁. Podczas takiego obrotu magnesy przylegają do wciśniętego guzika tym samym końcem co przed wciśnięciem.

Niestety, do zabawki Jasia dobrał się niezdarny Stasiu, który przypadkiem upuścił ją na ziemię, co sprawiło, że wszystkie magnesy powypadały na zewnątrz. Przerażony tym faktem szybko powkładał je z powrotem do środka, tak aby pasowały odpowiednimi kolorami do guzików. Następnie, aby pozbyć się podejrzeń (przecież Stasiu nie umie ułożyć tej układanki), dla wybranych par magnesów pozamieniał on je ze sobą miejscami. Mimo wszystko boi się on, że Jasiu wykryje fakt pomieszania magnesów, gdyż nie da się ich już poprawne ułożyć. A może Ty jesteś w stanie to zweryfikować?

Powyższe obrazki przedstawiają przykładowe ustawienia magnesów w zabawce Jasia. Na wszystkich obrazkach kółka z liczbami oznaczają guziki, a dwukolorowe krawędzie oznaczają magnesy. Rysunki w górnym rzędzie pokazują w jaki sposób uzyskać początkowe ustawienie magnesów dla pierwszego przypadku testowego, poprzez dwukrotne wciśnięcie guzika 4 (jednokrotne wciśnięcie spowodowałoby obrót w lewą stronę), a następnie wciśnięcie guzika 1. Dolne rysunki przedstawiają ułożenia magnesów z pozostałych dwóch przypadków testowych.

Wejście

W pierwszym wierszu wejścia podana jest liczba przypadków testowych T.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite N i M, oznaczające kolejno liczbę guzików oraz magnesów znajdujących się w zabawce.

W kolejnych M wierszach każdego przypadku testowego znajdują się opisy ułożeń kolejnych magnesów. Każdy z nich zawiera cztery liczby całkowite v₁, v₂, c₁, c₂ oznaczające że dany magnes przylega do guzików v₁ i v₂, a kolory jego końców to odpowiednio c₁ i c₂.

Kolejność magnesów przylegających do każdego guzika jest taka sama jak kolejność tych magnesów na wejściu.

Wyjście

Na wyjściu dla każdego testu wypisz jedno słowo TAK, jeżeli pierwotny układ magnesów jest możliwy do uzyskania za pomocą poprawnych ruchów, rozpoczynając w podanym na wejściu układzie. W przeciwnym przypadku wypisz jedno słowo NIE.

Ograniczenia

1 ≤ T ≤ 100, 3 ≤ N ≤ 10 000, 2 ≤ M ≤ 10 000, 1 ≤ v₁, v₂, c₁, c₂ ≤ N.

Suma wartości M we wszystkich przypadkach testowych nie przekroczy 10 000.

Przykłady

3
4 5
1 2 1 4
2 3 2 3
3 4 2 4
4 1 4 3
2 4 1 2
5 5
1 2 2 1
2 3 3 2
3 4 4 3
4 5 5 4
5 1 1 5
4 3
1 2 1 4
1 3 1 2
1 4 1 3

TAK
NIE
TAK