Teed

문제

Bytelandis on $NN$ linna (tähistatud $1\dots N1\; \backslash ldots\; N$), mida ühendavad $MM$ 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 $KK$ 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=6N\; =\; 6$ linna vahel alguses $M=2M\; =\; 2$ maanteed, vastavalt linnade $11$ ja $22$ ning linnade $33$ ja $44$ vahel, siis on riigis neli piirkonda: esimesse kuuluvad linnad $11$ ja $22$, teise linnad $33$ ja $44$, kolmandasse linn $55$ ja neljandasse linn $66$. Kui $K=3K\; =\; 3$ uut teed rajatakse linnade $11$ ja $44$, $22$ ja $44$ ning $22$ ja $33$ 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 $KK$ uue tee rajamist.

입력

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

Faili järgmisel $MM$ real on igaühel kaks tühikuga eraldatud täisarvu $X_{i}X\_i$ ja $Y_{i}Y\_i$ ($1\le X_i,Y_i\le N1\; \backslash le\; X\_i,\; Y\_i\; \backslash le\; N$), mis näitavad, et linnade $X_{i}X\_i$ ja $Y_{i}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.

3 1 1
1 2

1 1

6 2 3
1 2
3 4

1 3