← 返回题目列表

Codeforces · 1682/E

E. 无序交换

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

Alice 有一个从 $$$1$$$ 到 $$$n$$$ 的数字排列 $$$p$$$。 Alice 可以交换一对 $$$(x, y)$$$,这意味着交换 $$$p$$$ 中 $$$x$$$ 和 $$$y$$$ 位置的元素(即交换 $$$p_x$$$ 和 $$$p_y$$$)。 Alice 最近学习了她的第一个排序算法,因此她决定以尽可能少的交换次数对排列进行排序。她按照执行交换的顺序写下了所有交换,以便在一张纸上对排列进行排序。

例如,

- $$$[(2, 3), (1, 3)]$$$ 是 Alice 的有效交换序列 $$$p = [3, 1, 2]$$$ 而 $$$[(1, 3), (2, 3)]$$$ 不是,因为它不对排列进行排序。请注意,我们无法对少于 $$$2$$$ 交换的排列进行排序。
- $$$[(1, 2), (2, 3), (2, 4), (2, 3)]$$$ 不能是 Alice 对 $$$p = [2, 1, 4, 3]$$$ 的交换序列,即使它对排列进行排序,因为 $$$p$$$ 可以在 $$$2$$$ 交换中排序,例如使用序列$$$[(4, 3), (1, 2)]$$$。

不幸的是,Bob 打乱了 Alice 编写的交换序列。

您将获得 Alice 的排列 $$$p$$$ 以及 Alice 以任意顺序执行的交换。你能恢复对排列 $$$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$$$ 行。接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 第 $$$i$$$ 交换 $$$(x_i, y_i)$$$。

保证可以使用这些 $$$m$$$ 交换对 $$$p$$$ 进行排序,并且无法使用少于 $$$m$$$ 交换对 $$$p$$$ 进行排序。

输出

打印 $$$m$$$ 整数的排列 - Alice 编写的有效交换顺序,用于对排列 $$$p$$$ 进行排序。请参阅示例说明以更好地理解。

如果有多个可能的答案,则输出任何一个。

示例

输入 #1

4 3
2 3 4 1
1 4
2 1
1 3

输出 #1

2 3 1

输入 #2

6 4
6 5 1 3 2 4
3 1
2 5
6 3
6 4

输出 #2

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]$$$。