AT_abc233_f [ABC233F] Swap and Sort

题目描述

有一个长度为 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$，它是 $1,2,\ldots,N$ 的一个排列。

你可以进行 $M$ 种不同的操作，第 $i$ 种操作是“交换 $P$ 的第 $a_i$ 个元素和第 $b_i$ 个元素”。

你可以按照任意顺序，最多进行 $5\times 10^5$ 次操作。请判断是否可以将 $P$ 排成升序。

如果可以，请给出一种操作序列。如果不可以，请说明无法做到。

输入格式

输入通过标准输入按以下格式给出。

$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$

输出格式

如果可以将 $P$ 排成升序，请按以下格式输出：

$K$ $c_1$ $c_2$ $\ldots$ $c_K$

其中，$K$ 表示操作次数，$c_i\ (1\leq i \leq K)$ 表示第 $i$ 次执行的是第 $c_i$ 种操作。
请注意，必须满足 $0\leq K \leq 5\times 10^5$。

如果无法将 $P$ 排成升序，请输出 -1。

输入输出样例 #1

输入 #1

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

输出 #1

3
4 2 1

输入输出样例 #2

输入 #2

5
3 4 1 2 5
2
1 3
2 5

输出 #2

-1

输入输出样例 #3

输入 #3

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

输出 #3

0

说明/提示

限制条件

• $2\leq N \leq 1000$
• $P$ 是 $1,2,\ldots,N$ 的一个排列
• $1\leq M \leq \min(2\times 10^5,\ \frac{N(N-1)}{2})$
• $1\leq a_i < b_i \leq N$
• 若 $i\neq j$，则 $(a_i,b_i)\neq (a_j,b_j)$
• 输入中的所有值均为整数

样例解释 1

$P$ 变化过程如下：$(5,3,2,4,6,1)\to(5,2,3,4,6,1)\to(5,2,3,4,1,6)\to(1,2,3,4,5,6)$。

样例解释 2

无法将 $P$ 排成升序。

样例解释 3

初始时 $P$ 可能已经是升序排列。此外，像下面这样的答案也是正确的：

4 5 5 5 5

注意，不要求操作次数最少。

由 ChatGPT 4.1 翻译