F - Swap and Sort 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

(1,2,\ldots,N) を並び替えた長さ N の順列 P=(P_1,P_2,\ldots,P_N) があります。

あなたが可能な操作は M 種類あり、操作 i は「 P の a_i 番目の要素と P の b_i 番目の要素を入れ替える」というものです。

操作を好きな順序で、合計 5\times 10^5 回以下行うことによって、P を昇順に並び替えることはできますか？

できるならば、操作手順を 1 つ教えてください。できないならばその旨を伝えてください。

制約

  • 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

操作の回数を最小化する必要はないことに注意してください。

Score : 500 points

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.