Runda 22 [Basic] - Stół

06.06.2011 - Damian Rusak

Zadanie tygodnia

runda 22; kategoria Basic

Limit czasowy: 3s; Limit pamięciowy: 64MB

Stół

Bardzo Ważna Firma, której prezesujesz, ma odbyć spotkanie nowowybranego zarządu. Nie jest to łatwe zadanie, na szczęście to Ty masz okazję ten zarząd wybrać. Wiesz dobrze o licznych zatargach i osobistych niechęciach wszystkich swoich podwładnych. Spotkanie ma się odbyć przy okrągłym stole. Zależy Ci na tym, aby spotkanie przebiegło w miłej atmosferze i bez zbędnych emocji, dlatego pragniesz, aby każde dwie siedzące obok siebie osoby lubiły się. Ponadto aby uniknąć sytuacji, w której zarząd nie będzie mógł podjąć jakiejś ważnej decyzji z powodu remisu przy głosowaniu, liczba wybranych osób powinna być nieparzysta. Ponadto powinna ona być większa niż 1.

Zastanawiasz się, czy to w ogóle możliwe... sprytny program powinien pomóc Ci w odpowiedzi na to pytanie! Wiesz dobrze, którzy Twoi podwładni lubią się wzajemnie.

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $t$ - liczbę zestawów testowych. ( $1 \leq t \leq 10$ ) Pojedyńczy zestaw testowy opisany jest poniżej.

Pierwsza linia zestawu zawiera dwie liczby całkowite $n$ i $m$ - kolejno liczbę Twoich pracowników i liczbę par lubiących się pracowników. ( $1 \leq n,m \leq 10^{6}$ ). Podwładni są numerowani liczbami od $1$ do $n$ . W kolejnych $m$ liniach znajdują się pary $a_{i}$ $b_{i}$ oznaczające, że podwładni o numerach $a_{i}$ i $b_{i}$ lubią się nawzajem ( $a_{i}$ lubi $b_{i}$ i $b_{i}$ lubi $a_{i}$ ). Każda para wystąpi w danym zestawie co najwyżej raz.

Po każdym zestawie testowym następuje wolna linia.

Wyjście:

Dla każdego zestawu testowego należy wypisać w osobnej linii TAK jeśli można wybrać zarząd o nieparzystej liczbie członków, tak, żeby usadzić ich dookoła stołu i każdy sąsiadował z osobami które lubi, a w przeciwnym przypadku należy wypisać NIE.

Przykład:

4 4

1 2

2 3

3 1

4 1

7 9

1 2

4 7

5 2

5 4

7 2

1 4

6 1

5 6

6 3

Wyjście:

TAK

NIE

Wyjaśnienie: w pierwszym przykładzie do zarządu można wybrać osoby 1,2,3 i w takiej kolejności usadzić je dookoła stołu. W drugim przykładzie wybranie zarządu o żądanych własnościach jest niemożliwe.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Ocena:

Twoja ocena: Brak