## Algorithm

D. Swaps in Permutation
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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, ..., np is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so pk = qk for 1 ≤ k < i and pi < qi.

Input

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 pi (1 ≤ pi ≤ n) — the elements of the permutation p.

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

Output

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

Example
input
Copy
`9 61 2 3 4 5 6 7 8 91 44 72 55 83 66 9`
output
Copy
`7 8 9 4 5 6 1 2 3`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int const N = 1e6 + 1;
int n, m;
int nums[N], ds[N], sols[N];
vector<vector<int> > vals, poss;

int find(int x) {
return (ds[x] == x ? x : (ds[x] = find(ds[x])));
}

int main() {
cin >> n >> m;

for(int i = 0; i < n; i++) {
ds[i] = i;
cin >> nums[i];
}

int a, b;
for(int i = 0; i < m; i++) {
cin >> a >> b;
a--; b--;

ds[find(a)] = find(b);
}

vals.resize(n);
poss.resize(n);

for(int i = 0; i < n; i++) {
vals[find(i)].push_back(nums[i]);
poss[find(i)].push_back(i);
}

for(int i = 0; i < n; i++) {
sort(vals[i].rbegin(), vals[i].rend());

for(int j = 0; j < poss[i].size(); j++)
sols[poss[i][j]] = vals[i][j];
}

for(int i = 0; i < n; i++)
cout << (i == 0 ? "" : " ") << sols[i];
cout << endl;

return 0;
}``````
Copy The Code &

Input

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

Output

cmd
7 8 9 4 5 6 1 2 3