P15190 [SWERC 2019] Swapping Places

动物们在一个隔离区排队，等待进入一个禁止狩猎的区域，那里它们将过上更轻松的生活。 进入隔离区时，动物必须向一名守卫登记。守卫记下动物的物种，然后该动物被允许加入队伍的末尾，即最后一位。在队伍的另一端，动物必须登记离开：当队伍中第一位的动物最终被允许进入禁止狩猎区时，另一名守卫记下该动物的物种。因此，每名守卫都维护着一个动物物种列表，按照动物登记进入或离开的时间顺序记录。总共有 $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}$ 必须是所有可能的登记离开列表中按字典序排列最靠前的那一个。

#### 样例解释 登记离开时可能的六种顺序，按字典序（递增）排列如下： 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 完成