Лень — это плохо, не так ли? Поэтому мы решили приготовить задачу, чтобы наказать ленивых.
Вам дано дерево, вы должны посчитать количество способов убрать одно ребро, а затем добавить одно ребро так, чтобы получившийся граф был деревом, и в нем существовало совершенное паросочетание. Два способа считаются различными, если удаленные или добавленные ребра не совпадают. Добавленное ребро может совпадать с удаленным.
Совершенным паросочетанием называется подмножество ребер такое, что каждая вершина графа является концом ровно одного ребра.
Выходные данные
Выведите одно целое число — ответ на задачу.
Примечание
В первом примере имеются 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
2 3
3 4
|
8
|
|
2
|
5
1 2
2 3
3 4
3 5
|
0
|
|
3
|
8
1 2
2 3
3 4
1 5
5 6
6 7
1 8
|
22
|