Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Кактусы

(Время: 1 сек. Память: 16 Мб Сложность: 78%)

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

Дерево можно превратить в кактус, добавив в него несколько ребер (поскольку дерево само является кактусом, то можно не добавлять ребер вообще). Вообще говоря, может существовать несколько способов превратить дерево в кактус. Количество способов сделать это назовем кактусастостью дерева.

Например, кактусастость дерева, изображенного на картинке слева, равна 12. Двенадцать кактусов, в которые оно может быть превращено, изображены справа.

Для заданного дерева требуется найти его кактусастость.

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

Первая строка входного файла INPUT.TXT содержит одно целое число n - количество вершин в дереве (1 ≤ n ≤ 200). Следующие n-1 строк задают ребра дерева.

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

В выходной файл OUTPUT.TXT выведите единственное целое число - кактусастость заданного дерева.

Пример

INPUT.TXTOUTPUT.TXT
16
1 3
2 3
3 4
4 5
4 6
12

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ