E - ㉍. výročie

Č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 ]

UPJŠ si tohto roku pripomenula 60. výročie svojho vzniku. Ako ale pozvať efektívne všetkých ľudí na takúto slávnosť? Študentom stačí jeden odkaz na Facebook-u, zamestnancom môžeme poslať emaily, ale čo s absolventami, ktorí už niekoľko rokov nemusia byť ani na Slovensku. Medzi každú skupinku komunikujúcich osôb stačí poslať jednu pozvánku, sami si ju šíria medzi sebou. Nájdite minimálny počet osôb, ktorým treba pozvánku zaslať.

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 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 kontaktoch medzi osobami – každý riadok obsahuje 2 prirodzené čísla z intervalu 1 až N určujúce dvojicu ľudí, ktorí navzájom komunikujú.

Výstup

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

Vstup

Výstup

(Pozvánka pôjde odobe čí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 pozvánku treba poslať aj jej.)

18 Domáce 1