问题 AL: Limak and Compressing

Limak讨厌长字符串，因此他们喜欢把它们压缩。另外还因为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的前2个字母压缩成1个字母。 你可能会注意到，执行一个操作会将字符串s的长度恰好减少1。此外，对于某些操作集，可能存在无法进一步压缩的字符串，因为前两个字母与任何ai都不匹配。

Limak希望从长度为n的字符串开始，并执行n - 1次运算，最终得到一个单字母字符串a。他可以通过几种方式选择起始字符串来获得a？请记住，Limak只能使用他知道的字母。

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

4