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

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

HotLog


 

Космические путешествия

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

3141 год. Космические путешествия с использованием подпространственных телепортирующих туннелей уже давно не новинка. Однако еще не во всех частях Межгалактической Федерации Землян сеть таких туннелей достаточно развита.

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

На каждой планете установлена подстанция, которая обеспечивает работу всех туннелей, которыми эта планета соединена с другими. Если эта подстанция перестает работать (например, из-за неполадок или из-за того, что ее закрывают на профилактический ремонт), то все туннели, одним из концов которых является эта планета, перестают работать. Вследствие этого для некоторых других планет может исчезнуть возможность добраться от одной до другой. Будем называть планеты, подстанции которых обладают описанным свойством, важными.

Поясним более формально. Планета u называется важной, если после того, как туннели, одним из концов которых является u, перестанут работать, появятся хотя бы две такие планеты v и w, что из v нельзя добраться до w по оставшимся туннелям.

Задана схема гиперпространственных туннелей в рассматриваемой звездной системе. Ваша задача – написать программу, которая вычисляет количество важных планет в этой звездной системе.

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

Первая строка входного файла INPUT.TXT содержит n – количество планет в звездной системе (1 ≤ n ≤ 100). Далее следуют n-1 строка, каждая из которых описывает один туннель и содержит два числа: u и v – номера планет, соединенных соответствующим туннелем (1 ≤ u, v ≤ n, u ≠ v). Планеты пронумерованы натуральными числами от 1 до n.

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

В выходной файл OUTPUT.TXT выведите количество важных планет.

Примеры

INPUT.TXTOUTPUT.TXT
14
1 2
1 3
1 4
1
25
1 2
2 3
2 4
4 5
2

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Дороги
 B. Светофорчики
 C. Цветной дождь
 D. Издевательство
 E. Эволюция
 F. Космические путешествия

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru



Изготовление лестницы-стула.