Задано дерево из n вершин и n − 1 ребер, соответственно пронумерованных 1, 2, ..., n и 1, 2, ..., n − 1. Ребро i соединяет вершины ui и vi.

Для чисел L, R (1 ≤ L ≤ R ≤ n) объявим функцию f(L, R) следующим образом:

• Пусть S - множество вершин с номерами от L до R. Функция f (L, R) представляет собой количество компонент связности в подграфе, образованном только из множества вершин S и ребер, оба конца которых принадлежат S.

Вычислите

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

Первая строка содержит число n (1 ≤ n ≤ 2 * 105). Каждая из следующих n - 1 строк содержит две вершины (ui, vi) (1 ≤ ui, vi ≤ n) - ребро в графе.

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

Выведите значение суммы.

Пример

Имеются шесть возможных пар (L, R):

Для L = 1, R = 1, S = {1}, имеется 1 связная компонента.

Для L = 1, R = 2, S = {1, 2}, имеется 2 связные компоненты.

Для L = 1, R = 3, S = {1, 2, 3}, имеется 1 связная компонента, так как S содержит оба конца каждого из ребер 1, 2.

Для L = 2, R = 2, S = {2}, имеется 1 связная компонента.

Для L = 2, R = 3, S = {2, 3}, имеется 1 связная компонента, так как S содержит оба конца ребра 2.

Для L = 3, R = 3, S = {3}, имеется 1 связная компонента.

Сумма всех значений равна 7.