任何一种生物的DNA都可以表示为一个由小写英文字母组成的非空字符串。科学家发现，所有的生物都有可能发生变异。所谓变异，就是子代的DNA串与父代的DNA串有差异。每次变异，DNA串中恰好有一个字符会变成两个任意的字符。一共有n种可能的变异。变异ai->bici表示字符ai有可能变异为两个字符bici。详细来说，就是删掉一个字符ai，之后在原来ai的位置处，插入bi，ci两个字符（注意字符bi必须在ci的前面）。每种变异都有可能发生任意多次。可以发现，每变异一次，DNA串的长度会加1。

如果有一种生物a，他的DNA串是s1，另外存在一种生物b，他的DNA串是s2。如果s2可以通过若干次变异变为s1（可以为0次），那么生物b就被叫做生物a的祖先。

现在，给定一种生物，他的DNA串是s。请找出他的一个祖先，且这个祖先的DNA串尽量短。

对于30%的数据，s的长度<=5， N <= 3；

对于100%的数据，s的长度<=50， N <= 50

第一行包含一个非空字符串s。

第二行含有一个整数n，表示所有可能的变异。

接下来n行，每行描述一种可能的变异，按照ai->bici的格式。

s，ai，bi，ci仅包含小写英文字母。

请注意：一种变异可能出现多次。

输出只有一行，一个整数，表示祖先DNA串的最短长度。