← 返回题目列表

Codeforces · 691/D

D. 排列交换

中文机器翻译题面 查看原题

给出了数字 1、2、...、n 和 m 对位置 (aj, bj) 的排列。

在每一步中,您都可以从给定的位置中选择一对并交换该位置中的数字。可以得到的字典顺序最大排列是多少?

令 p 和 q 为数字 1、2、...、n 的两个排列。如果存在数字 1 ≤ i ≤ n,则 p 按字典顺序小于 q,因此 pk = qk(对于 1 ≤ k < i 且 pi < qi)。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 106) — 排列 p 的长度和位置对的数量。

第二行包含 n 个不同的整数 pi (1 ≤ pi ≤ n) — 排列 p 的元素。

最后 m 行中的每一行都包含两个整数 (aj, bj) (1 ≤ aj, bj ≤ n) — 要交换的位置对。请注意,您获得的是位置,而不是要交换的值。

输出

打印唯一包含 n 个不同整数 p'i (1 ≤ p'i ≤ n) 的行 — 可以得到的字典顺序最大排列。

示例

输入 #1

9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9

输出 #1

7 8 9 4 5 6 1 2 3