题目描述

我们有一个排列 $P=(P_1,P_2,\\ldots,P_N)$，其中 $P$ 是 $(1,2,\\ldots,N)$ 的一个排列。

你可以进行 $M$ 种操作之一。第 $i$ 个操作将交换 $P$ 的第 $a_i$ 个元素和第 $b_i$ 个元素。

是否可能通过以任意顺序进行最多 $5\\times 10^5$ 次操作，将 $P$ 排序为升序？

如果可能，请给出一种操作序列。否则，报告不可能。

约束条件

• $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)$。
• 输入中的所有值都是整数。

输入

从标准输入读入数据，输入的格式如下：

$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

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

示例输出 1

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

示例输入 2

5
3 4 1 2 5
2
1 3
2 5

示例输出 2

-1

无法将 $P$ 排序为升序。

示例输入 3

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

示例输出 3

0

$P$ 可能已经按升序排序。

此外，以下也是一种可接受的输出：

4
5 5 5 5

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