Mini Liga 2

Dane jest drzewo o n wierzchołkach i n-1 krawędziach. Krawędzie są nieskierowane, każda z nich ma długość 1.

Jan postanowił zmodyfikować graf. Stworzył listę wszystkich ścieżek o długości 2 znajdujących się w drzewie. Następnie dla każdej ścieżki u - w - v, gdzie u, w, v to wierzchołki drzewa, dodał nieskierowaną krawędź o długości 1 pomiędzy wierzchołkami u i v.

Odpowiedz na pytanie, jaka jest suma najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w nowo powstałym grafie?

Wejście

W pierwszej linii wejścia znajduje się liczba wierzchołków n ∈ [2, 10⁵]. W kolejnych n-1 liniach znajdują się opisy krawędzi.

Opis każdej krawędzi składa się z dwóch liczb naturalnych u, v (1 ≤ u, v ≤ n; u ≠ v) określających numery wierzchołków, które są ze sobą połączone.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, jaka jest suma najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w nowo powstałym grafie.

Przykład

Wejście:

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

Wyjście:

68