CF1682E.Unordered Swaps

Alice had a permutation $p$ of numbers from $1$ to $n$. Alice can swap a pair $(x, y)$ which means swapping elements at positions $x$ and $y$ in $p$ (i.e. swap $p_x$ and $p_y$). Alice recently learned her first sorting algorithm, so she decided to sort her permutation in the minimum number of swaps possible. She wrote down all the swaps in the order in which she performed them to sort the permutation on a piece of paper.

For example,

• $[(2, 3), (1, 3)]$ is a valid swap sequence by Alice for permutation $p = [3, 1, 2]$ whereas $[(1, 3), (2, 3)]$ is not because it doesn't sort the permutation. Note that we cannot sort the permutation in less than $2$ swaps.
• $[(1, 2), (2, 3), (2, 4), (2, 3)]$ cannot be a sequence of swaps by Alice for $p = [2, 1, 4, 3]$ even if it sorts the permutation because $p$ can be sorted in $2$ swaps, for example using the sequence $[(4, 3), (1, 2)]$.

Unfortunately, Bob shuffled the sequence of swaps written by Alice.

You are given Alice's permutation $p$ and the swaps performed by Alice in arbitrary order. Can you restore the correct sequence of swaps that sorts the permutation $p$? Since Alice wrote correct swaps before Bob shuffled them up, it is guaranteed that there exists some order of swaps that sorts the permutation.

爱丽丝有一个从 $1$ 到 $n$ 的排列 $p$。爱丽丝可以执行一次交换操作 $(x, y)$，即交换 $p$ 中位置 $x$ 和 $y$ 上的元素（也就是交换 $p_x$ 和 $p_y$）。最近，爱丽丝学习了她的第一个排序算法，于是她决定以最少的交换次数将她的排列 $p$ 排序。她将排序过程中执行的所有交换操作按实际执行顺序记录在一张纸上。

例如：

• 对于排列 $p = [3, 1, 2]$，序列 $[(2, 3), (1, 3)]$ 是爱丽丝可能写出的一个合法交换序列；而 $[(1, 3), (2, 3)]$ 则不合法，因为它不能将该排列排序。注意：该排列无法用少于 $2$ 次交换完成排序。
• 序列 $[(1, 2), (2, 3), (2, 4), (2, 3)]$ 不可能是爱丽丝对 $p = [2, 1, 4, 3]$ 所写的交换序列，尽管它最终能将排列排序，但该排列实际上只需 $2$ 次交换即可排好序（例如使用序列 $[(4, 3), (1, 2)]$）。

不幸的是，鲍勃打乱了爱丽丝写下的交换序列的顺序。

现在你被给定了爱丽丝的原始排列 $p$，以及她所执行的全部交换操作（但顺序是任意打乱的）。你能还原出正确（即能以最少交换次数将 $p$ 排序）的交换操作序列吗？由于鲍勃打乱前爱丽丝所写的交换序列是正确的，因此保证存在某种交换顺序可将排列 $p$ 排序。

The first line contains $2$ integers $n$ and $m$ $(2 \le n \le 2 \cdot 10^5, 1 \le m \le n - 1)$ — the size of permutation and the minimum number of swaps required to sort the permutation.

The next line contains $n$ integers $p_1, p_2, ..., p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct) — the elements of $p$. It is guaranteed that $p$ forms a permutation.

Then $m$ lines follow. The $i$-th of the next $m$ lines contains two integers $x_i$ and $y_i$ — the $i$-th swap $(x_i, y_i)$.

It is guaranteed that it is possible to sort $p$ with these $m$ swaps and that there is no way to sort $p$ with less than $m$ swaps.

第一行包含两个整数 $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$ 行中的第 $i$ 行）包含两个整数 $x_i$ 和 $y_i$ —— 表示第 $i$ 次交换 $(x_i, y_i)$。

保证使用这 $m$ 次交换可以将 $p$ 排序，且不存在少于 $m$ 次交换即可将 $p$ 排序的方法。

Print a permutation of $m$ integers — a valid order of swaps written by Alice that sorts the permutation $p$. See sample explanation for better understanding.

In case of multiple possible answers, output any.

输出一个由 $m$ 个整数组成的排列——即爱丽丝所写的、能将排列 $p$ 排序的一组合法交换顺序。参见样例解释以获得更清晰的理解。

若存在多个可能的答案，输出任意一个即可。

In the first example, $p = [2, 3, 4, 1]$, $m = 3$ and given swaps are $[(1, 4), (2, 1), (1, 3)]$.

There is only one correct order of swaps i.e $[2, 3, 1]$.

1. First we perform the swap $2$ from the input i.e $(2, 1)$, $p$ becomes $[3, 2, 4, 1]$.
2. Then we perform the swap $3$ from the input i.e $(1, 3)$, $p$ becomes $[4, 2, 3, 1]$.
3. Finally we perform the swap $1$ from the input i.e $(1, 4)$ and $p$ becomes $[1, 2, 3, 4]$ which is sorted.

In the second example, $p = [6, 5, 1, 3, 2, 4]$, $m = 4$ and the given swaps are $[(3, 1), (2, 5), (6, 3), (6, 4)]$.

One possible correct order of swaps is $[4, 2, 1, 3]$.

1. Perform the swap $4$ from the input i.e $(6, 4)$, $p$ becomes $[6, 5, 1, 4, 2, 3]$.
2. Perform the swap $2$ from the input i.e $(2, 5)$, $p$ becomes $[6, 2, 1, 4, 5, 3]$.
3. Perform the swap $1$ from the input i.e $(3, 1)$, $p$ becomes $[1, 2, 6, 4, 5, 3]$.
4. Perform the swap $3$ from the input i.e $(6, 3)$ and $p$ becomes $[1, 2, 3, 4, 5, 6]$ which is sorted.

There can be other possible answers such as $[1, 2, 4, 3]$.

在第一个例子中，$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]$。