Bajtogóra jest małym miastem, w którym istnieje tylko jedna szkoła. Niestety, ostatnio w tej szkole niektóre dzieci dość mocno się nie lubią i bardzo często dochodzi do bójek między nimi. Dyrekcja postanowiła zażegnać kryzys budując kolejną szkołę (niestety tylko na jedną ich stać) i rozdzielając nielubiących się uczniów.
Nauczycielom, po długich obserwacjach, udało się stworzyć listę par dzieci, które się nie lubią (to uczucie jest zawsze odwzajemnione). Zrobiwszy to, poprosili Ciebie o rozdzielenie uczniów do dwóch szkół tak by w obrębie każdej ze szkół żadna para się nie nie lubiła (o ile to jest w ogóle możliwe).
Pierwsza linia wejścia zawiera jedną liczbę całowitą dodatnią, mówiącą ile na wejściu pojawi się zestawów testowych. Każdy zestaw zaczyna się od pary liczb całkowitych N i M (2 ≤ N ≤ 500, M ≥ 0), oznaczających odpowiednio liczbę dzieci oraz liczbę wzajemnie nielubiących się par. Po nich następuje M par liczb (p,q) mówiących, które dzieci się nie lubią (1 ≤ p,q ≤ N, p≠q). Mamy gwarancję, że żadna para nie pojawi się na wejściu dwa razy (nawet z zaminionymi składowymi).
Dla każdego zestawu na wejściu należy wypisać na wyjście dokładnie jedną linię. Powinna ona zawierać słowo "NIE" jeżeli nie da się rozdzielić dzieci do dwóch różnych szkół. W przeciwnym wypadku należy wypisać ciąg liczb reprezentujący zbiór uczniów przydzielonych do jednej ze szkół (siłą rzeczy niewymienione dzieci są przydzielone do tej drugiej). Ciąg musi być zakończony liczbą -1. W przypadku wielu prawidłowych odpowiedzi należy wypisać dowolną z nich.
3 3 2 1 2 3 2 3 3 1 2 3 2 1 3 4 4 1 2 2 3 3 4 4 1
2 -1 NIE 1 3 -1