跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F1168. Swaps in Permutation

  • ID: 1174
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:进阶
  • 上传者:
  • 搜索
  • 并查集
  • 数学
  • 数据结构
  • 进阶
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Swaps in Permutation

题目描述

D. Swaps in Permutation
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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, 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≤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 a positions, 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.

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


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 641 题。保留原作者与原赛事署名。