У маленького пингвина Поло есть дерево — неориентированный связанный ациклический граф, в котором n вершин и n - 1 ребро. Будем считать, что вершины дерева пронумерованы целыми числами от 1 до n.
Сегодня Поло интересует следующая задача: найти количество пар путей, у которых нет ни одной общей вершины. Более формально, нужно найти количество четверок целых чисел a, b, c и d таких, что:
- 1 ≤ a < b ≤ n;
- 1 ≤ c < d ≤ n;
- не существует такой вершины, которая одновременно лежит на кратчайшем пути от вершины a до вершины b и от вершины c до вершины d.
Под кратчайшим путем между двумя вершинами подразумевается путь, кратчайший по количеству ребер.
Помогите Поло, решите эту задачу.
Выходные данные
В единственной строке выведите целое число — ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
2 3
3 4
|
2
|