题目描述

某种语言，它由大小写英文字母拼出的单词组成，但它还存在一种后缀转换的系统。 后缀转换系统一共有 $n$ 个元件，这些元件是已知的，一个元件包括两个等长的字符串 $(S_a,S_b)$。

如果一个单词的后缀为 $S_a$，这个元件就可以将这个单词的后缀 $S_a$ 变为 $S_b$，从而形成一个新的单词。 现在你手上有两个等长的字符串 $S,T$，你需要知道至少经过多少次后缀转换可以变字符串 $S$ 变为 $T$。

输入格式

每个测试数据含多组数据

第一行包含两个字符串 $S,T$，以及一个整数 $n$，意义如上所述。

第二行至第 $n+1$ 行每行包括两个字符串 $S_a,S_b$，表示一个元件。

整个测试以 . 结束。

输出格式

对于一组数据，输出这组的数据编号及最小步数，如果无法转换，就输出 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

数据规模与约定

对于 $100\%$ 的数据，$|S|\leq 20$，$1\leq n\leq 100$。