Відстань до LCA

Обмеження: 2 сек., 256 МіБ

Зеник і Марічка мають кореневе неорієнтоване дерево із \(n\) вершин. Усі вершини пронумеровані цілими числами від 1 до \(n\), включно, а вершина з номером 1 є коренем дерева.

Вони хочуть вибрати пару різних вершин \(a, b\). Після цього вони знаходять найнижчого спільного предка цих вершин — таку вершину \(c\), яка одночасно лежить на простому шляху від кореня до \(a\) та на простому шляху від кореня до \(b\), і є найдальшою від кореня. Далі вони знаходять два числа: \(dist(a, c)\) та \(dist(b, c)\) — відстань (кількість ребер) на простому шляху між відповідними вершинами.

Ваше завдання — знайти суму \(dist(a, c) \cdot dist(b, c)\) по всіх можливих парах \(a, b\) (\(1 \le a < b \le n\)).

Вхідні дані

У першому рядку задано одне ціле число \(n\) — кількість вершин дерева.

У наступних \(n-1\) рядках задано пари чисел \(u_i\) та \(v_i\), розділені пробілами — ребра дерева.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Обмеження

\(1 \le n \le 10^5\),

\(1 \le u_i, v_i \le n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 2 3 1 4	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 1 2 4 2 2 5 1 3 2 7 7 6	17