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.
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.