Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal(a) bodov. Ak si takýto typ úloh ešte nikdy neriešil(a), skús sa pozrieť, ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel(a) by si sa naučiť, môžeš skúsiť našu KSP School.
Ak máš hocijaké otázky k tejto úlohe, napíš Štepimu na [email protected].
Vedeli ste, že {insert_name} a {insert_name} spolu chodia? Ja som sa to dozvedel včera od Lucky, ktorej to povedala Sonička. A odkiaľ to vie Sonička? No, to už nikto nevie, klebety v Trojstene sa totiž šíria príliš rýchlo na to, aby to niekto stíhal sledovať.
Šírenie klebiet v Trojstene funguje tak, že vždy, keď niekto zistí nejakú klebetu, tak ju povie všetkým svojim kamarátom. Tí, keď sa to dozvedia, tak to povedia všetkým svojim kamarátom, a tak ďalej.
Nedávno som sa dozvedel jednu veľmi exkluzívnu klebetu a zaujímalo by ma, koľko ľudí sa ju dozvie, keď ju teraz začnem šíriť.
Ľudí v Trojstene si môžeme očíslovať $1$ až $n$. Na vstupe je zadaný počet ľudí $n$, počet kamarátstiev, a číslo, u koho sa klebeta na začiatku objaví.
Potom je na každom riadku popísané jedno kamarátstvo: dve čísla, ktoré znamenajú, že sa títo ľudia kamarátia. Kamarátstva sú vzájomné.
Zisti, ku koľkým ľuďom sa klebeta dostane.
Sú 4 sady vstupov, za každú je 25 bodov. V jednotlivých sadách:
| sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| počet ľudí $\leq$ | $10$ | $100$ | $1000$ | $100\,000$ |
| počet kamarátstiev $\leq$ | $20$ | $1000$ | $10\,000$ | $300\,000$ |
5 3 1
1 2
2 3
4 5
3
Máme $5$ ľudí, $3$ kamarátstva a klebeta začína u človeka $1$. Ten ju povie $2$-ke, tá ju povie $3$-ke, a potom sa už nemá kam ďalej šíriť.
4 3 3
1 2
2 4
4 1
1
Tentokrát sa mimo $3$ kamarátia všetci navzájom, ale $3$ sa nekamaráti s nikým, takže klebeta sa ku nikomu inému nedostane.