题目描述

JOHNKRAM 收到了一个字符串 $S$ ，但他不喜欢这个串，他决定把它变成 $T$ 。

JOHNKRAM 最近学习了一些后缀数据结构，他相信通过替换后缀可以实现一切操作。他有 $m$ 种替换方式，每种替换方式包含两个等长的字符串 $u$ 和 $v$ ，如果当前 $u$ 是 $S$ 的后缀，则可以将 $S$ 的后缀 $u$ 替换成 $v$ 。

现在 JOHNKRAM 希望你能帮他计算出，最少需要替换多少次才能将 $S$ 变成 $T$ 。

输入格式

一个测试点包含多组数据。
每组数据第一行包含两个字符串 $S$ 和 $T$ 以及一个整数 $n$ ，意思如题所示。
接下来 $n$ 行每行两个字符串 $u$ 和 $v$ ，表示一种替换方式。
输入文件以一个 . 结束。

对于每一组数据，输出该组数据编号以及最小步数，如果无解输出 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

对于 $30\%$ 的数据，字符串长度 $\leq 1$ ；
对于 $45\%$ 的数据，字符串长度 $\leq 5$ ；
对于 $100\%$ 的数据，字符串长度 $\leq 20$ ， $1 \leq n \leq 100$ ，字符集为大小写字母。