Sorting 2

Aizan has a sequence $S$ of length $N$ that contains each of the integers 0 to $N-1$ exactly once. Aizan wants to sort it into increasing order by swapping the values at two positions.

Ermac, an old friend of Aizan, also swaps the values at two positions of the same sequence. Ermac picks the positions at random and has no intention of sorting anything.

The two of them repeat rounds. In one round Ermac swaps first, then Aizan swaps. A swap means choosing two positions and exchanging the values stored there. The two chosen positions may be equal, and then the sequence stays as it is.

Aizan knows Ermac's whole plan before the first round starts. The plan covers $M$ rounds numbered 0 to $M-1$. In round $i$ Ermac swaps the values at positions $X[i]$ and $Y[i]$.

Before a round starts, if the sequence is already in increasing order, Aizan stops there. Let $R$ be the number of rounds played up to that point. If $S$ is already sorted at the beginning, then $R = 0$. If the sequence is sorted right after Ermac's swap in some round, Aizan can choose the same position twice, and the sequence is sorted at the end of that round.

You are given the sequence $S$ and Ermac's plan $M$, $X$, $Y$. Find the two positions Aizan chooses in each round so that $R$ is as small as possible.

The first line contains the length $N$ of the sequence.

The second line contains $S[0]$ to $S[N-1]$, separated by spaces.

The third line contains the number of rounds $M$ that Ermac planned.

The $i$-th of the next $M$ lines contains $X[i]$ and $Y[i]$, separated by a space.

• $1 \le N \le 500$
• $S$ contains each integer from 0 to $N-1$ exactly once
• $1 \le M \le 1000$
• $0 \le X[i], Y[i] \le N-1$
• Aizan can always sort the sequence within $M$ rounds

On the first line, print the smallest possible number of rounds $R$.

On each of the next $R$ lines, print the positions Aizan chooses. The $i$-th of those lines contains the two positions $P[i]$ and $Q[i]$ chosen in round $i$, separated by a space, with $0 \le P[i] \le Q[i] \le N-1$. Writing $P[i] = Q[i]$ means a swap that leaves the sequence unchanged.

If several answers reach the minimum $R$, print the one whose sequence $P[0], Q[0], P[1], Q[1], \dots, P[R-1], Q[R-1]$, read in that order, is lexicographically smallest.

If $R$ is 0, print only the first line.