P13986 [PO Final 2023] 降重 / Synonyms

1s, 1G, synonymer

有时把文字从网络百科复制到文章里，会被查重程序判定为抄袭。为避免这种情况，需要先用自己的话改写文本，使其不被程序标记。方法很多，其中一种是先把文本翻译成另一种语言，再翻译回来。如果运气不好，即便这样，文本仍可能与原文过于相似。 你可以通过确保：若存在其他可能性，则一个词永远不会被翻译回同一个词，来规避这个问题。形式化地，设有一个包含 $N$ 个单词对 $(a, b)$ 的词典，其中 $a$ 是瑞典语的单词，$b$ 是另一种语言的单词。若存在某个单词 $z$，使得词典中同时存在 $(x, z)$ 与 $(y, z)$ 这两对，则某个单词 $x$ 可以被改写为单词 $y$。 给定一段文本，请通过「先翻译到另一种语言再翻译回来」的方式，尽可能多地将其中的单词替换为同义词。

第一行给出整数 $N$（$1 \le N \le 5000$），表示词典中的单词对数量。 接下来的 $N$ 行中，每行包含一对单词，先给出瑞典语单词，再给出另一种语言中的单词。同一个词不会同时出现在两种语言中，且完全相同的单词对不会重复出现。 随后给出一个整数 $M$（$1 \le M \le 1000$），表示文本中的单词数。下一行包含 $M$ 个单词，即需要你改写的文本。保证这些单词都至少作为瑞典语单词在词典中出现过一次。 所有单词的长度在 $1$ 到 $20$ 之间，且只包含字母表 $\texttt{a}\sim \texttt{z}$ 的字母。不保证这些单词一定是真实存在的自然语言单词。

在一行中输出 $M$ 个单词，即按题述过程将尽可能多的单词替换为同义词后的文本。如果某个词有多个可选同义词，你可以任选其一，但不得与原词相同。

### 样例 $1$ 解释 单词「skum」有 2 个译法，分别是「foam」和「shady」 。这些词再翻译回瑞典语时，可以得到两个不同的词：「skum」和「fradga」。为了避免把该词翻译回 「skum」，你必须选择「fradga」。 然而，对于第二个词，只有 1 个可用的翻译，因此只能翻回原词。 ### 子任务 **本题采用捆绑测试。** | 子任务编号 | 分值 | 限制 | |:-:|:-:|-------------| | $1$ | $56$ | 另一种语言中的每个词都至少有 2 个瑞典语翻译。 | | $2$ | $44$ | 无其他限制。 |