Sidevõrk

문제

[이미지 1]Sidevõrk koosneb $NN$ serverist, mis on nummerdatud $1\dots N1\; \backslash ldots\; N$, ja $N-1N\; -\; 1$ neid ühendavast kaablist. Võrk on sidus: igast serverist on võimalik andmeid edastada igasse teise serverisse. Kui mõni server rikki läheb, siis tema kaudu andmeid edastada ei saa, ja see võib põhjustada häireid ka teiste serverite vahelises sides. Sidefirma tahab hinnata, millised võivad olla tagajärjed, kui rikki läheb korraga kaks serverit.

Kui serverite rikkega jaguneb võrk $kk$ osaks, milles on vastavalt $a_{1}a\_1$, $a_{2}a\_2$, $\dots \backslash ldots$, $a_{k}a\_k$ serverit, siis on sellise võrgu sidususkoefitsient $C=a_1^2+a_2^2+\dots +a_k^{2}C\; =\; a\_1^2\; +\; a\_2^2\; +\; \backslash ldots\; +\; a\_k^2$. Näiteks kui kõrvaloleval joonisel kujutatud võrgus lähevad rikki serverid 1 ja 5, jaguneb võrk $33$ osaks, kus ühes osas on $22$ serverit (2 ja 4), teises osas $55$ serverit (3, 6, 11, 12 ja 8) ning kolmandas osas $33$ serverit (7, 9 ja 10). Selliselt jagunenud võrgu sidususkoefitsient on seega $C=2^2+5^2+3^2=38C\; =\; 2^2\; +\; 5^2\; +\; 3^2\; =\; 38$.

Kirjutada programm, mis leiab suurima ja vähima võimaliku sidususkoefitsiendi, kui antud võrgus lähevad rikki täpselt kaks serverit.

입력

Sisendi esimesel real on täisarv $TT$ ($1\le T\le 21\; \backslash le\; T\; \backslash le\; 2$). $T=1T\; =\; 1$ korral peab programm leidma maksimaalse, $T=2T\; =\; 2$ korral aga minimaalse võimaliku sidususkoefitsiendi.

Sisendi teisel real on serverite arv $NN$ ($3\le N\le {10}^{5}3\; \backslash le\; N\; \backslash le\; 10^5$).

Järgmisel $N-1N\; -\; 1$ real on igaühel kaks täisarvu $A_{i}A\_i$ ja $B_{i}B\_i$ ($1\le A_i\le N1\; \backslash le\; A\_i\; \backslash le\; N$, $1\le B_i\le N1\; \backslash le\; B\_i\; \backslash le\; N$), mis näitavad, et kaabel $ii$ ühendab servereid $A_{i}A\_i$ ja $B_{i}B\_i$.

출력

Väljastada üks täisarv, vastavalt $TT$ väärtusele sidususkoefitsiendi maksimum või miinumum.