M - Meškanie

Cez víkend sa v Prahe konala súťaž v programovaní pre vysokoškolské tímy ACM ICPC - CERC 2018. Vysokoškolský učiteľ Rasťo, spolu s 3 študentami, pri návrate späť nočným vlakom do Košíc zostal stáť v zmeškanom vlaku viac ako 8 hodín z prevádzkových dôvodov (námraza trakčného vedenia). Nestihol sa teda dostaviť na výučbu a musel zrušiť výučbu. Ako ale túto informáciu z vlaku rozoslať všetkým zainteresovaným? Kolegom môže poslať e-mail, ale nie všetci študenti čítajú často maily zo školskej emailovej adresy. Zopár ich už komunikovalo mailom, tak má aj ich súkromné emailové adresy. No a samozrejme info môže dať na stránku predmetu, či zverejniť cez nejakú sociálnu sieť. Ako zabezpečiť, aby sa všetci túto informáciu dozvedeli?

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 spolužiakov, 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 komunikačných kanáloch – každý riadok obsahuje 2 prirodzené čísla z intervalu 1 až N určujúce dvojicu ľudí, ktorí navzájom kominukujú.

Výstup

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

Príklad

Vstup

1
4 2
1 2
2 4

Výstup

2

(Rasťo pošle informáciu napríklad osobe číslo 4, ktorá ju oznámi osobe číslo 2, ktorá ju ďalej oznámi osobe číslo 1. Osoba 3 s nikým nekomunikuje, teda učitel musí informáciu povedať ešte aj jej.)