F - Farbenie

Č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 ]

Fero nepatri medzi studentov, z ktorych by ste si mali brat priklad. Na vyucovani nikdy nedava pozor, nic ho nezaujima, nerobi si domace ulohy, proste je to velky flakac. Minule dostali za ulohu pripravit si na chemiu model nejakej zluceniny. Fero dostal konkretne zluceninu dvoch prvkov A a B. Kedze ale nikdy nedaval pozor, nevedel, ake zakony platia pre dane prvky. Aby nestracal cas zbytocnym studovanim, zobral len nejaku hrbu guliciek, nastrkal do nich spilky a nejako vsetko pospajal. Takto dostal nejaku zluceninu. Teraz potrebuje niekotre gulicky zafarbit na cierno (prvok A) a zvysne na bielo (prvok B). Od kamaratov sa dozvedel, ze v zlucenine existuju vazby len medzi A a B. Medzi dvoma rovnakymi atomami vazby neexistuju. Ma teda nejaky model, no vobec nevie, ako ho ma farbit. Na zaciatok by mu stacilo, keby aspon vedel, ci sa to takto zafarbit da. Skuste tomuto lajdakovi pomoct.

Uloha

Na vstupe dostanete pocet guliciek a spojenia medzi nimi. Vasou ulohou je zistit, ci je mozne gulicky zafarbit dvoma farbami tak, aby gulicky s rovnakou farbou neboli spolu spojene.

Vstup

Prvy riadok vstupu obsahuje cele kladne cisla N a M, N je pocet guliciek a M je pocet vazieb. 1 ≤ N,M ≤ 100. Dalsich M riadkov obsahuje po dve cisla, dvojice guliciek, ktore maju spolocnu vazbu. Gulicky su cislovane od 1. Vazba sa na vstupe vyskytne maximalne raz. Mozete predpokladat, ze vsetky gulicky tvoria jeden komponent, teda sa chodenim po vazbach da dostat z kazdej gulicky do kazdej.

Vystup

Na vystup vypiste text Ano, ak taketo zafarbenie existuje, inak napiste Nie.

Priklad 1

Vstup:

Vystup:

Nie

Vysvetlenie:

Vstupny model je vlastne trojuholnik. Ak zafarbite jeden vrchol nejako farbou, tak musite potom dalsie dva zafarbit druhou. A to nemozete, lebo potom maju dve spojene gulicky rovnaku farbu.

Priklad 2

Vstup:

Vystup:

Ano

Vysvetlenie:

Model je vlastne stvorec. Ak zafarbite jeden vrchol bielou farbou, tak jeho dva susedne vrcholy musite zafarbit ciernou farbou. Tie nie su priamo spojene, takze to mozete spravit. S nimi susedi uz len jeden nezafarbeny vrchol, ktory musite zafarbit bielou farbou.

Problem by Samuel BWPOW Kupka

DS2004