8. Diverzita obedov

Diverzita obedov hmyzu je v súčasnom spoločenskom diskurze prekvapivo málo diskutovaná téma. V KSP sa však dlhodobo snažíme o vyváženú stravu pre všetkých - nech už ide o akékoľvek sústredenie či letnú školu. Je ale pravda, že na hmyz sme doteraz veľmi nemysleli. Niektorí by dokonca mohli oprávnene namietať, že vôbec. Práve preto nastáva zmena. Zmena paradigmy, aká sa neobjavuje každé kolo, každú sériu, ba dokonca ani každý ročník. A keďže skutočná zmena musí prísť zdola, rozhodli sme sa zapojiť vás, milí riešitelia — ako inak než tematickou úlohou!

Bol raz jeden strom. A na ňom žilo mnoho rôznych druhov hmyzu. Ako to už v prírode chodí, silnejší hmyzáci mohli na obed zjesť tých slabších a následne obsadiť ich miesto na strome. Všetci hmyzáci však túžili po jedinom — mať možnosť zjesť čo najviac iných hmyzákov a získať tak čo najväčšiu diverzitu obedov. Bolo im jasné, že nemožno vyhovieť každému. No boli by radi, keby boli po strome rozmiestnení tak, aby bol súčet diverzít ich obedov čo najväčší.

Úloha

Je zadaný strom. Dobrú cestu nazveme takú cestu v strome, ktorej čísla vrcholov tvoria klesajúcu postupnosť dĺžky aspoň \(2\). Úlohou je zistiť, koľko najviac dobrých ciest sa môže v strome nachádzať po ľubovoľnom prečíslovaní vrcholov.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 200000\)) udávajúce počet vrcholov stromu.

Nasleduje \(n - 1\) riadkov, ktoré popisujú hrany daného stromu. Na každom z nich sú čísla \(u, v\) (\(1 \leq u, v \leq n\)), ktoré označujú, že medzi vrcholmi \(u\) a \(v\) je hrana.

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

V druhej sade navyše platí, že všetky vrcholy majú stupne \(\leq 10\).

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo - najväčší počet dobrých ciest, ktorý vieme dosiahnuť prečíslovaním vrcholov.

Príklad

Input:

5
1 2
1 3
1 4
4 5

Output:

9

Ak prečíslujeme vrcholy \(1, \dots, 5\) postupne na \(3, 4, 5, 2, 1\), tak dostaneme \(9\) dobrých ciest.

Input:

8
5 6
1 4
2 8
3 6
1 3
3 8
3 7

Output:

22