﻿CodeForces Round#691.D Swaps in Permutation-Ocrosoft

# CodeForces Round#691.D Swaps in Permutation

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 ≤ in 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 ≤ pin) — the elements of the permutation p.

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

Output

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

Example
input
```9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9
```

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

Solution：

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 1000000+10
using namespace std;
int n,m;
int num[MAXN];
int pre[MAXN];
vector<int> a[MAXN],b[MAXN];
int ans[MAXN];
int find(int x)
{
if(pre[x]!=x)pre[x]=find(pre[x]);
return pre[x];
}
void Union(int x,int y)
{
int fx=find(x),fy=find(y);
pre[fx]=fy;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
pre[i]=i;
scanf("%d",&num[i]);
}
for(int i=0; i<m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
Union(a,b);
}
for(int i=1; i<=n; i++)
{
int x=find(i);
a[x].push_back(i);
b[x].push_back(-num[i]);
}
for(int i=1; i<=n; i++)
{
sort(b[i].begin(),b[i].end());
for(int j=0; j<a[i].size(); j++)
ans[a[i][j]]=-b[i][j];
}
for(int i=1; i<=n; i++)
printf("%d ",ans[i]);
return 0;
}
```