A10553 | 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}$ .

The first line contains two integers $n$ and $m$ ( $1<=n,m<=10^{6}$ ) — 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.

Print the only line with $n$ distinct integers $p'_{i}$ ( $1<=p'_{i}<=n$ ) — the lexicographically maximal permutation one can get.