Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Кактусы

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

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

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

Например, кактусастость дерева, изображенного на картинке слева, равна 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

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

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483