Обмін місцями#9708

Обмін місцями

2 секунди

128 мегабайтів

Складна

Тварини стоять у черзі в карантинній зоні, перш ніж потрапити в зону, вільну від полювання, де їм буде легше жити.

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

Однак тварини можуть заходити в чергу очікування і виходити з неї в іншому порядку. Насправді, деякі види тварин дружать один з одним, і тому дві тварини з таких видів, якщо вони займають сусідні місця в черзі, можуть помінятися місцями.

У вас є список тих пар видів тварин, які можуть погодитися помінятися місцями, перебуваючи на сусідніх позиціях у черзі: цей список містить $L$ пар. Вам вручили список реєстрації, який веде перший охоронець. Залежно від того, які тварини вирішили помінятися місцями, може бути кілька контрольних списків. Який з усіх можливих списків йде першим в алфавітному порядку?

Вхідні дані

Складається з наступних рядків:

Рядок $1$ містить три цілі числа через пробіл $S$ ( $1 \leq S \leq 200$ 1 \leq S \leq 200), $L$ ( $0 \leq L \leq 10000$ 0 \leq L \leq 10000) і $n$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100000). $S$ - кількість видів тварин, $L$ - кількість пар видів, які дружать один з одним, а $n$ - кількість тварин, що вийшли в чергу на очікування.
Рядок $i + 2$ i + 2, для $0 \leq i < S$ 0 \leq i < S, містить назву одного з представлених видів: ця назва складається з одного слова з прописними літерами між "A" і "Z" і містить від $1$ до $20$ літер.
Рядок $i + S + 2$ i + S + 2, для $0 \leq i < L$ 0 \leq i < L, містить дві назви видів, розділених пробілами $a$ і $b$ , що означає, що $a$ і $b$ дружать один з одним.
Рядок $S + L + 2$ S + L + 2 представляє собою список входу і містить $n$ назв видів, розділених пробілами: для всіх $1 \leq k \leq n$ 1 \leq k \leq n, $k$ -те слово - це назва виду тварини на $k$ -й позиції.

Вихідні дані

Вивести в одному рядку $n$ слів $w_{0}, \dots, w_{n - 1}$ w_0, \ldots, w_{n-1}, розділених пробілами: список $w_{0}, \dots, w_{n - 1}$ w_0, \ldots, w_{n-1} серед усіх можливих контрольних списків повинен бути першим в алфавітному порядку.

Приклади

Приклад 1