Problem description

W szkole Jasia odbywa się właśnie dyskoteka. Panują tam dość nietypowe konwenanse, bowiem do każdej piosenki to panie zapraszają panów do tańca. Panowie ustawiają się w kółku, a każda pani ma sobie wybrać partnera. Każda pani ustala przedział panów na kółku, z którymi mogłaby ewentualnie zatańczyć. Teraz pojawia się problem – należy przyporządkować paniom partnerów do tańca. Rzecz jasna, w danym tańcu jeden pan może tańczyć tylko z jedną panią. Czy potrafisz napisać program, który sprawdzi czy da się każdej pani przyporządkować swojego partnera? Sprawdźmy to!

Napisz program, który: wczyta opis wymagań pań dla każdej piosenki, powyznacza czy istnieją przyporządkowania partnerów i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę piosenek. W kolejnych wierszach znajdują się opisy sytuacji dla każdej piosenki.

W pierwszym wierszu opisu znajdują się dwie liczby naturalne N oraz M, oddzielone pojedynczym odstępem i określające kolejno: liczbę panów oraz liczbę pań. W kolejnych M wierszach znajduje się opis wymagań dla każdej z kolejnych pań. Każdy opis składa się z dwóch liczb naturalnych a_i oraz b_i, oddzielonych pojedynczym odstępem i określających kolejno: numer pierwszego oraz numer ostatniego pana akceptowanego przez i-tą panią (przedział akceptowanych panów biegnie zawsze zgodnie z ruchem wskazówek zegara).

Panowie są ponumerowani kolejnymi liczbami naturalnymi od 0 do N − 1 włącznie zgodnie z ruchem wskazówek zegara.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy, po jednym dla każdej piosenki. W każdym wierszu powinno się znaleźć jedno słowo TAK, jeśli jest możliwe przyporządkowanie każdej pani partnera do tańca zgodnie z jej wymaganiami lub NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ Q ≤ 20, 1 ≤ N, M ≤ 100 000.

Przykład

3
3 3
1 2
1 0
1 1
7 6
0 2
1 3
0 2
1 3
2 3
5 6
4 4
0 2
2 0
1 3
3 1

TAK
NIE
TAK