C - Szkoły

Autor: Bartosz Nowierski

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).

Wejście

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, pq). Mamy gwarancję, że żadna para nie pojawi się na wejściu dwa razy (nawet z zaminionymi składowymi).

Wyjście

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.

Przykładowe wejście

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

Przykładowe wyjście

2 -1
NIE
1 3 -1