Description

Aizhan has a sequence $S[0],S[1],\cdots,S[N-1]$ consisting of $N$ distinct integers, where $S[i]$ is in the range $[0,N-1]$. Aizhan tries to sort this sequence in increasing order by swapping some pairs of elements. Aizhan’s friend Ermek also wants to swap some pairs of elements, and Ermek’s swaps may not help Aizhan sort the sequence.

Ermek and Aizhan plan to modify this sequence through several rounds. In each round, Ermek makes one swap first, and then Aizhan makes another swap. More precisely, the person who performs a swap chooses two valid indices and swaps the elements at those indices. Note that the two indices may be the same. If they are equal, it is a swap of an element with itself and does not change the sequence.

Aizhan knows that Ermek does not care about sorting the sequence $S$. She also knows which indices Ermek will choose. Ermek plans to take part in $M$ rounds of swaps, numbered from $0$ to $M-1$. For each $i$ between $0$ and $M-1$, in round $i$, Ermek will swap the elements at indices $X[i]$ and $Y[i]$.

Aizhan wants to sort the sequence $S$ in increasing order. Before each round, if Aizhan sees that the current sequence is already sorted in increasing order, she will stop the sorting process. Given the initial sequence $S$ and the indices Ermek will choose, you need to find a sequence of swaps so that Aizhan can finish sorting $S$. In addition, in some subtasks, you also need to find a swap sequence that is as short as possible. The problem guarantees that $S$ can be sorted in $M$ or fewer rounds.

Note that if Aizhan finds that after Ermek’s swap, the sequence $S$ is already sorted, then Aizhan may choose to swap two identical indices (for example $0$ and $0$). This way, $S$ is still sorted after this round, and Aizhan’s goal is achieved. Also, if the initial sequence $S$ is already sorted, then the minimum number of sorting rounds needed is $0$.

Input Format

• Line $1$ contains a positive integer $N$, the length of the sequence $S$.
• Line $2$ contains $N$ positive integers $S[0],\cdots,S[N-1]$, the initial sequence $S$.
• Line $3$ contains a positive integer $M$, the number of swaps Ermek plans to perform.
• Lines $4$ to $M+3$ each contain two positive integers $X[i]$, $Y[i]$, meaning that for $0\le i\le M-1$, in round $i$, Ermek plans to swap the elements at indices $X[i]$ and $Y[i]$.

Output Format

• Line $1$: the length of the swap sequence $R$.
• Line $2+i$ ($0\le i < R$): $P[i]$, $Q[i]$.

Note: $P$ and $Q$ are two integer arrays. Use these two arrays to report one possible swap sequence with which Aizhan can finish sorting $S$. Suppose the length of this swap sequence is $R$. For each $i$ from $0$ to $R-1$, the indices Aizhan chooses in round $i$ will be stored in $P[i]$ and $Q[i]$. You may assume that arrays $P$ and $Q$ have each been allocated $M$ elements.

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

Hint

For $100\%$ of the testdata, $1 \le N\le 2 \times 10^5$, $1 \le M \le 6 \times 10^5$. It is required that $R$ be minimized.

Translated by ChatGPT 5