Koniec kola: 20. apríl 2020 23:59
19 dní
Počet bodov:
Popis:  12b
Program:  8b

Krízový štáb KSP musí zasadnúť, no vzhľadom na aktuálnu epidémiu, nikto nikomu neverí. Nikto predsa nechce nikoho nakaziť a ani nece byť nakazený. Teda nie zase každý každému. Niektorí niekomu predsa len veria. Napríklad takému Krtkovi nikto neverí, lebo stále niekam behá, chodí na všetky stretká a stretáva veľa ludí. Naopak Samovi verí takmer každý, lebo všetci vedia, že celý deň sedí za počítačom a niečo kódi. Aby bola na zasadnutí krízového štábu dobrá atmosféra, chceme, aby mal každý ľudí, ktorím verí hneď vedľa seba.

Úloha

Krízový štáb má \(n\) členov a zasadá za okrúhlym stolom. Títo členovia majú dokopy \(m\) požiadaviek tvaru \(x y\) čo znamená, že člen číslo \(x\) verí členovi číslo \(y\). Dokážeme usadiť všetkých členov tak, aby každý člen mal všetkých ľudí, ktorím verí priamo vedľa seba?1

Formát vstupu

Na prvom riadku sa nachádzajú dve čísla \(n\) a \(m\), (\(1\leq n,m \leq 100\,000\)) počet členov krízového štábu a počet ich požiadavok. Nasleduje \(m\) riadkov tvaru \(x_i y_i\), (\(0\leq x_i,y_i<n, x_i \not = y_i\)) ktoré hovoria, že člen číslo \(x_i\) verí členovi číslo \(y_i\).

Formát výstupu

Vypíšte jeden riadok so slovom ano, ak sa dá usadiť všetkých členov tak, aby bola na zasadnutí dobrá atmosféra alebo nie, ak sa to nedá.

Príklady

Input:

2 1
0 1

Output:

ano

Krizový štáb má dvoch členov a jeden z nich verí tomu druhému, takže keď ich posadíme vedľa seba, všetky podmienky budú splnené.

Input:

4 3
0 1
0 2
0 3

Output:

nie

Člen číslo 0 verí trom ďalším členom, ale priamo vedľa seba môže mať len dvoch ľudí, takže nevieme splniť všetky jeho požiadavky zároveň.

Input:

5 3
0 2
0 1
3 0

Output:

nie

Ak má vedľa 0 sedieť 1 aj 2, už nemôže sedieť 3 vedľa 0.


  1. Ak napríklad niekto nikomu neverí, je vlastne jedno kto pri ňom sedí.↩︎

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.