Sorting with Interfering Swaps

Aizhan has a sequence \(S[0], S[1], \dots, S[N-1]\) consisting of \(N\) distinct integers, each in the range \([0, N-1]\). She wishes to sort the sequence in ascending order by performing swap operations. However, her friend Ermek interferes: in each round, Ermek performs a swap on two indices (which are predetermined) before Aizhan makes her move.

The process proceeds in rounds numbered from \(0\) to \(M-1\). In round \(i\):

1. Ermek’s move: Swap the elements at indices \(X[i]\) and \(Y[i]\) (indices may be equal, which means the sequence remains unchanged).
2. Aizhan’s move: After Ermek's swap, if the sequence is already in ascending order (i.e. \(S[0] \le S[1] \le \cdots \le S[N-1]\)), Aizhan may choose to perform a trivial swap (swapping an index with itself) and then the process ends. Otherwise, she must choose a swap that will help move the sequence closer to being sorted.

Before the start of each round, Aizhan checks if the sequence is already sorted. If it is, the process terminates immediately without performing that round.

Task: Given the initial sequence \(S\) and the predetermined Ermek swaps \(X[i]\) and \(Y[i]\) for \(i=0,1,\dots,M-1\), output a sequence of swaps for Aizhan (one swap per round executed) that guarantees that the sequence is sorted at the end. In some subtasks you may be required to output the minimum number of swaps. The problem guarantees that it is possible to sort \(S\) in \(M\) or fewer rounds.

Note: When the sequence is already sorted at the beginning of a round, no further moves are made. Also, if the sequence becomes sorted right after Ermek’s move, Aizhan is allowed to perform a trivial swap (for example, swapping index \(0\) with \(0\)).

For instance, if \(S = [0,3,2,1]\) and the following swaps occur:

• Round 0: Ermek swaps indices \(1\) and \(2\), changing \(S\) from \([0, 3, 2, 1]\) to \([0, 2, 3, 1]\). Aizhan then swaps indices \(1\) and \(3\) (swapping \(2\) and \(1\)) to obtain \([0,1,3,2]\).
• Round 1: Ermek swaps indices \(2\) and \(3\), resulting in \([0,1,2,3]\) which is sorted. Aizhan then performs a trivial swap (e.g. \(0,0\)) and the process terminates.

inputFormat

The input is given in the following format:

N
S[0] S[1] ... S[N-1]
M
X[0] Y[0]
X[1] Y[1]
... 
X[M-1] Y[M-1]

\(N\) is the length of the sequence \(S\) (\(1 \le N \le 10^5\)). \(S\) is a permutation of \(0, 1, 2, \dots, N-1\). \(M\) is the number of rounds (guaranteed to be sufficient to sort \(S\)).

outputFormat

First, output an integer \(K\) representing the number of rounds executed (\(K \le M\)). Following that, output \(K\) lines, each containing two integers representing the indices that Aizhan swaps in that round. If in some round the sequence becomes sorted after Ermek’s move, output a trivial swap (for example, "0 0") for Aizhan’s move in that round.

sample

3
0 1 2
1
0 1

0