CF2111E Changing the String

给定一个只包含拉丁字母前 $3$ 个字母的字符串 $s$，即字符串中的每个字符都是 $a$、$b$ 或 $c$。 同时给定 $q$ 个操作。每个操作会给出两个字母 $x$ 和 $y$（均为 $a$、$b$ 或 $c$），对于每个操作，必须执行以下两种操作之一： - 将字符串 $s$ 中任意（一个）出现的字母 $x$ 改为字母 $y$（如果 $x$ 至少出现一次）； - 什么都不做。 目标是按照给定顺序执行所有操作，使得字符串 $s$ 最终字典序最小。 回忆：如果字符串 $a$ 是字符串 $b$ 的前缀且 $a \neq b$，或者在第一个不同的位置，$a$ 的字母比 $b$ 的对应字母在字母表中更靠前，则称字符串 $a$ 的字典序小于字符串 $b$。

每个测试点包含若干组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^{3}$），表示测试数据组数。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \times 10^{5}$），分别表示字符串 $s$ 的长度和操作数。 每组测试数据的第二行给出字符串 $s$，长度恰为 $n$，且每个字符均为 $a$、$b$ 或 $c$。 接下来的 $q$ 行，每行包含两个字符 $x$ 和 $y$，均为 $a$、$b$ 或 $c$，表示一次操作。 额外输入限制： - 所有测试数据中 $n$ 的总和不超过 $2 \times 10^{5}$； - 所有测试数据中 $q$ 的总和不超过 $2 \times 10^{5}$。

对于每组测试数据，输出通过给定操作可以得到的字典序最小的字符串。

在第一个测试用例中，两个操作都需要应用在第一个字母上： 1. 第一个操作后，$s = $ "bb" 2. 第二个操作后，$s = $ "ab" 在第二个测试用例中，字符串的变化过程如下： 1. "bbbbabbbbb"（第 $5$ 个字母被修改） 2. "cbbbabbbbb"（第 $1$ 个字母被修改） 3. "cbbbabbbbb"（未做任何操作） 4. "cbbaabbbbb"（第 $4$ 个字母被修改） 5. "abbaabbbbb"（第 $1$ 个字母被修改） 6. "abcaabbbbb"（第 $3$ 个字母被修改） 7. "abcaabbbbb"（未做任何操作） 8. "aacaabbbbb"（第 $2$ 个字母被修改） 9. "aacaabbbbb"（未做任何操作） 10. "aaaaabbbbb"（第 $3$ 个字母被修改） 由 ChatGPT 4.1 翻译