CF691D.Swaps in Permutation

You are given a permutation of the numbers 1, 2, ..., n and m pairs of positions (a__j, b__j).

At each step you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation one can get?

Let p and q be two permutations of the numbers 1, 2, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so p__k = q__k for 1 ≤ k < i and p__i < q__i.

给你一个 $1, 2, \dots, n$ 的排列，以及 $m$ 对位置 $(a_j, b_j)$。

每一步中，你可以从给定的位置对中选择一对，并交换该对位置上的数字。问：通过若干次操作，你能得到的字典序最大的排列是什么？

设 $p$ 和 $q$ 是 $1, 2, \dots, n$ 的两个排列。若存在某个 $1 \le i \le n$，使得对所有 $1 \le k < i$ 都有 $p_k = q_k$，且 $p_i < q_i$，则称 $p$ 的字典序小于 $q$。

The first line contains two integers n and m (1 ≤ n, m ≤ 106) — the length of the permutation p and the number of pairs of positions.

The second line contains n distinct integers p__i (1 ≤ p__i ≤ n) — the elements of the permutation p.

Each of the last m lines contains two integers (a__j, b__j) (1 ≤ a__j, b__j ≤ n) — the pairs of positions to swap. Note that you are given a positions, not the values to swap.

第一行包含两个整数 $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$）—— 表示需要交换的位置对。注意：此处给出的是位置，而非待交换的值。

Print the only line with n distinct integers p'i (1 ≤ p'i ≤ n) — the lexicographically maximal permutation one can get.

输出唯一一行，包含 n 个互不相同的整数 p'i（1 ≤ p'i ≤ n），即所能得到的字典序最大的排列。