BZPRO
#4156. [Wf2009]Suffix-Replacement Grammars
内存限制：64 MiB
时间限制：20 Sec
提交
提交记录
讨论
题目描述
某种语言，它由大小写英文字母拼出的单词组成，但它还存在一种后缀转换的系统。
后缀转换系统一共有N个元件，这些元件是已知的，一个元件包括两个等长的字符串(Sa,Sb)。
如果一个单词的后缀为Sa,这个元件就可以将这个单词的后缀Sa变为Sb,从而形成一个新的单词。
现在你手上有两个等长的字符串S,T,你需要知道至少经过多少次后缀转换可以变字符串S变为T.
输入格式
每个测试数据含多组数据
第一行包含两个字符串S，T，以及一个整数N，意义如上所述
第二行至第N+1行每行包括两个字符串Sa,Sb,表示一个元件
整个测试以'.'结束。
输出格式
对于一组数据，输出这组的数据编号及最小步数，如果无法转换，就输出'No Solution'
样例
样例输入
AA BB 4
A B
AB BA
AA CC
CC BB
A B 3
A C
B C
c B
.
样例输出
Case 1: 2
Case 2: No solution
数据范围与提示
字符串长度<=20,N<=100.保证输入字符只有英文字母
BZPRO