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 翻译