说明

动物们在一个隔离区排队，等待进入一个禁止狩猎的区域，那里它们将过上更轻松的生活。

进入隔离区时，动物必须向一名守卫登记。守卫记下动物的物种，然后该动物被允许加入队伍的末尾，即最后一位。在队伍的另一端，动物必须登记离开：当队伍中第一位的动物最终被允许进入禁止狩猎区时，另一名守卫记下该动物的物种。因此，每名守卫都维护着一个动物物种列表，按照动物登记进入或离开的时间顺序记录。总共有 $N$ 只动物，代表 $S$ 个物种，进行了登记进入（因此也登记离开）。

然而，动物进入等待队伍和离开的顺序可能不同。实际上，某些动物物种彼此是朋友，因此如果两个属于此类物种的动物在队伍中占据相邻位置，它们可能会同意交换位置。

你有一个这样的动物物种对的列表，这些物种对在队伍中相邻时可能会同意交换位置：该列表包含 $L$ 对物种。你拿到了第一名守卫维护的登记进入列表。根据哪些动物决定交换位置，可能有多个登记离开列表。在所有可能的列表中，按字典序排列，哪一个是最靠前的？

输入格式

输入包含以下行：

• 第 1 行包含三个空格分隔的整数 $S$、$L$ 和 $N$。$S$ 是动物物种的数量，$L$ 是彼此是朋友的物种对的数量，$N$ 是进入等待队伍的动物数量。
• 对于 $0 \leq i < S$，第 $i+2$ 行包含一个所代表物种的名称：该名称由单个单词组成，仅包含大写字母 “A” 到 “Z”，且长度在 1 到 20 个字母之间。
• 对于 $0 \leq i < L$，第 $i+S+2$ 行包含两个空格分隔的物种名称 $A$ 和 $B$，表示 $A$ 和 $B$ 彼此是朋友。
• 第 $S + L + 2$ 行代表登记进入列表，包含 $N$ 个空格分隔的物种名称：对于所有 $1 \leq k \leq N$，第 $k$ 个单词是第 $k$ 个进入队伍的动物的物种名称。

输出格式

输出应包含一行，包含 $N$ 个单词 $w_0, \ldots, w_{N-1}$，以空格分隔：列表 $w_0, \ldots, 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

提示

样例解释

登记离开时可能的六种顺序，按字典序（递增）排列如下：

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

数据范围

• $1 \leq S \leq 200$；
• $0 \leq L \leq 10\,000$；
• $1 \leq N \leq 100\,000$。

翻译由 DeepSeek 完成