Codeforces 691D Swaps in Permutation

Time Limit:5000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Description

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, sop_k = q_k for 1 ≤ k < i and p_i < q_i.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁶) — 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 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

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

/*
我本来还以为每种操作只能操作一次，结果可以操作无穷次
“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[1000005],teampos[1000005],a[1000005];
bool vis[1000005];
int cnt,n,m;
vector<int> s[1000005];
void dfs(int k)
{
    team[++cnt]=a[k];
    teampos[cnt]=k;
    vis[k]=1;
    for(int i=0;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=1;i<=n;i++)
            {scanf("%d",&a[i]);vis[i]=0;s[i].clear();}

        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            s[x].push_back(y);
            s[y].push_back(x);
        }
        for(int i=1;i<=n;i++)
        if (!vis[i])
        {
            cnt=0;
            dfs(i);
            sort(teampos+1,teampos+cnt+1);
            sort(team+1,team+cnt+1,cmp);
            for(int j=1;j<=cnt;j++)
                a[teampos[j]]=team[j];
        }
        for(int i=1;i<n;i++)
            printf("%d ",a[i]);
        printf("%d
",a[n]);
    }
    return 0;
}

Codeforces 691D Swaps in Permutation

相关推荐