题目描述

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$，字符集为大小写字母。