eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Обмен местами

Обмен местами

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

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

При входе в карантинную зону животные должны пройти регистрацию у охраны. Охранник записывает вид животного, после чего животному разрешают присоединиться к концу очереди - стать на последнюю позицию. На другом конце очереди животных снова следует проверить: когда животному, находящемуся на первом месте в очереди, наконец разрешается войти в зону, свободную от охоты, другой охранник записывает вид животного. Таким образом, каждый охранник ведет список видов животных, записанный в хронологическом порядке, в котором животные зарегистрировались или выписались. Всего n животных, представляющих S видов, зарегистрировались (и, следовательно, выписались).

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

У Вас есть список тех пар видов животных, которые могут согласиться поменяться местами, находясь на соседних позициях в строке: этот список содержит L пар. Вам вручили список регистрации, который ведет первый охранник. В зависимости от того, какие животные решили поменяться местами, может быть возможно несколько контрольных списков. Какой из всех возможных списков идет первым в алфавитном порядке?

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

Состоит из следующих строк:

  • Строка 1 содержит три целых числа через пробел S (1S200), L (0L10000) и n (1n100000). S - количество видов животных, L - количество пар видов, которые дружат друг с другом, а n - количество животных, вышедших в очередь на ожидание.

  • Строка i + 2, для 0i < S, содержит название одного из представленных видов: это название состоит из одного слова с прописными буквами между "A" и "Z" и содержит от 1 до 20 букв.

  • Строка i + S + 2, для 0i < L, содержит два названия видов, разделенных пробелами a и b означающих что a и b дружат друг с другом.

  • Строка S + L + 2 представляет собой список входа и содержит n названий видов, разделенных пробелами: для всех 1kn, k - ое слово - это название вида животного в k - ой позиции.

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

Вывести в одной строке n слов w[0], ..., w[n-1], разделенных пробелами: список w[0], ..., w[n-1] среди всех возможных контрольных списков должен быть первым в алфавитном порядке.

Пример

Входные данные #1
3 2 6
ANTILOPE
CAT
ANT
CAT ANTILOPE
ANTILOPE ANT
ANT CAT CAT ANTILOPE CAT ANT
Выходные данные #1
ANT ANTILOPE CAT CAT CAT ANT
Источник 2019 ACM Southwestern Europe Regional Contest (SWERC), Париж, Январь 26 (2020), Задача G