2. Aerolinkové ceny

Nemenovanej spoločnosti sa podarilo navrhnúť dokonalý systém, ako čo najefektívnejšie navrhnúť lety medzi ľubovoľnou skupinou miest tak, aby nebolo treba príliš veľa prestupovať, nemuseli sme chodiť z Bratislavy do Trnavy cez Košice… No, určite si viete aj sami predstaviť mnohé nepríjemnosti, ktoré by mohli nastať, keby lety neboli naplánované rozumne. Čo ale ešte nevymysleli je, že koľko budú stáť jednotlivé lety. Bez veľkého rozmýšľania sa rozhodli priradiť mestám unikátne hodnoty, a cenu letu medzi dvomi mestami určovať ako súčet ich hodnôt. Už teda stačí iba mestám priradiť hodnoty. Lenže ako na to? Hlavným cieľom spoločnosti je samozrejme zarobiť čo najviac. Pomôžte spoločnosti vymyslieť systém ohodnocovania miest tak, aby súčet cien všetkých letov bol čo najväčší.

Úloha

Vašou úlohou bude priradiť \(n\) mestám rôzne hodnoty od \(1\) po \(n\) (vrátane), a to tak, aby súčet cien všetkých letov medzi nimi bol čo najväčší. Cenu letu medzi dvomi mestami vypočítame ako súčet hodnôt daných dvoch miest.

Formát vstupu

Na prvom riadku vstupu sú 2 medzerou oddelené čísla \(n\) a \(m\), kde \(n\) je počet miest a \(m\) je počet letov medzi nimi. Mestá sú očíslované od 0 po \(n-1\). Nasleduje \(m\) riadkov, každý z nich obsahuje 2 medzerou oddelené čísla miest, medzi ktorými sa pravidelne uskutočňujú lety. Rátame s tým, že ak existuje let z A do B, tak existuje aj let z B do A za presne rovnakú cenu, preto s nimi budeme rátať ako s jedným letom a zarátame jeho cenu iba raz (na vstupe nikdy nebude dvojica A B aj B A a taktiež nikdy nebudú na vstupe dva úplne rovnaké lety).

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte jediné číslo, a to najväčší možný súčet cien všetkých letov. Toto číslo môže byť veľké, a teda odporúčame použiť 64 bitovú premennú (long long v C++). Nezabudnite za číslom vypísať znak nového riadku.

Príklady

Input:

3 3
0 1
0 2
1 2

Output:

12

Keď priradíme mestám hodnoty (mesto:hodnota): 0:1, 1:2, 2:3, tak potom súčet cien všetkých letov by bol: (1 + 2) + (1 + 3) + (2 + 3) = 12. Môžeme si ale všimnúť, že v tomto prípade by sme pre ľubovoľné priradenie dostali rovnaký súčet.

Input:

4 2
0 1
1 2

Output:

13

Pre priradenie: 0:3, 1:4, 2:2, 3:1 získame takýto súčet: (3 + 4) + (4 + 2) = 13. Ak by sme ale zvolili napríklad priradenie: 0:1, 1:2, 2:3, 3:4, tak by bol súčet cien všetkých letov menší, a to: (1 + 2) + (2 + 3) = 8.

Input:

6 4
0 1
1 2
1 3
2 5

Output:

37