Кактусы
(Время: 1 сек. Память: 16 Мб Сложность: 78%)
Вершинный кактус - это связный неориентированный граф, каждая вершина которого лежит не более, чем на одном простом цикле.
Дерево можно превратить в кактус, добавив в него несколько ребер (поскольку дерево само является кактусом, то можно не добавлять ребер вообще). Вообще говоря, может существовать несколько способов превратить дерево в кактус. Количество способов сделать это назовем кактусастостью дерева.
Например, кактусастость дерева, изображенного на картинке слева, равна 12. Двенадцать кактусов, в которые оно может быть превращено, изображены справа.
Для заданного дерева требуется найти его кактусастость.
Входные данные
Первая строка входного файла INPUT.TXT содержит одно целое число n - количество вершин в дереве (1 ≤ n ≤ 200). Следующие n-1 строк задают ребра дерева.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число - кактусастость заданного дерева.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6
1 3
2 3
3 4
4 5
4 6 | 12 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
