CodeForces 691D Swaps in Permutation

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

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

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<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF / 3;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const int read() 
{
  char ch = getchar();
  while (ch<'0' || ch>'9') ch = getchar();
  int x = ch - '0';
  while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
  return x;
}
int T, n, m, x, y;
int fa[N], g[N], a[N], tot, ans[N];
vector<int> p[N], pp[N];

int get(int x)
{
  return x == fa[x] ? x : fa[x] = get(fa[x]);
}

int main()
{
  //scanf("%d", &T);
  //while (T--)
  {
    scanf("%d%d", &n, &m);
    rep(i, 1, n) a[i] = read(), g[i] = 0, fa[i] = i;
    while (m--)
    {
      x = read(); y = read(); 
      int fx = get(x), fy = get(y);
      if (fx == fy) continue;
      fa[fx] = fy;
    }
    tot = 0;
    rep(i, 1, n)
    {
      get(i); 
      if (!g[fa[i]])
      {
        g[fa[i]] = ++tot;
        p[tot].clear(); 
        pp[tot].clear();
      }
      p[g[fa[i]]].push_back(i);
      pp[g[fa[i]]].push_back(a[i]);
    }
    rep(i, 1, tot)
    {
      sort(pp[i].begin(), pp[i].end());
      for (int j = 0; j < p[i].size(); j++)
      {
        ans[p[i][j]] = pp[i][p[i].size() - j - 1];
      }
    }
    rep(i, 1, n) printf("%d%s", ans[i], i == n ? "\n" : " ");
  }
  return 0;
}