102335: [AtCoder]ABC233 F - Swap and Sort

Problem Statement

We have a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$.

There are $M$ kinds of operations available to you. Operation $i$ swaps the $a_i$-th and $b_i$-th elements of $P$.

Is it possible to sort $P$ in ascending order by doing at most $5\times 10^5$ operations in total in any order?

If it is possible, give one such sequence of operations. Otherwise, report so.

Constraints

• $2\leq N \leq 1000$
• $P$ is a permutation of $(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$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$P_1$ $P_2$ $\ldots$ $P_N$
$M$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$

Output

If it is possible to sort $P$ in ascending order, print the following:

$K$
$c_1$ $c_2$ $\ldots$ $c_K$

Here, $K$ represents the number of operations to do, and $c_i$ $(1\leq i \leq K)$ means the $i$-th operation to do is Operation $c_i$.
Note that $0\leq K \leq 5\times 10^5$ must hold.

If it is impossible to sort $P$ in ascending order, print -1.

Sample Input 1

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

Sample Output 1

3
4 2 1

$P$ changes as follows: $(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)$.

Sample Input 2

5
3 4 1 2 5
2
1 3
2 5

Sample Output 2

-1

We cannot sort $P$ in ascending order.

Sample Input 3

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

Sample Output 3

0

$P$ may already be sorted in ascending order.

Additionally, here is another accepted output:

4
5 5 5 5

Note that it is not required to minimize the number of operations.

问题描述

我们有一个排列$P=(P_1,P_2,\ldots,P_N)$，表示$(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

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