← 返回题目列表

Codeforces · 653/B

B. 承受和压缩

中文机器翻译题面 查看原题

Limak 是一只小北极熊。北极熊讨厌长绳子,因此喜欢压缩它们。您还应该知道,利马克太年轻了,他只知道英文字母表的前六个字母:“a”、“b”、“c”、“d”、“e”和“f”。

给您一组 q 种可能的操作。 Limak 可以按任何顺序执行它们,任何操作可以应用任意次。第 i 个操作由长度为 2 的字符串 ai 和长度为 1 的字符串 bi 描述。 q 个可能的操作中没有两个具有相同的字符串 ai。

当 Limak 有一个字符串 s 时,如果 s 的前两个字母与两个字母的字符串 ai 匹配,他可以对 s 执行第 i 次操作。执行第 i 个操作会删除 s 的前两个字母并在其中插入字符串 bi。请参阅注释部分以获取进一步说明。

您可能会注意到,执行操作会将字符串 s 的长度精确减少 1。此外,对于某些操作集,可能存在无法进一步压缩的字符串,因为前两个字母与任何 ai 都不匹配。

Limak 希望从一个长度为 n 的字符串开始,执行 n - 1 次操作,最终得到一个单字母字符串“a”。他可以通过多少种方式选择起始字符串来得到“a”?请记住,利马克只能使用他认识的字母。

输入

第一行包含两个整数 n 和 q (2 ≤ n ≤ 6, 1 ≤ q ≤ 36) - 初始字符串的长度和可用操作的数量。

接下来的 q 行描述了可能的操作。其中第 i 个包含两个字符串 ai 和 bi (|ai| = 2, |bi| = 1)。保证 i ≠ j 时 ai ≠ aj,并且所有 ai 和 bi 仅包含前 6 个小写英文字母。

输出

打印长度为 n 的字符串数量,Limak 仅通过应用输入中给出的操作即可将其转换为字符串“a”。

示例

输入 #1

3 5
ab a
cc c
ca a
ee c
ff d

输出 #1

4

输入 #2

2 8
af e
dc d
cc f
bc b
da b
eb a
bb b
ff c

输出 #2

1

输入 #3

6 2
bb a
ba a

输出 #3

0

注意

在第一个示例中,我们计算长度为 3 的初始字符串,从中 Limak 可以获得所需的字符串“a”。有 4 个这样的字符串:“abb”、“cab”、“cca”、“eea”。第一个 Limak 可以使用操作 1 进行两次压缩(将“ab”更改为单个“a”)。第一个操作会将“abb”更改为“ab”,第二个操作会将“ab”更改为“a”。

其他三个字符串可以压缩如下:

- “出租车”$$\rightarrow$$“ab”$$\rightarrow$$“a”
- “cca”$$\rightarrow$$“ca”$$\rightarrow$$“a”
- “eea”$$\rightarrow$$“ca”$$\rightarrow$$“a”

在第二个示例中,唯一正确的初始字符串是“eb”,因为它可以立即压缩为“a”。