S1 - Semester 1

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

Ondrej aj tento rok organizuje Letnú kapustnicu na záver semestra (26.06.2024) pre zamestnancov aj študentov informatiky na PF UPJŠ. Ondrej chce túto informáciu rozšíriť medzi všetkými zamestnancami (osobne alebo mailom) aj študentami rôznych ročníkov (rôzne sociálne siete). Ondrej je však navyše strašne lenivý, a teda by nerád strávil šírením informácie viac času, ako je nevyhnutné. Ondrej o každej osobe vie, s ktorými ďalšími osobami sa kamaráti, a tiež vie, že ak niekomu túto zaujímavú informáciu povie, dozvedia sa ju rýchlo aj všetci jeho kamaráti. Vašou úlohou je zistiť, najmenej koľkým osobám musí Ondrej povedať informáciu, aby sa ju dozvedeli všetci.

Úloha

Pre zadané vzťahy v rámci študentov a zamestnancov určte počet osôb, ktorým musí Ondrej 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≤100, 0≤M≤200). N je počet osôb, 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 osobami – každý riadok obsahuje 2 prirodzené čísla z intervalu 1 až N určujúce dvojicu ľudí, ktorí sa navzájom kamarátia a preposielajú si informácie.

Výstup

Pre každú testovaciu sadu vypíšte jediný riadok obsahujúci jediné prirodzené číslo, počet ľudí, ktorým musí Ondrej povedať informáciu, aby sa ju dozvedelo všetkých N osôb.

Príklad

Vstup:

Výstup:

Pozn.: Ondrej informáciu povie napríklad osobe číslo 4, ktorá ju oznámi osobe číslo 2, ktorá ju ďalej oznámi osobe číslo 1. Osoba 3 sa s nikým nekamaráti, teda Ondrej musí infroemáciu povedať ešte aj jej.)

22 Finále