Градоначальник города Q недавно получил от руководства письмо о важности повышения рейтинга городов страны в связи с предстоящим годом «высоких рейтингов». На первом этапе необходимо выслать рейтинг города, вычисленный по новой методике, в столицу государства.
Мэр поручил аналитическому отделу рассчитать этот рейтинг.
В городе Q расположено N памятников архитектуры, которые пронумерованы от 1 до N и между собой связаны автобусными маршрутами. Известно, что таких маршрутов ровно N - 1 и они позволяют туристу проложить путь между любой парой памятников (возможно, с пересадками). Назовем «привлекательностью» пути от памятника A до памятника B функцию F(A, B) = D, где D – количество оплаченных автобусных маршрутов, необходимых для того, чтобы добраться от A до B.
Для привлечения большего числа туристов и, соответственно, повышения рейтинга мэр издал указ о том, что каждый второй маршрут на пути от некоторого памятника A до некоторого памятника B является бесплатным.
Вам необходимо вычислить рейтинг города, который определяется как сумма «привлекательностей» путей между всеми парами памятников архитектуры.
В первой строке располагается целое положительное число N — количество памятников архитектуры в городе Q (1 ≤ N ≤ 105). Далее в N - 1 строках раполагается по два числа Ai и Bi — номера памятников, между которыми проложен автобусный маршрут (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi).
В единственной строке выведите единственное число — привлекательность города Q.
3
1 2
1 3
3
8
1 3
8 1
4 3
5 2
3 6
7 6
5 6
42
