题目描述

任何一种生物的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串的最短长度。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论