7137번 - Teed 다국어

문제

Bytelandis on $N$ linna (tähistatud 1ドル \ldots N$), mida ühendavad $M$ kahesuunalist maanteed. Iga kahe linna vahel on ülimalt üks tee ja iga tee otspunkid on kaks erinevat linna.

Küll aga pole kindel, et need teed võimaldavad liikuda igast linnast igasse teise. Seega jagab teedevõrk Bytelandi piirkondadeks, kus iga piirkonna sees on võimalik teid pidi liikuda igast linnast igasse teise (võimalik, et vahepeal ka muid linnu läbides), aga eri piirkondade linnade vahel liiklemiseks tuleb kasutada lennukeid.

Nüüd plaanitakse Bytelandis teereformi. Ametnikud on otsustanud rajada täpselt $K$ uut teed, kuid pole teada, milliste linnade vahele uued teed ehitatakse. Niipalju on siiski kindel, et iga uue tee otspunktid on kaks erinevat linna, mille vahel veel ei ole maanteed.

On selge, et uute teede rajamine võib muuta ka riigi jaotust piirkondedeks. Näiteks kui riigis on $N = 6$ linna vahel alguses $M = 2$ maanteed, vastavalt linnade 1ドル$ ja 2ドル$ ning linnade 3ドル$ ja 4ドル$ vahel, siis on riigis neli piirkonda: esimesse kuuluvad linnad 1ドル$ ja 2ドル,ドル teise linnad 3ドル$ ja 4ドル,ドル kolmandasse linn 5ドル$ ja neljandasse linn 6ドル$. Kui $K = 3$ uut teed rajatakse linnade 1ドル$ ja 4ドル,ドル 2ドル$ ja 4ドル$ ning 2ドル$ ja 3ドル$ vahele, väheneb regioonide arv sellega ühe võrra (endise jaotuse esimene ja teine regioon ühendatakse).

Kirjutada programm, mis leiab minimaalse ja maksimaalse võimaliku regioonide arvu riigis pärast $K$ uue tee rajamist.

입력

Tekstifaili esimesel real on tühikutega eraldatud täisarvud $N,ドル $M$ ja $K$ (2ドル \le N \le 10^5,ドル 0ドル \le M \le 10^5,ドル 1ドル \le K \le \min(10^9, \frac{N \cdot (N - 1)}{2} - M)$), vastavalt linnade, olemasolevate teede ja rajatavate teede arv.

Faili järgmisel $M$ real on igaühel kaks tühikuga eraldatud täisarvu $X_i$ ja $Y_i$ (1ドル \le X_i, Y_i \le N$), mis näitavad, et linnade $X_i$ ja $Y_i$ vahel juba on maantee.

출력

Tekstifaili ainsale reale väljastada kaks tühikuga eraldatud täisarvu, vastavalt minimaalne ja maksimaalne võimalik piirkondade arv pärast uute teede rajamist.

제한

힌트