20 anys del Jutge.org P42345

El Professor Oak està de celebració. Enguany, el Jutge.org, la pàgina web més estimada de tota la comunitat UPC, fa 20 anys. Sí, 20 anys enrere el Professor Oak i el Professor Small van crear aquesta plataforma.

El Professor Oak ha quedat molt satisfet de la festa d’aniversari. Hi ha dominat la Coca-Cola, els dònuts, les galetes i altres queviures de qüestionables propietats alimentícies, però també la felicitat per tots aquests anys i el desig perquè el Jutge.org segueixi endavant per molts anys més sense quedar plena de AI slop com la resta de l’Internet.

Ara bé, el Professor Oak encara té ganes per més. Com que no hi ha res que els estudiants de la FME estimin més que resoldre problemes d’algorísmia, el Professor Oak organitzarà un concurs improvisat a la FME. Desgraciadament, els ordinadors de les aules d’informàtica tenen un comportament ben curiós. Aquesta vegada, no es poden connectar a Internet, però sí que alguns d’ells es poden comunicar entre si, formant una mena de múltiples xarxes locals d’ordinadors. Per estalviar temps, el servei tècnic de la FME ha decidit connectar a la xarxa directament només uns pocs ordinadors, concretament un ordinador per cadascuna d’aquestes xarxes locals, de manera que actuï com a router per a la resta d’ordinadors de la seva xarxa. El servei tècnic necessita saber quantes connexions haurà de realitzar.

Podeu ajudar-los per tal que el Professor Oak pugui organitzar el seu concurs?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre d’ordinadors $n$ i el nombre de connexions entre ordinadors $m$. Després, segueixen $m$ parells d’enters $x,y$ que indiquen que l’ordinador $x$ i l’ordinador $y$ estan connectats.

Podeu suposar que $1<=n <=10^4$, $0 <= m <= 5n$, que els ordinadors es numeren de 0 a $n-1$ i que no hi ha més de dues connexions entre dos mateixos ordinadors $x,y$.

Sortida

Per cada cas, digueu quantes xarxes locals d’ordinadors hi ha (i.e. conjunts d’ordinadors que estan connectats entre si i no amb cap altre ordinador).

Pista

Feu una cerca en profunditat.