#P1957. Beehives

Beehives

题目描述:

太郎和花子是生物专业的学生,他们长期致力于对蜂巢的观察研究。他们的兴趣在于发现某一特定野生蜂种的蜂王所产的卵的分布模式。据说蜂王会在短时间内产下一批卵。太郎和花子从未亲眼见过蜂王产卵的过程。因此,每次他们发现蜂巢时,看到的都是刚刚产在蜂巢巢室里的卵。

太郎和花子有一个记录卵的分布布局的惯例:他们假定蜂王产卵时,会沿着一条没有回路(循环)的路径,从一个巢室移动到相邻的巢室。他们会记录下有卵的巢室所构成的路径。从生物学角度来说,并不能保证在每种情况下都能找到这样一条无回路的路径。然而,在他们的观察过程中,从未出现过找不到这种无回路路径的情况。

从一个巢室移动到相邻的巢室只有六种可能的方向,他们约定按照逆时针方向用字母 aabbccddeeff 来表示这六种移动方向,如图 2 所示。因此,图 1 中的卵的分布布局可以记录为 faafdfaafd

太郎和花子各自独立地在森林中对蜂巢进行了调查。他们每个人都有自己接近蜂巢的方法,以保护自己免受可能的蜜蜂攻击。

他们被要求在一个会议上共同汇报工作,并且要分享各自的观察记录以起草一份联合报告。就在这个时候,他们发现了他们惯例中的一个严重问题。他们从未讨论过从绝对意义上来说,哪个方向应该被认定为 aa,因此图 2 可能会被看作是,比如说,图 3 或者图 4 的样子。根据观察蜂巢的方向以及所假定的路径,图 1 中所示的布局可能会被记录得有所不同:如果结合图 3 和图 5,可能会记录为 bcbdbbcbdb;如果结合图 4 和图 6,则可能会记录为 bccacbccac

只能从蜂巢的正面观察蜂巢,而绝不能从背面观察,所以一个卵的分布布局不会与它的镜像相混淆。

由于他们可能独立地观察到了相同的卵的分布布局,所以他们必须在自己的观察记录中找出重复的记录(当然,他们并没有记录每次观察的准确地点和准确时间)。你的任务是编写一个程序来帮助太郎和花子,检查两条观察记录是否来自相同的卵的分布布局。

输入:

输入的第一行包含后续记录对的数量。该数量最多由三位数字表示。

每一对记录由两行卵的分布布局记录和一行包含一个连字符 - 的行组成。每行卵的分布布局记录由字母 aabbccddeeff 组成的一个序列构成。请注意,如果由于某种原因蜂王只产了一个卵,那么卵的分布布局记录可能是一个空序列。你可以相信太郎和花子,输入中的任何路径都不会让你访问任何一个巢室超过一次。输入中的任何一行除了上述所描述的字符外不包含其他字符,并且每行最多包含一百个字符。

输出:

对于每一对记录,输出一行内容,内容为 truetrue 或者 falsefalse:如果两条记录表示的是相同的卵分布布局,则输出 truetrue;否则,输出 falsefalse。该行不应包含其他任何字符。

输入数据1

5
faafd
bcbdb
--
bcbdb
bccac
--
faafd
aafdd
--
aaafddd
aaaeff
--
aaedd
aafdd
--

输出数据1

true
true
false
false
false

来源:

日本2001