CF154A Hometask

Sergey 正在学习 $N$ 语。他每节课都会收到一项家庭作业。这次的任务是将一句话翻译成 $N$ 语。$N$ 语的句子可以被表示为只包含小写拉丁字母、没有空格或标点符号的字符串。 Sergey 完全忘记了这项作业，直到下节课前半小时他才匆忙写了一些内容。但随后他回想起在上节课中学习过 $N$ 语的语法规则。拼写规则规定，$N$ 语中包含一些“禁止”字母对：这样的字母不能出现在句子中相邻的位置。此外，字母的顺序无关紧要（例如，如果禁止字母对为“ab”，那么出现子串“ab”或“ba”都是被禁止的）。同时，每个禁止对都由不同的字母组成，并且每个字母最多只会出现在一个禁止对中。 现在 Sergey 想要修改他的句子，使其不包含任何相邻的“禁止”字母对。然而，他时间紧迫，因此他决定仅仅划掉句子中的某些字母。请你计算，最少需要删除多少个字母，才能使字符串相邻的字母之间不含有任何“禁止”对。删除某个字母后，该字母的左右字符（如果存在）会相邻。例如，从字符串 "aba" 删除第一个字母后得到 "ba"，删除第二个字母后得到 "aa"。

第一行包含一个非空字符串 $s$，由小写拉丁字母组成 —— 这是 Sergey 写下的 $N$ 语言初始句子。字符串 $s$ 的长度不超过 $10^{5}$。 第二行包含一个整数 $k$（$0 \leq k \leq 13$）—— 被禁止的字母对的数量。 接下来的 $k$ 行，每行包含恰好两个不同的小写拉丁字母，表示一个禁止对，没有分隔符。保证每个字母最多只出现在一个禁止对中。

输出一个整数——为使字符串中不含任何相邻的“禁止”字母对，最少需要删除多少个字母。请注意，总是存在解法，因为可以全部删除所有字母。

在第一个样例中，应该删除两个字母 b。 在第二个样例中，应该删除第二个或第三个字母。第二个限制对解法没有影响。 由 ChatGPT 5 翻译