SP21083 LEXSTR - Lexicographically Smallest

Taplu 和 Abhishar 非常喜欢玩拼字游戏。有一天，他们决定用字母小方块发明一个新游戏。Abhishar 用这些方块拼成了一个字符串，并给了 Taplu 一组交换位置的规则对 (i, j)。在这些规则中，“i, j” 表示 Taplu 可以在字符串中任意交换第 i 个和第 j 个字符。然后，他们要求 Taplu 找出通过这些交换，能生成的字典序最小的字符串。

第一行输入一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的个数。 每个测试用例的第一行是字符串 $S$，其长度为 $\text{len}$ ($1 \le \text{len} \le 100000$)。 接下来的一行是整数 $M$ ($1 \le M \le 100000$)，表示可以交换位置的规则数量。 接下来的 $M$ 行，每行包含一对整数 $i$ 和 $j$，表示字符串中第 $i$ 个字符可以与第 $j$ 个字符交换。 注意：$i$ 和 $j$ 可以相同，同样的 $i, j$ 对可以多次出现。

对于每个测试用例，输出一个可以通过交换操作得到的字典序最小的字符串。 **本翻译由 AI 自动生成**