시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

Dylan is a corrupt politician trying to steal an election. He has already used a mind-control technique to enslave some set U of government representatives. However, the representatives who will be choosing the winner of the election is a different set V . Dylan is hoping that he does not need to use his mind-control device again, so he is wondering which representatives from V can be convinced to vote for him by representatives from U.

Luckily, representatives can be persuasive people. You have a list of pairs (A, B) of represenatives, which indicate that A can convice B to vote for Dylan. These can work in chains; for instance, if Dylan has mind-controlled A, A can convince B, and B can convince C, then A can effectively convince C as well.

입력

The first line contains a single integer T (1 ≤ T ≤ 10), the number of test cases. The first line of each test case contains three space-separated integers, u, v, and m (1 ≤ u, v, m ≤ 10,000). The second line contains a space-separated list of the u names of representatives in U. The third line contains a space-separated list of the v names of representatives from V . Each of the next m lines contains a pair of the form A B, where A and B are names of two representatives such that A can convince B to vote for Dylan. Names are strings of length between 1 and 10 that only consists of lowercase letters (a to z).

출력

For each test case, output a space-separated list of the names of representatives from T who can be convinced to vote for Dylan via a chain from S, in alphabetical order.

예제 입력 1

2
1 1 1
alice
bob
alice bob
5 5 5
adam bob joe jill peter
rob peter nicole eve saul
harry ron
eve adam
joe chris
jill jack
jack saul

예제 출력 1

bob
peter saul

힌트

In the second test case, Jill can convince Saul via Jack, and Peter was already mind-controlled.