题目描述

Aizhan 有一个由 $N$ 个互不相同的整数组成的序列 $S[0],S[1],\cdots,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$，表示序列 $S$ 的长度；
• 第 $2$ 行有 $N$ 个正整数，分别为 $S[0],\cdots,S[N-1]$，即初始序列 $S$；
• 第 $3$ 行有一个正整数 $M$，表示 Ermek 打算做交换的次数；
• 第 $4$ 到 $M+3$ 行，有两个正整数 $X[i]$，$Y[i]$，表示对于 $0\le i\le M-1$, 在第 $i$ 轮 Ermek 打算交换下标为 $X[i]$ 和 $Y[i]$ 的数组。

输出格式

• 第 $1$ 行 : 交换的长度 $R$；
• 第 $2+i$（$0\le i < R$）行：$P[i]$，$Q[i]$。

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

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

3
0 4
1 3
3 4

5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4

3
1 4
4 2
2 2

提示

对于 $100\%$ 的数据，$1 \le N\le 2 \times 10^5$，$1 \le M \le 6 \times 10^5$。要求 $R$ 取最小值。