Problem description

Baron Raphael z Wyspy Man wystawił do bitwy śnieżkowej przeciwko Johnowi Mouse’owi wiele oddziałów i właśnie przyszedł czas, by podzielić wszystkich żołnierzy na dwie flanki, z których jedną będzie dowodził Baron, natomiast drugą niejaki Charles Latin.

Żołnierze znają wiele legend, w których głównym bohaterem jest John Mouse i ich morale nie jest zbyt wysokie, ponieważ w każdej z nich John Mouse wygrywa wszelkie starcia i spory. Baron Raphael z Wyspy Man jest świadom nastrojów swoich żołnierzy, ale nie może sobie pozwolić na odwrót lub dezercję, dlatego zatrudnił prawdziwego specjalistę, który pomoże mu zidentyfikować żołnierzy podatnych na oślepiający blask legendy Johna Mouse’a.

Mike Music, bo tak zwał się ów specjalista, wytypował M par żołnierzy skłonnych do dezercji. Dla Barona kluczowe jest rozdzielenie pomiędzy różne flanki jak największej liczby takich par, tak by żołnierze wspólnie skłonni do dezercji znajdowali się daleko od siebie w różnych flankach.

Niestety, blask legendy Johna Mouse’a jest tak silny, że w całej armii jedynie jedna para żołnierzy skłonnych do dezercji może być w tej samej flance (wtedy Baron Raphael poprosi niejaką Iron Woman o przypilnowanie tej pary żołnierzy).

Do rozpoczęcia bitwy zostało niewiele czasu, dlatego Baron potrzebuje szybko dowiedzieć się czy warto skorzystać z usług Iron Woman, a jeśli tak, to na ile sposobów może wskazać jej parę żołnierzy do przypilnowania.

Napisz program, który wczyta opisy par żołnierzy skłonnych do dezercji, wyznaczy na ile sposobów można wybrać parę żołnierzy tak, by pozostałych można było rozmieścić pomiędzy dwoma flankami w taki sposób, by żadna para nie była w jednej flance i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się dodatnia liczba całkowita Q oznaczająca liczbę zestawów danych.

W pierwszym wierszu opisu zestawu danych znajdują się dwie dodatnie liczby całkowite N i M oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę żołnierzy w armii Barona Raphaela z Wyspy Man oraz wyznaczoną przez specjalistę znanego jako Mike Music liczbę par żołnierzy skłonnych do dezercji.

W każdym z następnych M wierszy opisu zestawu danych znajdują się po dwie dodatnie liczby całkowite A i B oddzielone pojedynczym odstępem i oznaczające numery żołnierzy składających się na parę skłonną do dezercji.

Wyjście

W i-tym spośród Q wierszy wyjścia powinna się znaleźć odpowiedź dla i-tego zestawu danych zgodna z poniższym opisem.

Jeśli usługi Iron Woman nie są niezbędne i da się podzielić żołnierzy tak, by wyeliminować ryzyko dezercji, odpowiedzią jest słowo NIE. W przeciwnym razie odpowiedzią jest nieujemna liczba całkowita oznaczająca na ile sposobów można w i-tym zestawie danych wybrać parę skłonnych do dezercji żołnierzy tak, by pozostałych można było rozmieścić pomiędzy dwoma flankami w taki sposób, by żadna para skłonna do dezercji nie była w jednej flance.

Ograniczenia

1 ≤ Q ≤ 500, 1 ≤ N ≤ 1 000 000, 0 ≤ M ≤ 2 000 000, ∑N + ∑M ≤ 20 000 000.

Podzadania

Przykład

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

NIE
1
0
7
0
3