P2187 Xiao Z's Notes

Because Xiao Z wasted too much time writing love letters, he didn’t pay attention in his foreign language class. Why is it a foreign language class and not English? Because Xiao Z doesn’t even know what language this class is about.

Since he didn’t pay attention, Xiao Z’s notes are a complete mess with lots of mistakes. His notes are so bad that he only wrote down one example sentence, and he doesn’t even know what it means. Later, when the teacher explained grammar, Xiao Z jotted down a few letter pairs, and the teacher said these pairs must never be adjacent. Adjacency is order-insensitive: for example, if the teacher says "ab" cannot be adjacent, then "ba" is also forbidden. Back at home, Xiao Z opened his class notes and found many contradictions: why do the forbidden pairs appear in the example sentence above? After thinking it over, he felt the items below are relatively simpler, so they are less likely to be mistaken. He decides to erase some letters from the example sentence above to make the sentence valid. But Xiao Z still has other homework to do, so he doesn’t have time to clean up his notes. He leaves this tough task to you: what is the minimum number of letters that Xiao Z must erase to make the example sentence above valid? # Description

The first line: an integer $N$. The second line: a string of length $N$, containing only lowercase letters, representing the example sentence Xiao Z wrote down. The third line: an integer $M$, the number of forbidden adjacent letter pairs. The next $M$ lines: each line contains two lowercase letters, representing a forbidden adjacent pair. Since Xiao Z was careless, duplicates may appear.

One line, an integer: the minimum number of letters to erase.

Constraints - For 10% of the testdata, $M = 0$. - For another 30% of the testdata, $N \le 1000$. - For 100% of the testdata, $N \le 100000$, $M \le 400$. Translated by ChatGPT 5