Unordered Swaps

题意翻译

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$ 排列，因为 $p$ 可以在 $2$ 次交换中排序，例如使用序列 $[(4, 3), (1, 2)]$ 。 不幸的是，Bob 打乱了 Alice 编写的交换序列。 你得到 Alice 的排列 $p$ 和 Alice 以任意顺序执行的交换。你能恢复对排列 $p$ 进行排序的正确交换序列吗？由于 Alice 在 Bob 洗牌之前写了正确的交换，因此可以保证存在某种对排列进行排序的交换顺序。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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

**题目大意：**

爱丽丝有一个从1到n的数字排列p。她可以通过交换一对(x, y)来改变排列，即交换p中位置x和y的元素。爱丽丝学习了排序算法，并希望以最少的交换次数对排列进行排序。她在一张纸上按执行顺序记录了所有交换。

不幸的是，鲍勃打乱了爱丽丝记录的交换顺序。

给定爱丽丝的排列p和她的任意顺序执行的交换，要恢复对排列p进行排序的正确交换序列。保证存在某种交换顺序可以对排列进行排序。

**输入输出数据格式：**

**输入格式：**

第一行包含两个整数n和m（2≤n≤2×10^5，1≤m≤n-1）——排列的大小和排序排列所需的最少交换次数。

接下来一行包含n个整数p1, p2, ..., pn（1≤pi≤n，所有pi各不相同）——排列p的元素。保证p形成一个排列。

然后是m行，每行包含两个整数xi和yi——第i个交换(xi, yi)。

保证可以通过这m次交换来排序p，且没有少于m次交换就能排序的方法。

**输出格式：**

打印m个整数的排列——爱丽丝记录的正确交换顺序，以对排列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]。**题目大意：** 爱丽丝有一个从1到n的数字排列p。她可以通过交换一对(x, y)来改变排列，即交换p中位置x和y的元素。爱丽丝学习了排序算法，并希望以最少的交换次数对排列进行排序。她在一张纸上按执行顺序记录了所有交换。 不幸的是，鲍勃打乱了爱丽丝记录的交换顺序。 给定爱丽丝的排列p和她的任意顺序执行的交换，要恢复对排列p进行排序的正确交换序列。保证存在某种交换顺序可以对排列进行排序。 **输入输出数据格式：** **输入格式：** 第一行包含两个整数n和m（2≤n≤2×10^5，1≤m≤n-1）——排列的大小和排序排列所需的最少交换次数。 接下来一行包含n个整数p1, p2, ..., pn（1≤pi≤n，所有pi各不相同）——排列p的元素。保证p形成一个排列。 然后是m行，每行包含两个整数xi和yi——第i个交换(xi, yi)。 保证可以通过这m次交换来排序p，且没有少于m次交换就能排序的方法。 **输出格式：** 打印m个整数的排列——爱丽丝记录的正确交换顺序，以对排列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]。