问题 B: 熊压缩

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:84 通过:57

题目描述

     Limak 是一只小北极熊。北极熊讨厌长绳。您还应该知道,Limak 非常年轻,他只知道英文字母表的前六个字母:“a”、“b”、“c”、“d”、“e”和“f”。
Limak 
获得 q种 可能的操作。Limak可以按任何顺序执行它们,任何操作可以应用任意次数。第 i 个操作可以把一个长度为2的字符串s压缩成为一个字符串为1的字符串bq 种操作中没有两个具有相同的操作.
    现在Limak 有一个字符串 ss ,如果 ss 的前两个字母
与第 i 个操作的两个字母的字符串s匹配,他可以对 ss 执行第 i 个操作. 执行第 i 个操作会删除 ss 的前两个字母并插入一个字符串.有关进一步说明,请参阅注释部分。
执行一次操作会将字符串 ss 的长度正好减少 1。此外,对于某些操作集,因为不匹配可能存在无法进一步压缩字符串
.
Limak 希望从长度为 n 的字符串开始并执行 n-1 操作以最终获得一个字母字符串“a”。他可以通过多少种方式选择起始字符串才能得到“a”?请记住,利马克只能使用他知道的字母。

输入格式

输入第一行输入两个整数n(2<=n<=6)和q(1<=q<=36),代表压缩前字符串的长度以及压缩方式的种类数

接下来q行,每行两个字符串,长度分别为2和1,只有abcdef共6种字母,代表前面的字符串可以压缩成后面的字符串


输出格式

输出长度为n的符合条件的字符串种类数

例子
输入
3 5
ab a
cc c
ca a
ee c
ff d
输出
4
输入
2 8
af e
dc d
cc f
bc b
da b
eb a
bb b
ff c
输出
1
输入
6 2
bb a
ba a
输出
0
注意

在第一个样例中,符合条件的长度为3的字符串有4中,“abb”,“cab”,“cca”,“eea”

“abb” -----> “ab” -----> “a”

“cab”-----> “ab” —> “a”

“cca”----->“ca” ----->“a”

“eea” ----->“ca” -----> “a”

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

输入样例 复制

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

输出样例 复制

4