P2187 小Z的笔记

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

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

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

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

【数据规模】 对于 $10\%$ 的数据，$M=0$。 对于另外 $30\%$ 的数据，$N \le 1000$。 对于 $100\%$ 的数据，$N \le 10^5$，$M \le 400$。