Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BIPART - Światełka Choinkowe

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 ≤ 106
  • 0 ≤ m ≤ 106
  • 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 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.

 


Dodane przez:Rafal Nowak
Data dodania:2008-01-23
Limit czasu wykonania programu:0.180s-0.319s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO PERL6
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.