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

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1000005;
int n,m;
vector<int>num[N];
vector<int>pos[N];
int r[N],a[N],ans[N];
priority_queue<int>qu[N];
int findx(int x)
{
    return r[x] == x ? x : r[x] = findx(r[x]);
}

void merge(int x,int y)
{
    int fa=findx(x);
    int fb=findx(y);
    if(fa!=fb)
    {
        r[fa]=fb;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        r[i]=i;
        scanf("%d",&a[i]);
    }

   for(int i=1; i<=m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        merge(a,b);//下标a，b的数可互换，合并；
    }
    for(int i=1; i<=n; i++)
    {
        findx(i);
        qu[r[i]].push(a[i]);//下标为i时，所有可能在那个位置的数，入队，优先队列默认int型数大先出队
    }
    for(int j=1; j<=n; j++)
    {
        printf("%d ",qu[r[j]].top());//取各个位置队顶输出
        qu[r[j]].pop();
    }
    return 0;
}