Problem Description

Aizhan has a sequence \( S[0], S[1], \cdots, S[N-1] \) consisting of \( N \) distinct integers, where \( S[i] \) ranges from \( 0 \) to \( N-1 \). Aizhan attempts to sort this sequence in ascending order by swapping certain pairs of elements. Aizhan's friend Ermek also wants to swap certain pairs of elements, but Ermek's swaps may not necessarily help Aizhan's sorting.

Ermek and Aizhan plan to modify the sequence through several rounds. In each round, Ermek performs a swap first, followed by Aizhan. More precisely, the person performing the swap chooses two valid indices and swaps the elements at these indices. Note that the indices may be the same. If they are equal, the swap is performed on the element itself, which does not change the sequence.

Aizhan knows that Ermek does not care about sorting the sequence \( S \). Aizhan also knows which indices Ermek will choose. Ermek plans to participate in \( M \) rounds of swaps, numbered from \( 0 \) to \( M-1 \). For each \( i \) from \( 0 \) to \( M-1 \), Ermek will choose the indices \( X[i] \) and \( Y[i] \) to swap in the \( i \)-th round.

Aizhan aims to sort the sequence \( S \) in ascending order. Before each round, if Aizhan sees that the current sequence is already sorted in ascending order, she will end the sorting process. Given the initial sequence \( S \) and the indices Ermek will choose, please find a sequence of swaps that allows Aizhan to complete the sorting of sequence \( S \). Additionally, in some subtasks, you need to find the shortest possible sequence of swaps to complete the sorting task. The problem guarantees that the sequence \( S \) can be sorted in \( M \) or fewer rounds.

Note that if Aizhan finds that the sequence \( S \) is already sorted after Ermek's swap, Aizhan can choose to swap two elements with the same index (e.g., \( 0 \) and \( 0 \)). This way, the sequence \( S \) remains sorted after this round, achieving Aizhan's goal. Also, if the initial sequence \( S \) is already sorted, the minimum number of sorting rounds required is \( 0 \).

Input Format

• The first line contains a positive integer \( N \), representing the length of the sequence \( S \);
• The second line contains \( N \) positive integers, \( S[0], \cdots, S[N-1] \), representing the initial sequence \( S \);
• The third line contains a positive integer \( M \), representing the number of swaps Ermek plans to perform;
• The fourth to \( M+3 \)-th lines contain two positive integers \( X[i] \) and \( Y[i] \), indicating that for \( 0 \le i \le M-1 \), Ermek plans to swap the elements at indices \( X[i] \) and \( Y[i] \) in the \( i \)-th round.

Output Format

• The first line: the length \( R \) of the swaps;
• The \( 2+i \)-th line (for \( 0 \le i < R \)): \( P[i] \), \( Q[i] \).

Note: \( P \) and \( Q \) are two integer arrays. Use these arrays to report a possible sequence of swaps that Aizhan can use to sort the sequence \( S \). Assume the length of this swap sequence is \( R \). For each \( i \) from \( 0 \) to \( R-1 \), the indices chosen by Aizhan in round \( i \) will be stored in \( P[i] \) and \( Q[i] \). You can assume that arrays \( P \) and \( Q \) have each been allocated \( M \) elements.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
0 4
1 3
3 4

Input Sample #2

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

Output Sample #2

3
1 4
4 2
2 2

Notes/Hints

For \( 100\% \) of the data, \( 1 \le N \le 2 \times 10^5 \), \( 1 \le M \le 6 \times 10^5 \). The value of \( R \) should be minimized.

见题面 Input 部分

见题面 Output 部分