Swap and Sort

题目描述

我们有一个排列 $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$。

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

3
4 2 1

5
3 4 1 2 5
2
1 3
2 5

-1

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

0


4
5 5 5 5

提示

$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 \lt b_i\leq N$ $(a_i,b_i)\neq (a_j,b_j)$ 若 $i\neq j$。 输入中的所有值均为整数。$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)$.
我们无法将 $P$ 排序为升序。
$P$ 也可能已经是升序的。 另外，下面是另一个被接受的输出：

注意不要求最小化操作次数。

标签: AtCoder|abc233F

来源

AtCoder|abc233F