Description
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, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, sopk = 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 apositions, 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.
Sample Input
9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9
7 8 9 4 5 6 1 2 3
/*
我本来还以为每种操作只能操作一次，结果可以操作无穷次
“At each step you can choose a pair from the given positions and swap the numbers in that positions.”
怪我英语不好，┗( T﹏T )┛
DFS或并查集求连通块。
把每一条允许交换的位置看做是图中的一条边，画图会发现：一个连通块内的那些位置是可以任意交换的。
因此，只需找出连通块，每一块内的值从大到小排序就行。 */
#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int team[],teampos[],a[];
bool vis[];
int cnt,n,m;
vector<int> s[];
void dfs(int k)
{
team[++cnt]=a[k];
teampos[cnt]=k;
vis[k]=;
for(int i=;i<s[k].size();i++)
if (!vis[s[k][i]]) dfs(s[k][i]);
}
bool cmp(int a,int b)
{
return a>b;
} int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<=n;i++)
{scanf("%d",&a[i]);vis[i]=;s[i].clear();} for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
s[x].push_back(y);
s[y].push_back(x);
}
for(int i=;i<=n;i++)
if (!vis[i])
{
cnt=;
dfs(i);
sort(teampos+,teampos+cnt+);
sort(team+,team+cnt+,cmp);
for(int j=;j<=cnt;j++)
a[teampos[j]]=team[j];
}
for(int i=;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
return ;
}