← 返回题目列表

AtCoder · abc233_f

I. 交换和排序

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

有 M 种操作可供您使用。操作 i 交换 a_i-th 和 b_i第一个元素 P.

是否可以排序 P 按升序排列最多执行 5\times 10^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) if 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.


示例输入 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

请注意,不需要最小化操作数量。