Z - OO

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

V ZOO UPJŠ je kvôli prestavbe potrebné dočasne premiestniť zvieratá zo svojich obydlí. Riaditeľstvo vybralo dve veľké ohrady, kde je možné dočasne tieto zvieratá umiestniť. Ošetrovatelia dostali za úlohu určiť, ktoré zvieratá sa majú do ktorej ohrady dočasne premiestniť. Všetci vieme, že nie každá dvojica zvierat môže byť spolu (pes naháňa mačku, mačka myš, ...).

Úloha

Určte, či je možné rozdeliť zvieratá do dvoch ohrád, aby si v ani jednej navzájom neubližovali.

Vstup

Prvý riadok obsahuje počet testovacích sád.

V prvom riadku každej sady sa nachádzajú dve čísla - N udávajúce počet zvierat a M počet dvojíc, ktoré si ubližujú.

Nasleduje M riadkov, každý obsahuje dve čísla zvierat, ktoré si ublížia, ak budú spolu.

Výstup

Výstupom programu je pre každú testovaciu sadu jeden riadok obsahujúci text "ANO" (ak je možné rozdeliť zvieratá do 2 skupín), resp. "NIE" (ak to nie je možné)

1≤N≤10 000, 0≤M≤20 000

Príklad

Vstup:

Výstup:

ANO
NIE

V prvej sade môžu byť spolu zvieratá 2,3,6,7 v jednej skupine, ostatné v druhej.

16 Domáce 1