P2 - Prezentácie ŠVK 2

Časový limit: 5s, 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 ]

Klebetná Veronika sa práve dozvedela, že tohtoročnú ŠVK v sekcii ANALÝZA DÁT, UMELÁ INTELIGENCIA A INFORMATIKA vyhral ... . Veronika nebude mať pokoja, kým túto informáciu nebudú poznať všetci študenti. Klebetná Veronika je však navyše strašne lenivá, a teda by nerada strávila šírením klebiet viac času, ako je nevyhnutné. Veronika o každom študentovi vie, s ktorými ďalšími študentmi sa kamaráti, a tiež vie, že ak niektorému študentovi povie klebetu, dozvedia sa ju rýchlo aj všetci jeho kamaráti. Vašou úlohou je zistiť, najmenej koľkým študentom musí Veronika povedať klebetu, aby sa ju dozvedeli všetci študenti.

Úloha

Pre zadané vzťahy v rámci študentov určte počet študentov, ktorým musí Veronika takúto čerstvú informáciu oznámiť.

Vstup

Prvý riadok vstupu obsahuje prirodzené číslo P≤20 určujúce počet testovacích sád.
Každá testovacia sada pozostáva z viacerých riadkov:
Prvý riadok testovacej sady obsahuje dve prirodzené čísla N, M (1≤N≤10 000, 0≤M≤20 000). N je počet študentov, ktorých pre jednoduchosť budeme ďalej označovať prirodzenými číslami od 1 po N.
Nasledujúcich M riadkov testovacej sady obsahuje informácie o vzťahoch medzi študentmi – každý riadok obsahuje 2 prirodzené čísla z intervalu 1 až N určujúce dvojicu ľudí, ktorí sa navzájom kamarátia.

Výstup

Pre každú testovaciu sadu vypíšte jediný riadok obsahujúci jediné prirodzené číslo, počet ľudí, ktorým musí Veronika povedať klebetu, aby sa ju dozvedelo všetkých N študentov.

Príklad

Vstup:

Výstup:

Pozn.: Veronika klebetu povie napríklad študentovi číslo 4, ktorý ju oznámi študentovi číslo 2, ktorý ju ďalej oznámi študentovi číslo 1. Študent 3 sa s nikým nekamaráti, teda Veronika musí klebetu povedať ešte aj jemu.)

UPJŠ ŠVK 2024