Swaps in Permutation

题意翻译

有 $n$ 个整数的数列,由数字 $[1,n]$ 构成,同时还有 $m$ 对交换 $(a_i,b_i)$,表示交换位置 $a_i$ 和位置 $b_i$ 上的值,你可以使用这些交换 $0$ 次及以上。 请你通过这些交换,获得字典序最大的排列并输出。

题目描述

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&lt;i $ and $ p_{i}&lt;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.

输入输出样例

输入样例 #1

9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9

输出样例 #1

7 8 9 4 5 6 1 2 3