CF691D Swaps in Permutation

给定一个 $1,2,...,n$ 的排列，以及 $m$ 个位置对 $(a_{j},b_{j})$。 每一步，你可以选择已给定位置对中的一个，将这两个位置上的数进行交换。你能得到的字典序最大的排列是什么？ 设 $p$ 和 $q$ 是 $1,2,...,n$ 的两个排列。如果存在某个 $1 \leq i \leq n$，使得 $p_{k}=q_{k}$ 对任意 $1 \leq k < i$ 都成立，且 $p_{i}

第一行包含两个整数 $n$ 和 $m$（$1\leq n,m\leq 10^{6}$），表示排列 $p$ 的长度和给定的位置对个数。 第二行包含 $n$ 个互不相同的整数 $p_{i}$（$1\leq p_{i}\leq n$），表示排列 $p$ 的元素。 接下来的 $m$ 行，每行包含两个整数 $(a_{j},b_{j})$（$1\leq a_{j},b_{j}\leq n$），表示可以交换的两个位置。注意，这里给出的为位置而非数值。

输出仅一行，包含 $n$ 个互不相同的整数 $p'_{i}$（$1\leq p'_{i}\leq n$），表示能够得到的字典序最大的排列。

由 ChatGPT 5 翻译