Обмен местами
Обмен местами
Животные ждут в очереди в карантинной зоне, прежде чем попасть в зону, свободную от охоты, где им будет легче жить.
При входе в карантинную зону животные должны пройти регистрацию у охраны. Охранник записывает вид животного, после чего животному разрешают присоединиться к концу очереди - стать на последнюю позицию. На другом конце очереди животных снова следует проверить: когда животному, находящемуся на первом месте в очереди, наконец разрешается войти в зону, свободную от охоты, другой охранник записывает вид животного. Таким образом, каждый охранник ведет список видов животных, записанный в хронологическом порядке, в котором животные зарегистрировались или выписались. Всего n животных, представляющих S видов, зарегистрировались (и, следовательно, выписались).
Однако животные могут заходить в очередь ожидания и выходить из нее в другом порядке. В самом деле, некоторые виды животных дружат друг с другом, и поэтому два животных из таких видов, если они занимают соседние места в очереди, могут поменяться местами.
У Вас есть список тех пар видов животных, которые могут согласиться поменяться местами, находясь на соседних позициях в строке: этот список содержит L пар. Вам вручили список регистрации, который ведет первый охранник. В зависимости от того, какие животные решили поменяться местами, может быть возможно несколько контрольных списков. Какой из всех возможных списков идет первым в алфавитном порядке?
Входные данные
Состоит из следующих строк:
Строка 1 содержит три целых числа через пробел S (1 ≤ S ≤ 200), L (0 ≤ L ≤ 10000) и n (1 ≤ n ≤ 100000). S - количество видов животных, L - количество пар видов, которые дружат друг с другом, а n - количество животных, вышедших в очередь на ожидание.
Строка i + 2, для 0 ≤ i < S, содержит название одного из представленных видов: это название состоит из одного слова с прописными буквами между "A" и "Z" и содержит от 1 до 20 букв.
Строка i + S + 2, для 0 ≤ i < L, содержит два названия видов, разделенных пробелами a и b означающих что a и b дружат друг с другом.
Строка S + L + 2 представляет собой список входа и содержит n названий видов, разделенных пробелами: для всех 1 ≤ k ≤ n, k - ое слово - это название вида животного в k - ой позиции.
Выходные данные
Вывести в одной строке n слов w[0]
, ..., w[n-1]
, разделенных пробелами: список w[0]
, ..., w[n-1]
среди всех возможных контрольных списков должен быть первым в алфавитном порядке.
Пример
3 2 6 ANTILOPE CAT ANT CAT ANTILOPE ANTILOPE ANT ANT CAT CAT ANTILOPE CAT ANT
ANT ANTILOPE CAT CAT CAT ANT