← 返回题目列表

Codeforces · 2111/E

E. 更改字符串

中文机器翻译题面 查看原题

给定一个字符串 $$$s$$$,仅包含拉丁字母表的前三个字母,这意味着该字符串的每个字符是 a, b,或 c.

还给出了需要对字符串执行的 $$$q$$$ 操作。在每个操作中,提供来自拉丁字母表前三个字母的集合中的两个字母 $$$x$$$ 和 $$$y$$$,并且对于每个操作,必须采取以下两个操作之一:

  • 将字符串 $$$s$$$ 中任意(一次)出现的字母 $$$x$$$ 更改为字母 $$$y$$$(如果至少存在一次字母 $$$x$$$);
  • 什么都不做。

目标是按照给定顺序执行所有操作,使得字符串 $$$s$$$ 在字典顺序上变得最小。

回想一下,当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

  • $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \neq b$$$;
  • 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的一个字母比 $$$b$$$ 中相应的字母更早。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行有两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^{5}$$$) — 字符串 $$$s$$$ 的长度和操作次数。

在每个测试用例的第二行中,给出字符串 $$$s$$$ — 一个恰好包含 $$$n$$$ 个字符的字符串,每个字符都是 a, b,或 c.

每个测试用例的接下来的 $$$q$$$ 行包含操作的描述。每行包含两个字符 $$$x$$$ 和 $$$y$$$,每个字符是 a, b,或 c.

输入的附加限制:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$;
  • 所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,输出可以使用给定操作从 $$$s$$$ 获取的按字典顺序排列的最小字符串。

示例

输入
复制

3
2 2
cb
c b
b a
10 10
bbbbbbbbbb
b a
b c
c b
b a
c a
b c
b c
b a
a b
c a
30 20
abcaababcbbcabcbbcabcbabbbbabc
b c
b c
c a
b c
b c
b a
b c
b c
b a
b a
b a
b a
c a
b c
c a
b c
c a
c a
b c
c b

输出
复制

ab
aaaaabbbbb
aaaaaaaaaaaaaaabbbabcbabbbbabc

注意

在第一个测试用例中,两个操作都需要应用于第一个字母:

  1. 第一次操作后,$$$s =$$$ "bb"
  2. 第二次操作后,$$$s =$$$ "ab"

在第二个测试用例中,字符串可能会更改如下:

  1. "bbbbbbbbbb"(更改了第 $$$5$$$ 个字母)
  2. "cbbbabbbbb"(更改了 $$$1$$$-st 字母)
  3. "cbbbabbbbb“(什么也没做)
  4. "cbbaabbbbb"(更改了第 $$$4$$$ 个字母)
  5. "阿巴阿布"(更改了 $$$1$$$-st 字母)
  6. "abcaabbbbb"(更改了 $$$3$$$-rd 字母)
  7. "abcaabbbbb“(什么也没做)
  8. "aacaabbbbb"(更改了 $$$2$$$-nd 字母)
  9. "aacaabbbbb“(什么也没做)
  10. "aaaaabbbbb"(更改了 $$$3$$$-rd 字母)