2529: 笔记

小 Y 由于破解某人的情书浪费了太多时间,导致他外语课都没有好好听。为什么是外语
课?不是英语课?因为小 Y 也不知道这门课学的是什么语言。由于没有好好听课,小 Y 的笔
记全都记的杂乱无章,出现了好多错误的地方。小 Y 的笔记是如此的糟糕,以至于他只记了
一句例句,而且自己还不知道是什么意思......然后在老师讲语法的时候,小 Y 又零星的记了
几个字母对,老师说:这几个字母对是绝对不能相邻的,而且相邻是不关心字母的顺序的,
比如老师说,’ab’相邻不能,那么相同的,’ba’也相邻不能。
现在小 Y 到家了,打开了上课的笔记,然后他发现笔记有很多自相矛盾的地方:为什么
下面的不能相邻的字母对会出现在上面的例句里面呢?纠结再三,小 Y 觉得下面的东西相对
比较简单,所以记错的概率比较小......他决定在上面的例句里面擦掉几个字母,使得句子变
得合法。
但是小 Y 还有其他作业要做呢,来不及整理笔记了,就把这个艰巨的任务留给了大家,
请问大家,小 Y 最少要擦掉几个字母,才能使得上面的例句合法?

第一行:一个整数 N。
第二行:一个长度为 N 的字符串,只包含小写字母,代表小 Y 记下的例句。
第三行:一个整数 M,代表不能相邻的字母对的个数。
接下来 M 行:每行两个小写字母,代表不能相邻的字母对,因为小 Y 太不认真了,所以
可能有重复。

一行一个整数:最少要擦除的字母数。

4
noip
2
ip
mo

1