B. Махмуд, Ехаб и двудольность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Махмуд и Ехаб продолжают свои приключения! Каждый житель Злой Страны знает, что Доктор Зло любит двудольные графы, особенно деревья.

Дерево — это связный граф без циклов. Двудольный граф — это граф, вершины которого можно разбить на 2 множества таким образом, что для любого ребра (u, v) графа вершины u и v лежат в разных множествах. Более формальное определение дерева и двудольного графа дано ниже.

Доктор Зло дал Махмуду и Ехабу дерево, состоящее из n вершин и сказал добавлять рёбра таким образом, чтобы граф оставался двудольным, а также в нём не было петель и кратных рёбер. Какое максимальное число рёбер они могут добавить?

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

В первой строке дано целое число n — число вершин в дереве (1 ≤ n ≤ 105).

В следующих n - 1 строках содержатся пары целых чисел u и v (1 ≤ u, v ≤ n, u ≠ v) — описание рёбер дерева.

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

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

Выведите одно число — максимальное число рёбер, которые Махмуд и Ехаб могут добавить в граф.

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

Определение дерева: https://ru.wikipedia.org/wiki/Дерево_(теория_графов)

Определение двудольного графа: https://ru.wikipedia.org/wiki/Двудольный_граф

В первом тестовом примере единственное ребро, которое можно добавить в граф, чтобы избежать появления петель и кратных рёбер — это (2, 3), но его добавление сделает граф не двудольным.

Во втором тестовом примере Махмуд и Ехаб могут добавить рёбра (1, 4) и (2, 5).