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

Лень — это плохо, не так ли? Поэтому мы решили приготовить задачу, чтобы наказать ленивых.

Вам дано дерево, вы должны посчитать количество способов убрать одно ребро, а затем добавить одно ребро так, чтобы получившийся граф был деревом, и в нем существовало совершенное паросочетание. Два способа считаются различными, если удаленные или добавленные ребра не совпадают. Добавленное ребро может совпадать с удаленным.

Совершенным паросочетанием называется подмножество ребер такое, что каждая вершина графа является концом ровно одного ребра.

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

Первая строка содержит одно целое число n (2 ≤ n ≤ 5·105) — количество вершин в дереве.

Каждая из следующих n - 1 строк содержит два целых числа a и b (1 ≤ a, b ≤ n) — концы ребер. Гарантируется, что заданный граф является деревом.

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

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

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

В первом примере имеются 8 вариантов:

  • ребро между 2 и 3 заменить на ребро между 1 и 3,
  • ребро между 2 и 3 заменить на ребро между 1 и 4,
  • ребро между 2 и 3 заменить на ребро между 2 и 3,
  • ребро между 2 и 3 заменить на ребро между 2 и 4,
  • ребро между 1 и 2 заменить на ребро между 1 и 2,
  • ребро между 1 и 2 заменить на ребро между 1 и 4,
  • ребро между 3 и 4 заменить на ребро между 1 и 4,
  • ребро между 3 и 4 заменить на ребро между 3 и 4.