SP15562 IITKWPCI - Find Lexicographically Smallest Permutation

给你一组 $n$ 个数 $a_1, a_2, \ldots, a_n$。你的任务是对这些数进行排列，使结果在字典序上最小。但请注意，你不能随意交换任意两个数。只有当两个位置 $i$ 和 $j$ 是可交换的位置时，才能交换它们。问题中会给出 $m$ 对可交换位置。 在这些限制条件下，找出 $a_1, a_2, \ldots, a_n$ 的字典序最小排列。 字典序的定义是：如果序列 $(a_1, a_2, \ldots, a_n)$ 在第一个不同的元素上小于序列 $(b_1, b_2, \ldots, b_n)$，即 $a_i < b_i$，那么我们就称 $(a_1, a_2, \ldots, a_n)$ 在字典序上小于 $(b_1, b_2, \ldots, b_n)$。 例如，序列 $(1, 2, 3, 4)$ 小于 $(2, 1, 3, 4)$。

第一行是一个整数 $T$，表示测试用例的数量（$T \leq 10$）。 每个测试用例包括： - 第一行有两个整数 $n$ 和 $m$，其中 $1 \leq n \leq 10^3$，$0 \leq m \leq \min(n \cdot (n - 1) / 2, 10^5)$。 - 第二行包含 $n$ 个整数，依次为 $a_1, a_2, \ldots, a_n$，且满足 $1 \leq a_i \leq 10^6$。 - 接下来的 $m$ 行，每行有两个整数 $i$ 和 $j$，表示可以进行交换的位置。

对于每个测试用例，输出一行，包含 $n$ 个整数，表示根据题目要求排列后的序列。 **本翻译由 AI 自动生成**