Kilka miesięcy temu, kiedy Jasio przygotowywał się do Świąt Bożego Narodzenia, tata Jasia kupił mu piękny zestaw światełek choinkowych. Zestaw to sieć światełek połączonych kablami. Jak czasami bywa, w zestawie nie było żarówek; należało ja dokupić osobno. Gdy Tata rozpakował zestaw i zobaczył, że nie ma w nim żarówek, bardzo się zdenerwował. Zanim wyszedł dokupić żarówki, Jasio zawołał go i powiedział mu, żeby nie kupował wszystkich żarówek tego samego koloru. Poddenerwowany Tata powiedział, że zamierza dokupić żarówki co najwyżej dwóch różnych kolorów. Mądry Jasio powiedział. Poczekaj, sprawdzę czy w ogóle jest sens kupować takie żarówki, a celem jego było powkręcanie żarówek w taki sposób, aby żadne dwie połączone kablem żarówki nie świeciły tym samym kolorem.
I tak do dzisiaj Tata nie uzyskał odpowiedzi. Pomóż Jasiowi, bo niedługo przyjdą kolejne Święta i Tata zdenerwuje się jeszcze bardziej gdy nie wykorzysta się zakupionego przez niego zestawu światełek.

Wejście

T - liczba testów. Każdy test podany jest w postaci:

• n,m - w pierwszym wierszu podane są dwie liczby; n - liczba światełek; m - liczba połączeń między nimi
• w kolejnych m wierszach podane są połączenia w postaci par (a,b) - oznaczających, że światełko o numerze a jest połączone ze światełkiem o numerze b.

Możesz założyć, że

• 1 ≤ n ≤ 10⁶
• 0 ≤ m ≤ 10⁶
• 1 ≤ a,b ≤ n

Wyjście

Dla każdego zestawu danych wypisz "TAK" lub "NIE" w zależności od tego, czy da się powkręcać żarówki co najwyżej dwóch różnych kolorów w taki sposób, aby każde połączone kablem żarówki świeciły na różne kolory.

Przyklad

Dla danych wejściowych

3
2 1
1 2

4 3
1 2
2 3
3 4

3
1 2
2 3
3 1

poprawną odpowiedzią jest

TAK
TAK
NIE

W pierwszym zestawie wystarczy aby żarówka 1 miała kolor bladoróżowy, a druga niebiesko-żólty :-). W drugim zestawie również da się kupić żarówki dwóch różnych kolorów, mianowicie:

1. kolor sinofioletowy
2. kolor szaro-turkusowy
3. kolor sinofioletowy
4. kolor szaro-turkusowy

W trzecim zestawie nie warto iść do sklepu, nawet gdyby były w nim żarówki sino-słabo-bladoniebiesko-lazurowego koloru.