자리 바꾸기

동물들이 사냥이 없는 지역에 들어가 더 편한 삶을 누리기 전까지, 격리 구역의 줄에서 기다리고 있다.

격리 구역에 들어갈 때 각 동물은 검사원에게 등록한다. 검사원이 동물의 종을 기록하면, 동물은 줄의 맨 끝, 마지막 자리에 선다. 줄의 반대편 끝에서는 동물이 퇴장한다. 맨 앞의 동물이 마침내 사냥이 없는 지역에 들어가도 되면, 다른 검사원이 그 동물의 종을 기록한다. 따라서 각 검사원은 등록 또는 퇴장이 일어난 시간순으로 종의 목록을 보관한다. 총 N마리의 동물이 S개 종에 속하며, 등록하고 그에 따라 퇴장한다.

그러나 동물들은 서로 다른 순서로 줄에 들어가고 줄에서 나올 수 있다. 일부 종은 서로 친구여서, 줄에서 바로 옆에 선 그런 종의 두 동물은 자리를 바꾸기로 합의할 수 있다.

옆자리에 섰을 때 자리를 바꾸기로 합의할 수 있는 종의 쌍 L개가 주어진다. 첫 번째 검사원이 보관한 등록 목록이 주어진다. 어떤 동물들이 자리를 바꾸기로 하느냐에 따라 여러 퇴장 목록이 가능하다. 가능한 모든 목록 중 사전순으로 가장 앞에 오는 것은 무엇인가?

입력은 다음 줄로 구성된다.

• 1번째 줄에는 공백으로 구분된 정수 S, L, N이 있다. S는 동물 종의 수, L은 서로 친구인 종 쌍의 수, N은 줄에 들어간 동물의 수다.
• 이어지는 S개 줄에는 각각 종의 이름이 하나씩 있다. 이름은 A부터 Z까지의 대문자로 이루어진 한 단어이며, 길이는 1자 이상 20자 이하다.
• 이어지는 L개 줄에는 서로 친구인 두 종의 이름 A와 B가 공백으로 구분되어 있다.
• 마지막 줄에는 공백으로 구분된 N개의 단어가 있다. k번째 단어는 k번째 자리에 들어간 동물의 종이다.

N개의 단어 $w_0, \ldots, w_{N-1}$을 공백으로 구분해 한 줄에 출력한다. 가능한 모든 퇴장 목록 중 사전순으로 가장 앞에 오는 목록이어야 한다.

• $1 \le S \le 200$
• $0 \le L \le 10\,000$
• $1 \le N \le 100\,000$

사전순으로 정렬한 퇴장 순서의 여섯 가지 가능성은 다음과 같다.

1. ANT ANTILOPE CAT CAT CAT ANT
2. ANT CAT ANTILOPE CAT CAT ANT
3. ANT CAT CAT ANTILOPE CAT ANT
4. ANT CAT CAT CAT ANT ANTILOPE
5. ANT CAT CAT CAT ANTILOPE ANT
6. ANTILOPE ANT CAT CAT CAT ANT