交换排序

题目描述

有一个 $(1,2,\ldots,N)$ 的排列 $P=(P_1,P_2,\ldots,P_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

$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)$。

5
3 4 1 2 5
2
1 3
2 5

-1

无法将 $P$ 排成升序。

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

0

$P$ 可能一开始就已经排成升序。

此外,以下也是一种可接受的输出:

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$
• 当 $i\neq j$ 时,$(a_i,b_i)\neq (a_j,b_j)$
• 输入中的所有值均为整数

提示

答案不唯一,输出任意合法解即可。