← 返回题目列表

Codeforces · 154/A

A. 家庭任务

中文机器翻译题面 查看原题

Sergey 参加 N-ish 语言课程。每节课他都会收到一个家庭作业。这次的任务是将一些句子翻译成 N-ish 语言。 N-ish 语言的句子可以表示为由小写拉丁字母组成的字符串,不带空格或标点符号。

谢尔盖完全忘记了这项任务,直到下节课前半小时,他匆匆写下了一些东西。但他随即想起上一堂课他学了N-ish的语法。拼写规则规定,N-ish 包含一些“禁止”的字母对:这些字母永远不能出现在彼此相邻的句子中。此外,字母的顺序并不重要(例如,如果禁止一对字母“ab”,则也禁止出现任何子字符串“ab”和“ba”)。此外,每一对都有不同的字母,并且每个字母出现在不超过一对禁用的字母中。

现在谢尔盖想要纠正他的句子,使其不包含任何彼此相邻的“禁止”字母对。然而,他的时间不多了,所以他决定简单地从句子中划掉一些字母。他最少需要划掉多少个字母?当一个字母被划掉时,它被“删除”,以便其左侧和右侧的字母(如果存在)成为相邻的。例如,如果我们划掉字符串“aba”中的第一个字母,我们会得到字符串“ba”,如果我们划掉第二个字母,我们会得到“aa”。

输入

第一行包含一个非空字符串 s,由小写拉丁字母组成 - 这是 N-ish 的初始句子,由 Sergey 编写。字符串s的长度不超过105。

下一行包含整数 k (0 ≤ k ≤ 13) — 禁止的字母对的数量。

接下来的 k 行包含禁止字母对的描述。每行包含两个不同的小写拉丁字母,不带分隔符,表示禁止对。保证每个字母不超过一对。

输出

打印单个数字 - 需要删除的字母的最小数量,以获得没有任何禁止的相邻字母对的字符串。请注意,答案始终存在,因为总是可以删除所有字母。

示例

输入 #1

ababa
1
ab

输出 #1

2

输入 #2

codeforces
2
do
cs

输出 #2

1

注意

在第一个示例中,您应该删除两个字母 b。

在第二个示例中,您应该删除第二个或第三个字母。第二个限制不影响解决方案。