当前没有测试数据。

F - 交换和排序

给定一个排列$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$
• $(a_i,b_i)\neq (a_j,b_j)$，当$i\neq 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。

示例

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

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