分数: 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
请注意,不需要最小化操作数量。