小Z的笔记

题目背景

小Z由于写情书浪费了太多时间,导致他外语课都没有好好听。为什么是外语课而不是英语课?因为小Z也不知道这门课学的是什么语言。

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

4
noip
2
ip
mo

输出样例 #1

1

说明

【数据规模】 对于10%的数据,M=0; 对于另外30%的数据,N<=1000; 对于100%的数据,N<=100000,M<=400。