P13074 [GCJ 2020 Finals] Replace All

**Banana Rocks Inc** 正在研发一项革命性技术，用于执行常见的编辑操作“替换所有字符”。他们的实现会将给定文本中某个字符的所有出现替换为另一个字符。（如果该字符未出现在文本中，则操作会执行但无实际效果。） 例如，如果初始文本为 `CODEJAMWORLDFINALS`，执行将 A 替换为 O 的操作后，新文本为 `CODEJOMWORLDFINOLS`。若在该结果上再执行将 O 替换为 Y 的操作，最终文本为 `CYDEJYMWYRLDFINYLS`。 遗憾的是，该实现尚未完成，因此只能执行特定列表中的 $\mathbf{N}$ 对字符的替换。此外，即使实现了将某个字符 $c_1$ 替换为另一个字符 $c_2$ 的操作，反向将 $c_2$ 替换为 $c_1$ 的操作可能实现也可能未实现。 你需要尝试所有已实现的替换操作。给定一个初始字符串 $\mathbf{S}$ 作为初始文本，你可以按任意顺序执行任意次数的替换操作：第一次替换作用于 $\mathbf{S}$，第 $(i+1)$ 次替换作用于第 $i$ 次替换后的结果。唯一的要求是在此过程中每个已实现的替换操作至少执行一次。每个替换操作的执行次数无上限。 允许的字符包括十进制数字、大小写英文字母。在此问题中，同一字母的大小写被视为不同字符。 在执行完最后一次替换操作后，最终文本中可能出现的**最大不同字符数**是多少？

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例包含两行：第一行是一个字符串 $\mathbf{S}$ 和一个整数 $\mathbf{N}$，分别表示初始文本和已实现的替换操作数量。第二行包含 $\mathbf{N}$ 个两字符的字符串 $\mathbf{R}_1, \mathbf{R}_2, \ldots, \mathbf{R}_\mathbf{N}$，表示已实现的替换操作。$\mathbf{A}_i$ 和 $\mathbf{B}_i$ 分别是 $\mathbf{R}_i$ 的第一个和第二个字符。第 $i$ 个替换操作表示将所有 $\mathbf{A}_i$ 替换为 $\mathbf{B}_i$。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是在以某种顺序对 $\mathbf{S}$ 执行所有已实现替换操作（每个至少一次）后，最终文本中可能出现的最大不同字符数。

**样例解释** 样例测试集 1 符合测试集 1 的限制。另一个不符合这些限制的样例可能出现在测试集 2 中。 样例 #1 对应题目描述中的例子。注意，若按描述中的顺序执行替换操作，最终文本中有 13 个不同字符；但若以相反顺序各执行一次，则可得到 `CYDEJOMWYRLDFINOLS`，其中包含 14 个不同字符。 在样例 #2 中，按从左到右的顺序各执行一次替换操作，最终文本中可得到 2 个不同字符。 在样例 #3 中，所有替换操作均不影响文本，因此执行顺序无关紧要。最终文本始终为原始的两个字母。注意，替换操作可能包含初始文本中未出现的字符，且初始文本也可能包含替换操作中未出现的字符。 在样例 #4 中，请记住大写 $\mathbf{B}$ 与小写 $\mathbf{b}$ 是不同的字符。 在此附加样例中，一种可能的替换顺序为 `X3 2X X2 2X 12 31`。该过程从 $\mathbf{S}$ 开始依次生成以下字符串：`1234 1234 1X34 1234 1X34 2X34 2X14`。 **限制条件** - $1 \leq \mathbf{T} \leq 100$。 - 对于所有 $i$，$2 \leq \text{初始文本 } \mathbf{S} \text{ 的长度} \leq 1000$。 - $\mathbf{S}$ 的每个字符为大写或小写英文字母或十进制数字。 - 对于所有 $i$，$\mathbf{A}_i$ 为大写或小写英文字母或十进制数字。 - 对于所有 $i$，$\mathbf{B}_i$ 为大写或小写英文字母或十进制数字。 - 对于所有 $i$，$\mathbf{A}_i \neq \mathbf{B}_i$。 - 对于所有 $i \neq j$，$(\mathbf{A}_i, \mathbf{B}_i) \neq (\mathbf{A}_j, \mathbf{B}_j)$（每个替换操作唯一）。 **测试集 1（15 分，可见判定）** - $2 \leq \mathbf{N} \leq 62$。 - 对于所有 $i \neq j$，$\mathbf{B}_i \neq \mathbf{B}_j$。 **测试集 2（27 分，隐藏判定）** - $2 \leq \mathbf{N} \leq 62 \times 61$。 翻译由 DeepSeek V3 完成