[IOI2015]sorting排序

时间限制:10s      空间限制:1500MB

题目描述

Aizhan有一个由N个互不相同的整数组成的序列S[0],S[1],…,S[N-1],其中S[i]取值范围是[0,N-1]。Aizhan试图通过交换某些元素对的方法将这个序列按照升序排序。Aizhan的朋友Ermek也想交换某些元素对,Ermek的交换未必有助于Aizhan的排序。
Ermek和Aizhan打算通过若干轮次来修改这个序列。在每一轮,Ermek首先做一次交换,然后Aizhan做另一次交换。更确切地说,做交换的人选择两个有效的下标并交换这两个下标的元素。请注意这两个下标可能相同。如果它们相等,则对这个元素自身做交换,并不改变这个序列。
Aizhan知道Ermek并不关心对序列S排序的事情。Aizhan还知道Ermek将会选择哪些下标。Ermek打算参加M轮交换,将这些轮次从0到M-1编号。对于0到M-1之间的每个i,Ermek在第i轮将选择下标X[i]和Y[i]的元素进行交换。
Aizhan要对序列S按升序进行排序。在每一轮之前,如果Aizhan看到当前的序列已经按升序排列,她将结束这个排序过程。给定初始序列S以及Ermek要选择的下标,请你找出一个交换的序列,使得Aizhan能完成对序列S的排序。此外,在有些子任务中,你还要找出尽可能短的交换序列来完成排序任务。题目保证通过M或更少的轮次能够将序列S排好序。
请注意如果Aizhan发现在Ermek的交换之后,序列S已经排好序,则Aizhan可以选择交换两个相同下标(例如0和0)的元素。这样,序列S在这一轮次之后也完成排序,于是也达到了Aizhan的目标。另外,如果初始序列S就已经排好序,那么所需的最少排序轮数就是0。


输入格式

第 1 行: N
第 2 行: S[0] … S[N-1]
第 3 行: M
第 4 行, …, M+3行: X[i] Y[i]
N: 序列S的长度.
S: 一个整数数组,表示初始序列S。
M: Ermek打算做交换的次数。
X, Y: 长度为M的整数数组。 对于0≤i≤M-1, 在第i轮Ermek打算交换下
标为X[i]和Y[i]的数组。


输出格式

第 1 行: 交换的长度R
第 2+i(0≤i< R)行:P[i] Q[i]
P, Q: 整数数组。利用这两个数组报告Aizhan完成对序列S排序的一种可能的交换序列,假设这个交换序列的长度为R,对于0到R-1之间的每个i, Aizhan在轮次i选择的下标将被存入P[i]和Q[i]。 你可以假设数组P和Q均已分别被分配了M个元素。


样例输入

输入样例1
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2
输入样例2
5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4

样例输出

输出样例1
3
0 4
1 3
3 4
输出样例2
3
1 4
4 2
2 2

提示


题目来源

鸣谢yts1999上传 鸣谢mcfx提供SPJ

Menuappsclose