Time Limit: 2 sec / Memory Limit: 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.