D. Пингвин Поло и дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У маленького пингвина Поло есть дерево — неориентированный связанный ациклический граф, в котором n вершин и n - 1 ребро. Будем считать, что вершины дерева пронумерованы целыми числами от 1 до n.

Сегодня Поло интересует следующая задача: найти количество пар путей, у которых нет ни одной общей вершины. Более формально, нужно найти количество четверок целых чисел a, b, c и d таких, что:

  • 1 ≤ a < b ≤ n;
  • 1 ≤ c < d ≤ n;
  • не существует такой вершины, которая одновременно лежит на кратчайшем пути от вершины a до вершины b и от вершины c до вершины d.

Под кратчайшим путем между двумя вершинами подразумевается путь, кратчайший по количеству ребер.

Помогите Поло, решите эту задачу.

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 80000) — количество вершин дерева. В каждой из следующих n - 1 строк задана пара целых чисел ui и vi (1 ≤ ui, vi ≤ n; ui ≠ vi) — i-тое ребро дерева.

Гарантируется, что заданный граф является деревом.

Выходные данные

В единственной строке выведите целое число — ответ на задачу.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
4
1 2
2 3
3 4
Выходные данные
2