У Алисы есть перестановка \(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\)? Поскольку Алиса написала правильные обмены до того, как Боб их перемешал, гарантируется, что существует некоторый порядок обменов, который сортирует перестановку.
Выходные данные
Выведите перестановку \(m\) целых чисел — правильный порядок обменов, выписанный Алисой, который сортирует перестановку \(p\). Для лучшего понимания обратитесь к объяснению примера.
В случае нескольких возможных ответов выведите любой.
Примечание
В первом примере \(p = [2, 3, 4, 1]\), \(m = 3\) и заданы обмены \([(1, 4), (2, 1), (1, 3)]\).
Существует только один правильный порядок обмена, а именно \([2, 3, 1]\).
- Сначала мы выполняем обмен \(2\) из входных данных, т.е. \((2, 1)\), \(p\) становится \([3, 2, 4, 1]\).
- Затем мы выполняем обмен \(3\) из входных данных, т.е. \((1, 3)\), \(p\) становится \([4, 2, 3, 1]\).
- Наконец, мы выполняем обмен \(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]\).
- Выполните обмен \(4\) из входных данных, т.е. \((6, 4)\), \(p\) становится \([6, 5, 1, 4, 2, 3]\).
- Выполните обмен \(2\) из входных данных, т.е. \((2, 5)\), \(p\) становится \([6, 2, 1, 4, 5, 3]\).
- Выполните обмен \(1\) из входных данных, т.е. \((3, 1)\), \(p\) становится \([1, 2, 6, 4, 5, 3]\).
- Выполните обмен \(3\) из входных данных, т.е. \((6, 3)\) и \(p\) становится \([1, 2, 3, 4, 5, 6]\), что является отсортированным.
Возможны и другие ответы, например, \([1, 2, 4, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
2 3 4 1
1 4
2 1
1 3
|
2 3 1
|
|
2
|
6 4
6 5 1 3 2 4
3 1
2 5
6 3
6 4
|
4 1 3 2
|