ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Личное первенство УрГУ 2003

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Оборотень

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Ночь. Полная луна. Волчий вой. Удар когтистой лапы.
Нож. Лунная ночь. Трухлявый пень, в нём короткий нож с чёрной рукояткой. Кто знает, тот поймёт. В деревне беда. Оборотень.
В деревне не так уж много жителей. Многие приходятся друг другу родственниками. Только это и может помочь найти оборотня. Оборотень безжалостен, но его жертвами никогда не становятся его потомки. Оборотень может утопить в крови всю деревню, но никогда не тронет своих предков.
Про всех жителей деревни известно, кто кому приходится сыном или дочерью. Известен также и печальный список жертв оборотня. Программа должна помочь определить подозреваемых. Это было бы весьма трудной задачей, но есть одно важное условие, резко облегчающее дело: если у некоторого жителя деревни в этой деревне живёт какой-нибудь предок по той или иной линии, то в деревне живёт и его непосредственный предок по этой линии. Другими словами, если, например, отец матери некоторого жителя живёт в деревне, то и мать этого жителя тоже живёт там.

Исходные данные

В первой строке находится целое число N (1 < N ≤ 1000) — количество жителей деревни. Будем считать, что жители занумерованы числами от 1 до N. Далее следует описание родственных связей «ребёнок-родитель»: после­дова­тельность строк, в каждой из которых записано через пробел два числа — номер сына или дочери и номер отца или матери. Данные в списке корректны — для каждого жителя деревни указано не более двух родителей, циклы отсутствуют. После этого списка следует слово «BLOOD», записанное в отдельной строке. Далее следует список номеров жертв оборотня, по одному числу в строке.

Результат

Выведите через пробел в порядке возрастания номера всех тех жителей деревни, которые могут оказаться оборотнями. Если таких жителей нет, то следует вывести единственное число 0.

Примеры

исходные данныерезультат
8
1 3
3 6
4 5
6 2
4 6
8 1
BLOOD
3
8
4 5 7
6
1 2
3 2
1 4
3 4
2 6
5 2
5 4
BLOOD
2
5
0
Автор задачи: Леонид Волков
Источник задачи: Ural State University Personal Programming Contest, March 1, 2003
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1242. Оборотень