单点时限: 2.0 sec
内存限制: 256 MB
罗塞塔石碑(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$ 对单词,请输出每对单词中的第一个能否译为第二个。在翻译过程中,你不能对字母进行增删。
第一行两个整数 $m,n$ $(1 \leq m \leq 500, 1 \leq n \leq 50)$。
接下来 $m$ 行匹配规则,每行两个字母用一个空格隔开 a b
,表示 a
可以被译成 b
。
接下来 $n$ 行,每行一对单词,用一个空格隔开,单词长度不超过 $50$。
规则和单词中只会出现小写字母。
如果可以输出 yes
,否则输出 no
。
9 5 c t i r k p o c r o t e t f u h w p we we can the work people it of out the
yes no no yes yes
3 3 a c b a a b aaa abc abc aaa acm bcm
yes no yes