Runda 22 [Basic] - Stół

06.06.2011 - Damian Rusak
Trudność

 

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:

2
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.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com