给出了数字 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