E. Неупорядоченные обмены
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы есть перестановка $$$p$$$ чисел от $$$1$$$ до $$$n$$$. Алиса может поменять местами пару $$$(x, y)$$$, что означает поменять местами элементы в позициях $$$x$$$ и $$$y$$$ в $$$p$$$ (то есть поменять местами $$$p_x$$$ и $$$p_y$$$). Алиса недавно изучила свой первый алгоритм сортировки, поэтому она решила отсортировать свою перестановку за минимальное количество возможных обменов. Она записала на листе бумаги все обмены в том порядке, в котором она их выполняла для сортировки перестановки.

Например,

  • $$$[(2, 3), (1, 3)]$$$ является правильной последовательностью обменов Алисы для перестановки $$$p = [3, 1, 2]$$$, в то время как $$$[(1, 3), (2, 3)]$$$ не является, потому что не сортирует перестановку. Обратите внимание, что мы не можем отсортировать перестановку менее чем за $$$2$$$ обмена.
  • $$$[(1, 2), (2, 3), (2, 4), (2, 3)]$$$ не может быть последовательностью обменов Алисы для $$$p = [2, 1, 4, 3]$$$, даже если она сортирует перестановку, потому что $$$p$$$ можно отсортировать за $$$2$$$ обмена, например, используя последовательность $$$[(4, 3), (1, 2)]$$$.

К сожалению, Боб переставил местами обмены в последовательности, выписанной Алисой.

Вам дана перестановка Алисы $$$p$$$ и обмены, сделанные Алисой в произвольном порядке. Можете ли вы восстановить правильную последовательность обменов, которая сортирует перестановку $$$p$$$? Поскольку Алиса написала правильные обмены до того, как Боб их перемешал, гарантируется, что существует некоторый порядок обменов, который сортирует перестановку.

Входные данные

Первая строка содержит $$$2$$$ целых числа $$$n$$$ и $$$m$$$ $$$(2 \le n \le 2 \cdot 10^5, 1 \le m \le n - 1)$$$  — размер перестановки и минимальное количество обменов, необходимое для сортировки перестановки.

Следующая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, ..., p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны)  — элементы $$$p$$$. Гарантируется, что $$$p$$$ образует перестановку.

Далее следуют $$$m$$$ строк. В $$$i$$$-й из следующих $$$m$$$ строк содержатся два целых числа $$$x_i$$$ и $$$y_i$$$  — обозначающих $$$i$$$-й обмен $$$(x_i, y_i)$$$.

Гарантируется, что можно отсортировать $$$p$$$ с этими $$$m$$$ обменами и что нет способа отсортировать $$$p$$$ с менее чем $$$m$$$ обменами.

Выходные данные

Выведите перестановку $$$m$$$ целых чисел  — правильный порядок обменов, выписанный Алисой, который сортирует перестановку $$$p$$$. Для лучшего понимания обратитесь к объяснению примера.

В случае нескольких возможных ответов выведите любой.

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

В первом примере $$$p = [2, 3, 4, 1]$$$, $$$m = 3$$$ и заданы обмены $$$[(1, 4), (2, 1), (1, 3)]$$$.

Существует только один правильный порядок обмена, а именно $$$[2, 3, 1]$$$.

  1. Сначала мы выполняем обмен $$$2$$$ из входных данных, т.е. $$$(2, 1)$$$, $$$p$$$ становится $$$[3, 2, 4, 1]$$$.
  2. Затем мы выполняем обмен $$$3$$$ из входных данных, т.е. $$$(1, 3)$$$, $$$p$$$ становится $$$[4, 2, 3, 1]$$$.
  3. Наконец, мы выполняем обмен $$$1$$$ из входных данных, т.е. $$$(1, 4)$$$ и $$$p$$$ становится $$$[1, 2, 3, 4]$$$, что является отсортированным.

Во втором примере $$$p = [6, 5, 1, 3, 2, 4]$$$, $$$m = 4$$$ и заданные обмены $$$[(3, 1), (2, 5), (6, 3), (6, 4)]$$$.

Один из возможных правильных порядков обмена  — $$$[4, 2, 1, 3]$$$.

  1. Выполните обмен $$$4$$$ из входных данных, т.е. $$$(6, 4)$$$, $$$p$$$ становится $$$[6, 5, 1, 4, 2, 3]$$$.
  2. Выполните обмен $$$2$$$ из входных данных, т.е. $$$(2, 5)$$$, $$$p$$$ становится $$$[6, 2, 1, 4, 5, 3]$$$.
  3. Выполните обмен $$$1$$$ из входных данных, т.е. $$$(3, 1)$$$, $$$p$$$ становится $$$[1, 2, 6, 4, 5, 3]$$$.
  4. Выполните обмен $$$3$$$ из входных данных, т.е. $$$(6, 3)$$$ и $$$p$$$ становится $$$[1, 2, 3, 4, 5, 6]$$$, что является отсортированным.

Возможны и другие ответы, например, $$$[1, 2, 4, 3]$$$.