2017.8.17 ACM 训练赛

罗塞塔石碑（Rosetta Stone，又译为罗塞达碑），是一块制作于公元前 196 年的花岗闪长岩石碑，原本只是一块刻有古埃及法老托勒密五世（Ptolemy V）诏书的石碑，但由于这块石碑同时刻有同一段内容的三种不同语言版本，使得近代的考古学家得以有机会对照各语言版本的内容后，解读出已经失传千余年的埃及象形文之意义与结构，而成为今日研究古埃及历史的重要里程碑。罗塞塔石碑最早是在 1799 年时由法军上尉皮埃尔·弗朗索瓦·札维耶·布夏贺（Pierre-François Xavier Bouchard）在一个埃及港湾城市罗塞塔（Rosetta，今日亦称为拉希德）发现，但在英法两国的战争之中辗转到英国手中，自 1802 年起保存于大英博物馆中并公开展示。

但你可能不知道的是，解读这上面的文字却费尽了历代考古学者的心血。在公元 4 世纪结束后不久，尼罗河文明式微、不再使用的埃及象形文之读法与写法彻底失传，虽然之后有许多考古与历史学家极尽所能，却一直解读不了这些神秘文字的结构与用法。直到时隔 1400 年之后罗塞塔石碑出土，它独特的三语对照写法，意外成为解码的关键，因为三种语言中的古希腊文是近代人类可以阅读的，利用这关键来比对分析碑上其他两种语言的内容，就可以了解这些失传语言的文字与文法结构。

在许多尝试解读罗塞塔石碑的学者中，19 世纪初期的英国物理学家托马斯·杨（Thomas Young）是第一个证明碑文中曾多次提及“托勒密”这人名的发音者。至于法国学者尚-佛罕索瓦·商博良（Jean-François Champollion）则是第一个理解到，一直被认为是用形表义的埃及象形文，原来也是具有表音作用的，这重大发现之后成为解读所有埃及象形文的关键线索。也正是因为这缘故，罗塞塔石碑会被称为了解古埃及语言与文化的关键基础。

解读石碑的关键在于：找到语言与语言之间的匹配规则，然后尝试应用这些匹配规则，来解读文字。这些匹配规则可能需要被反复调整，以至于最终，我们所得到的文字能变成完整的一句话。今天，通过计算机，我们可以重现这个过程。为了避免处理难以输入的埃及文字，我们使用英文小写字母来代替。

给出 $m$ 条匹配规则，每条匹配规则都表示一个字母可以被译成另一个字母。一个字母可能适用于多条规则，也可能不适用于任何规则。你可以运用多次。例如，如果 a 可以变成 e，e 可以变成 i，那么，a 也可以译为 i。

再有 $n$ 对单词，请输出每对单词中的第一个能否译为第二个。在翻译过程中，你不能对字母进行增删。