3323. 罗塞塔石碑

单点时限: 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 可以变成 ee 可以变成 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

样例

Input
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
Output
yes
no
no
yes
yes
Input
3 3
a c
b a
a b
aaa abc
abc aaa
acm bcm
Output
yes
no
yes

54 人解决,62 人已尝试。

63 份提交通过,共有 188 份提交。

3.6 EMB 奖励。

创建: 7 年,3 月前.

修改: 7 年,3 月前.

最后提交: 9 月,3 周前.

来源: ICPC World Finals 2017

题目标签