5. Kandidát

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu conditions_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Jitke na [email protected]

Za siedmimi horami a siedmimi dolinami, v ďalekej krajine menom Trojsten sa chystajú prezidentské voľby. Kampane kandidátov sú v plnom prúde, no Emovi sa nepáči volebný program ani jedného z nich. Rozhodol sa teda sám vsúpiť do tohto kolotoču ako vhodný adept. No ak sa chce stať prezidentom, má pred sebou ešte dlhú cestu. Musí pozbierať dostatočný počet podpisov, aby mohol vôbec kandidovať a následne voľby vyhrať.

V Trojstene majú prezidentské voľby jednoduché pravidlá. Kandidát sa stane prezidentom ak sa pozná s každým občanom. Emo by rád vedel, či pozná každého občana, no má plné ruky práce so zháňaním podpisov. Pomôžte mu a zistite to preňho.

Úloha

Vašou úlohou je napísať program, ktorý na vstupe dostane zozmam známostí v Trojstene a zistí, či sa Emo pozná s každým občanom. Občan (aj Emo je občanom) sa s niekým pozná ak sa poznajú priamo alebo ob jedného človeka. Teda ak Emo pozná Andreja a Andrej pozná Timku, tak môžeme povedať, že aj Emo pozná Timku. Ak však Timka pozná Gabiku, ktorá inak nikoho iného nepozná, tak Emo Gabiku nepozná, pretože je to príliš vzdialená známosť.

Formát vstupu

Na prvom riadku vstupu sú tri celé čísla \(n\), \(m\) a \(e\). Číslo \(n\) (\(1 \leq n \leq 80\,000\)) je počet občanov Trojstenu, ktorí sú pre jednoduchosť očíslovaní od 1 po \(n\), číslo \(m (0 \leq m \leq 100\,000)\) je počet známostí a číslo \(e\) (\(1 \leq e \leq n\)) hovorí, ktorý občan je Emo.

Nasleduje \(m\) riadkov popisujúcich jednotlivé známosti. Na každom sú dve celé čísla \(a\), \(b\) (\(1 \leq a < b \leq n\)), ktoré udávajú, že občan s číslom \(a\) a občan s číslom \(b\) sa navzájom poznajú.

Formát výstupu

Na výstup vypíšte do jedného riadku slovo Ano ak sa Emo stane prezidentom alebo slovo Nie ak sa ním nestane. Do druhého riadku vypíšte vzostupne čísla občanov, ktorých Emo nepozná, oddelených medzerou. Ak pozná každého, do druhého riadku nevypisujte nič.

Hodnotenie

Príklady

Input:

5 5 1
1 2
1 3
1 4
2 3
2 5

Output:

Ano

Ema označuje číslo \(1\). Priamo pozná \(2, 3, 4\). Občana \(5\) pozná skrz občana \(2\).

Input:

6 5 2
1 2
3 6
3 4
2 3
2 5

Output:

Ano

Ema označuje číslo \(2\). Priamo pozná občanov \(1, 3, 5\). Občanov \(4, 6\) pozná skrz občana \(3\).

Input:

7 6 1
1 2
1 3
2 3
2 5
4 6
5 7

Output:

Nie
4 6 7

Ema označuje číslo \(1\). Priamo pozná občanov \(2, 3\). Občana \(5\) pozná skrz občana \(2\). Občania \(4\) a \(6\) sa poznajú len navzájom a Emo ich nepozná. Občan číslo 7 sa s Emom tiež nepozná, neexistuje totiž priamy známy Ema, ktorý by ho poznal.