Sparing w Programowaniu Zespołowym UAM & PP, 6.11.2004

Opis

Jako główny informatyk Politechniki Poznańskiej zostałeś poproszony o napisanie programu, który pozwoli sprawdzić czy możliwe jest przeprowadzenie wszystkich zajęć przewidzianych przez prowadzących. Głównym problemem jest tutaj przydział sal dla prowadzących. Twoim zadaniem będzie rozstrzygnięcie czy wszystkie zajęcia uda się pomieścić w ograniczonej liczbie sal, którymi dysponuje Uczelnia. Warto zauważyć, że jeśli w pewnej chwili czasu jakiś prowadzący kończy zajęcia to w tej samej chwili mogą się rozpocząć następne zajęcia w tej samej sali, czyli przedziały czasowe należy traktować jako przedziały otwarte. Jeśli jest to możliwe będziesz musiał także podać o ile mniej sal mogłaby posiadać Uczelnia, aby i tak możliwe było pomieszczenie tych zajęć.

Specyfikacja wejścia

W pierwszym wierszu znajduje się liczba D oznaczająca liczbę zestawów testowych. Dla każdego zestawu danych, w pierwszym wierszu znajdują się dwie liczby N, M (1 ≤ M, N ≤ 10^6), gdzie N to liczba zaplanowanych zajęć, natomiast M to liczba sal, którymi dysponuje Uczelnia. W kolejnych N wierszach znajdują się po dwie liczby naturalne A, B (0 ≤ A < B ≤ 10^9) oddzielone spacją oznaczające chwile rozpoczęcia i zakończenia zajęcia.

Specyfikacja wyjścia

Dla każdego zestawu danych wypisz w osobnej linii pojedyncze słowo NIE, jeśli kiedykolwiek zdarzy się sytuacja, że zabraknie sali dla prowadzącego, w przeciwnym wypadku wypisz pojedynczą liczbę naturalną równą ilości sal, które przez cały czas będą niewykorzystane.

Przykład

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

0
NIE