CF1682E Unordered Swaps

Alice 有一个由 $1$ 到 $n$ 组成的排列 $p$。Alice 可以交换一对 $(x, y)$，即交换 $p$ 中第 $x$ 和第 $y$ 个位置上的元素（即交换 $p_x$ 和 $p_y$）。Alice 最近学会了她的第一个排序算法，因此她决定用最少的交换次数将排列排序。她把所有的交换操作按照执行顺序记在了一张纸上。 例如： - 对于排列 $p = [3, 1, 2]$，$[(2, 3), (1, 3)]$ 是 Alice 的一个有效交换序列，而 $[(1, 3), (2, 3)]$ 不是，因为它不能将排列排序。注意，无法用少于 $2$ 次交换将该排列排序。 - 对于排列 $p = [2, 1, 4, 3]$，$[(1, 2), (2, 3), (2, 4), (2, 3)]$ 不是 Alice 的交换序列，即使它能将排列排序，因为该排列可以用 $2$ 次交换排序，例如 $[(4, 3), (1, 2)]$。 不幸的是，Bob 把 Alice 记录的交换序列顺序打乱了。 现在给你 Alice 的排列 $p$ 以及被打乱顺序的交换操作。你能还原出 Alice 排序排列 $p$ 时实际执行的交换操作顺序吗？由于 Alice 记录的交换操作本身就是正确的，只是顺序被打乱，所以保证存在一种顺序能将排列排序。

第一行包含两个整数 $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$ 行，每行两个整数 $x_i$ 和 $y_i$——第 $i$ 个交换操作 $(x_i, y_i)$。 保证用这 $m$ 个交换操作可以将 $p$ 排序，且无法用更少的交换次数将 $p$ 排序。

输出 $m$ 个整数的一个排列——Alice 实际执行的、能将排列 $p$ 排序的交换操作顺序。具体见样例解释。 如果有多种答案，输出任意一种均可。

在第一个样例中，$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]$。 由 ChatGPT 4.1 翻译