D. Свопы в перестановке
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана перестановка чисел 1, 2, ..., n, а также m пар позиций (aj, bj).

На каждом шагу вы можете выбрать некоторую пару из заданного набора и поменять местами числа на этих позициях. Найдите лексикографически максимальную перестановку, которую можно получить такими операциями.

Пусть p и q — это две перестановки чисел 1, 2, ..., n. Перестановка p считается лексикографически меньше перестановки q, если существует число 1 ≤ i ≤ n такое, что 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) — лексикографически максимальную перестановку, которую можно получить.

Пример
Входные данные
9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9
Выходные данные
7 8 9 4 5 6 1 2 3