HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > Алгоритмы и структуры данных — 2019. Набор задач 7 > problem:


F. Самый сложный предмет

Алгоритмы и структуры данных — 2019. Набор задач 7

Start: Nov.27.2020 at 08:00:00 AM
Finish: Dec.11.2021 at 08:00:00 AM
The contest is finished!
• Contest scoreboard

Contest problems

• Подсказки к задачам
• A. Граф
• B. Где ключи?
• C. Captcha
• D. Цикл
• E. Топологическая сортировка
• F. Самый сложный предмет
• G. Компоненты сильной связности
• H. Мосты

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

Самый сложный предмет
Самый сложный предмет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Макс, едва пережив очередной тяжёлый экзамен, задался вопросом — какая из дисциплин, преподаваемых в университете, является наиболее сложной?

Листая учебный план, Макс выяснил, что для изучения некоторых предметов необходимо предварительно освоить другие предметы. Так, например, чтобы изучать «Технологии программирования», нужно сдать «Основы программирования», перед «Цифровой схемотехникой» следует пройти «Электротехнику и электронику», а для «Высокопроизводительных вычислений» требуются «Алгоритмы и структуры данных» и «Машинно-ориентированное программирование».

Макс предположил, что чем больше у предмета список предварительных требований, тем сложнее этот предмет. Более формально, сложность 0 имеют предметы без предварительных требований, сложность 1 — предметы, основывающиеся хотя бы на одном предмете сложности 0, сложность 2 — предметы, основывающиеся хотя бы на одном предмете сложности 1, и так далее.

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

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

Первая строка содержит целое число N (1 ≤ N ≤ 104) — количество учебных предметов.

Вторая строка содержит N различных слов Si (1 ≤ |Si| ≤ 20), состоящих из строчных латинских букв и знаков подчёркивания, — названия каждого из предметов.

Третья строка содержит целое число M (0 ≤ M ≤ 105) — количество требований.

Следующие M строк описывают предварительные требования. Каждая из них содержит слова Aj и Bj и () — соответственно название предмета, который изучается ранее, и название предмета, который изучается позднее.

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

Выведите названия всех предметов, имеющих максимальную сложность, в алфавитном порядке.

Если сложность хотя бы одного из предметов не может быть определена, выведите Impossible.

Примеры

Входные данные
6
algorithms discrete_math higher_math history prog_basics prog_technologies
4
discrete_math algorithms
prog_basics prog_technologies
prog_basics algorithms
higher_math discrete_math
Выходные данные
algorithms
Входные данные
4
physics machine_learning electronics ai_systems
2
physics electronics
machine_learning ai_systems
Выходные данные
ai_systems electronics

Для отправки решений необходимо выполнить вход.

www.contester.ru